dar7yl wrote:

Google is your friend:

http://www.fact-index.com/q/qu/quantum_computer.html

has answers to most of your detailled questions.

However, I'll take a stab at answering your first question, because I'm not aware of any web-source which gives an overview before jumping in to details. It's basically a rehash of part of David Deutsch's "The Fabric of Reality".

>	How does QC relate to CC?

One way to look at this is historically: Turing (& other people like Church who turned out to be working on the foundations of computability theory) were trying to find some way of analysing what sorts of "information processing" was possible in the physical world in a way that whilst clearly physically realizable (in an idealized limiting case of infinite resources) whilst abstracting away as many inconsequential physical details as possible. (I'm trying to avoid the phrase computability here because the mathematical notion of computability was more an outcome of the investigation rather than a motivation for it.) So the Turing machine is a sort of machine built using the elementary physical operations are making marks on tape, moving the tape and changing internal state (where these operations behave as in classical physics). Algorithmics relates to what information processing can be done with these operations and the relative execution time (in terms of numbers of operations). It turns out that of most of the various fundamental models of computation, the sets of physical operations enable both the same information processing and the same execution times, which arguably is what makes algorithmics such an effective subject to study. (Imagine if what you could compute and/or dramatic changes in asymptotic execution time differed from computing device to computing device...)

However, David Deutsch (one of the pioneers of QC) has a neat line about how when building the Turing machine model "Turing thought he understood the physics of marks on tape works". Our current best quantum mechanical models of physics say it's possible build elementary physical operations of computation that manipulate entangled superpositions of states according to the exact rules of quantum mechanics for sets of states which are arbitrary size. (You can debate the experimental/theoretical justification for such hypotheses.) As I understand it (AIUI), this quantum mechanics based model of physical computation doesn't change the fundamental range of what information processing is possible (that is, what is computable) but does have some sequences of quantum operations (algorithms) which produce the same result as classical algorithms but with a smaller asymptotic execution time. However, AIUI it's not the case that all classical algorithms can be converted to quantum algorithms which have asymptotically lower execution times, and there's no small description of how quantum complexity theory relates to all the various classical complexity classes, and indeed many open questions about how they relate.

So quantum computing is what classical computing would be, except you use quantum mechanical physics and all its possiblities in your elementary physical operations rather than classical physics. The question of what changes occur to algorithms depends whether you can relate something about your problem to an operation with different quantum and classical time complexities: appropriately expressed the idea behind Shor's algorithm works on a quantum or classical computer, but its because of superpositions & the quantum fourier transforms different asymptotic complexity the algorithm has different time complexities in QC and CC. It's not just convertability of algorithms between CC and QC but also how the complexity changes.

Hopefully this high level overview will make the more detailled stuff on the web more approachable.

__cheers, dave____________________________________________
www.inf.ed.ac.uk/people/staff/David_Tweed.html
tel: +44 131 651 3447 fax: +44 131 651 3435
X wrote a book about this, which Y was carrying around for a long time with little discernible effect -- John Baez

dar7yl wrote:

>	My experience with computers has mostly been with the classic "von Neumann" architecture, a variant of the other-classical "Turing Machine" universal calculator. I will refer to this as "Classic Computing".

A quantum computer is similar, except that it can do a couple of extra operations. A "nondeterministic Turing machine" and a "quantum computer" are very similar concepts (they are both members a class of concepts, the "counting classes"). They all compute the same functions, but the complexity may be different.

It is not known if they are actually the same (complexity wise), or if either is the same as an ordinary Turing machine, but it is presumed that they are not.

The difference is that while a nondeterministic Turing machine is a totally abstract notion, a quantum computer is something you might be able to actually build.

>	Within Classic Computing, there has evolved the concept of Algorithms, which are codified representations of operations which may be performed using the architecture. I have seen a few references to QC algorithms

Just as nondeterministic algorithms are sequences of operations that can be performed on a nondeterministic machine, quantum algorithms can be performed on a quantum computer.

>	How does QC relate to CC? Can you translate CC algorithms into the QC realm?

CC algorithms are a subset of QC algorithms, so that translation is trivial.

>	And vice-versa?

Yes. Some people seem to think that because quantum computers involve "amplitudes" from the continuous set of complex numbers, quantum computers have an uncountable number of states. But that is generally not so. The total number of reachable states is countable (just as for a classical computer), and at ant fixed time after starting the number of possible states is finite (just as for a classical computer).

For any quantum algorithm there is a classical algorithm that computes a representation of its state as a function of time.

Fine print that doesn't really matter: the classical computer needs access to a random number generator, and the simulation is only statistically the same (i.e. the probability of producing a representation is the same as the probability that the QC will be in the represented state), which is all that can be required, since different runs of the same QC are only statistically the same as each other.

Anticipating your next question:

>	Can you develop a Turing Machine that mimics a QC? (ie, a simulator)

Yes. But it is generally believed that no simulator can work in polynomial time. The status of this belief is similar to the belief that P!=NP, fairly "obviously" true, but no real prospect of a proof.

The obvious way to simulate a quantum computation is exponential.

>	What problem domains can be solved using QC? What can't?

There are some problems for which there are quantum algorithms faster than the best known classical algorithm.

Simulating a physical quantum system is the most obvious and diverse class, but there are also problems of general interest.

Factoring is the best known example. Actually, such problems seem to be surprisingly rare, all fit into a few classes.

They would, however, have a substantial economic impact (both positive and negative). Especially in cryptography.

>	How practical are QC's? ie, how far away from actual computations being performed?

Still a ways. You noted a report of five particles being entangled. When we can reliably do a thousand or so, error correction starts to make headway, and you should be able to do lots.

That we don't know for sure that my last statement is true, reflects the difficulties of the theoretical side of quantum computation. Which even though it has received lots of attention, in my opinion needs much more.

>	If a simulator is possible (see above), does it not follow that the simulator can be used to solve NP-complete problems?.

No. So far as we know, BQP (the quantum equivalent of P) is neither a superset nor a subset of NP.

In other words, NP-complete problems are *not* among those that are known to be polynomial on a quantum computer.

There are fewer problems (like "what is the output of a given quantum computer") believed to be in BQP but not in NP, but I *would* have heard of any proof that none exist.

Both quantum and nondeterministic computers "do many computations in parallel" in a sense, but in two *different* senses (and neither in the obvious sense).

Also,

>	assuming that the simulator can work in polynomial time.

This is quite likely false (it is true iff BQP=P).

If you are at all interested, get the book _Quantum Computation and Quantum Information_ by Nielsen and Chuang. It is well written, complete (as of 2000 which is good enough to start with), and does not assume knowledge of either computation or quantum mechanics.

Ralph Hartley

In article , "dar7yl" writes:

>>

Many claims have been made lately about the existance of "Quantum Computing" and the use of entangled photons (among other techniques) to instantiate such QC's. (See Scientific American, September 2004, p36, "A group ... has entangled five particles, ... the minimum needed for standard error correction").

Some people believe that the problem of converting between a serial state and entanglement and back again may be exponentially complex, in which case there will never be a useful quantum computer. Others disagree. I don't have a clue, but should be interested to hear informed options :-)

>>

Within Classic Computing, there has evolved the concept of Algorithms, which are codified representations of operations which may be performed using the architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5 not yet published). for ISBN's see http://www-cs-faculty.stanford.edu/~knuth/taocp.html )

Algorithms can be rather more general. For example, some of the ones used in statistics operate on probability distributions, which are more general than any state in a von Neumann computer.

>>

I have seen a few references to QC algorithms, but have yet to wrap my puny human brain around the math involved. ( http://www.wordiq.com/definition/Shor's_algorithm ). This aludes to an algorithm for Quantum Fourier Transform ( http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027.pdf ) which is of interest to me, in a signal-processing sort of way.

Actually, it tackles a much harder problem, that of discrete logarithms. As far as I know, it is the only known quantum computer algorithm that would have any practical effect. It would have the effect of making current public key encryption methods (RSA, SSH etc.) useless, and would thereafter be used only by number theorists.

>>	I am trying to reconcile my in-depth experience with Classical Computing (CC) with my meagre knowledge of Quantum Computing (QC). How does QC relate to CC?

Effectively by adding a few extra primitives, that take exponential time on a classical computer and polynomial on a quantum one. That is a crude analogy, and someone else may explain better.

>>	Can you translate CC algorithms into the QC realm? And vice-versa?

Yes - just map each bit to a quantum state. And, to some extent vice versa, though you might get an exponential increase in complexity or time.

>>	Can you develop a Turing Machine that mimics a QC? (ie, a simulator)

Yes, but possibly very expensively or slowly - see above.

>>	What problem domains can be solved using QC? What can't?

Effectively factorisation and discrete logarithms, as far as I know. There are a couple of others (e.g. searching), but they don't seem to offer any significant advantages over classical methods.

>>	How practical are QC's? ie, how far away from actual computations being performed?

See my first point - I don't know, and should be interested to hear.

>>	If a simulator is possible (see above), does it not follow that the simulator can be used to solve NP-complete problems?. That's assuming that the simulator can work in polynomial time.

Which it can't - unless factorisation is in P :-)

Anyway. NP complete problems are among the most trivial of hard problems. Because they are search problems with a cheap check, there are almost always empirical search techniques (often using properties of the way the problem was created) that can find the answer faster. Whereupon it can be checked.

The main exceptions are ones like public key encryption (assuming that factorisation is not in P) where the problem creators have deliberately set out to ensure that such empirical search techniques won't work.

Regards,
Nick Maclaren.

David Tweed wrote in message news:...

>	However, David Deutsch (one of the pioneers of QC) has a neat line about how when building the Turing machine model "Turing thought he understood the physics of marks on tape works".

I don't agree.

Computations proved by Turing to be impossible would still be impossible on a quantum computer because solution brings contradiction.

The sort of computations that a quantum computer is meant for are those believed to be in NP. An informal definition is a puzzle that is too expensive to solve, but the solution if known can be verified easily. The classic example is factoring certain composite numbers.

Turing did consider such problems. In his terminology, these can be solved by a "nondeterministic computation." This confusing term means that while searching for a solution somehow the correct choice is always made. If you think about it, you will see that this is very much the same as the definition of NP.

So now we have uncomputable problems, which cannot be solved, and NP problems, which a quantum computer could do. There are classes of problems in between, solvable but not by a quantum computer. Typically these are competitive games: since there is a competitor with free will, there is no effective way to verify a purported best strategy. So, harder than NP.

dar7yl wrote:

>

Many claims have been made lately about the existance of "Quantum Computing" and the use of entangled photons (among other techniques) to instantiate such QC's. (See Scientific American, September 2004, p36, "A group ... has entangled five particles, ... the minimum needed for standard error correction"). My experience with computers has mostly been with the classic "von Neumann" architecture, a variant of the other-classical "Turing Machine" universal calculator. I will refer to this as "Classic Computing". Within Classic Computing, there has evolved the concept of Algorithms, which are codified representations of operations which may be performed using the architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5 not yet published). for ISBN's see http://www-cs-faculty.stanford.edu/~knuth/taocp.html ) I have seen a few references to QC algorithms, but have yet to wrap my puny human brain around the math involved. ( http://www.wordiq.com/definition/Shor's_algorithm ). This aludes to an algorithm for Quantum Fourier Transform ( http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027.pdf ) which is of interest to me, in a signal-processing sort of way. I am trying to reconcile my in-depth experience with Classical Computing (CC) with my meagre knowledge of Quantum Computing (QC). How does QC relate to CC? Can you translate CC algorithms into the QC realm? And vice-versa?

Yes

>	Can you develop a Turing Machine that mimics a QC? (ie, a simulator)

Yes (to a degree, exponential in time)

>	What problem domains can be solved using QC? What can't?

Same as classical computing. The main attraction to QC is the possibility of changing the complexity classes of algorithms.

>	How practical are QC's? ie, how far away from actual computations being performed?

I'll leave this to someone else to elaborate on but my feeling is that we are a long way away from quantum computers that are large enough to solve /real world/ problems.

>	If a simulator is possible (see above), does it not follow that the simulator can be used to solve NP-complete problems?. That's assuming that the simulator can work in polynomial time.

Simulator works in exponential time

["Followup-To:" header set to sci.physics.research.] On 2004-09-24, Nick Maclaren wrote:

>>>

Within Classic Computing, there has evolved the concept of Algorithms, which are codified representations of operations which may be performed using the architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5 not yet published). for ISBN's see http://www-cs-faculty.stanford.edu/~knuth/taocp.html )

>	Algorithms can be rather more general. For example, some of the ones used in statistics operate on probability distributions, which are more general than any state in a von Neumann computer.

What do you mean? Probability distributions can be represented to any degree of precision by a state of a standard von Neumann computer.

--
Aaron Denney -><-

"dar7yl" schreef in bericht news:kyJ3d.96249$XP3.18686@edtnps84...

>	How does QC relate to CC? Can you develop a Turing Machine that mimics a QC? (ie, a simulator) If a simulator is possible (see above), does it not follow that the simulator can be used to solve NP-complete problems?. That's assuming that the simulator can work in polynomial time.

The question is can you simulate a Quantum Computer QC on a Digital Computer DC.
Before you can answer that question you must have a clear definition of what means to simulate and what is a QC. (You use the word mimics) To start with the last (without going into the details) a QC operates (uses) the concepts of entanglement and superposition.
A DC does not use those concepts. In that respect you can not simulate a QC on a DC.

The same problem you have with the question can you simulate an Analog Computer AC on a DC.
In an Analog Computer all analog components work in parallel, simultaneous. In a DC (even with a multiprocessor) in some way or an other the processes are linked sequential. That means you can not simulate in that respect an AC on a DC.

That does not mean that you can not solve the same problems on an AC versus a DC and on a QC versus a DC.
IMO yes, you can solve the same problems on each however there is a clear timing and accuracy issue.

A much more interesting question is can you simulate a QC on a an AC and if not what you have to do to make it possible.
The issue again here is superposition and entanglement and a clear definition what each means. IMO it should be possible depending on the type of implementation of the quantum processes.

Nicolaas Vroom
https://www.nicvroom.be/

nmm1@cus.cam.ac.uk (Nick Maclaren) writes:

>

Actually, it tackles a much harder problem, that of discrete logarithms. As far as I know, it is the only known quantum computer algorithm that would have any practical effect. It would have the effect of making current public key encryption methods (RSA, SSH etc.) useless, and would thereafter be used only by number theorists.

Not quite. Certainly some encryption methods (like Diffie-Hellman and RSA) would be broken, but there are others that would be completely unaffected by solving the problem of discrete logarithms. SSH isn't an encryption method, it's a protocol that can use any available method, so it would only be affected for a short transition period.

-- Esa Peuha
student of mathematics at the University of Helsinki http://www.helsinki.fi/~peuha/

frisbieinstein@yahoo.com (Patrick Powers) wrote in message news:<9511688f.0409231857.b61cf4f@posting.google.com>...

>	David Tweed wrote in message news:...

> >	However, David Deutsch (one of the pioneers of QC) has a neat line about how when building the Turing machine model "Turing thought he understood the physics of marks on tape works".

>	I don't agree. Computations proved by Turing to be impossible would still be impossible on a quantum computer because solution brings contradiction.

I want to both agree and disagree with you. Turing's uncomputable problems are still uncomputable in the quantum computer model, but I think that's because (as far as we know) physics has turned out to be a Turing-computable system. As far as I know, Turing did not consider quantum mechanics to be relevant when he formulated Turing machines---a remarkable accomplishment nonetheless.

What I think you mean is that Turing's diagonalization proof that uncomputable functions exist still works even for quantum computers (and would indeed still work even for hypothetical machines that can compute uncomputable functions).

>	The sort of computations that a quantum computer is meant for are those believed to be in NP. An informal definition is a puzzle that is too expensive to solve, but the solution if known can be verified easily. The classic example is factoring certain composite numbers.

The classic examples are probably 3-SAT and the Travelling Salesman Problem. These are both NP-complete, and thus quite possibly harder than and provably no easier than factoring, which is not NP-complete*.

>	Turing did consider such problems.

He did? That would be news for historians of computer science. The first time that NP seems to have been proposed (long before it was named) is in a letter from Kurt Goedel to John von Neumann in 1956, two years after Turing's untimely death.

>

In his terminology, these can be solved by a "nondeterministic computation." This confusing term means that while searching for a solution somehow the correct choice is always made. If you think about it, you will see that this is very much the same as the definition of NP. So now we have uncomputable problems, which cannot be solved, and NP problems, which a quantum computer could do.

NP-complete problems are not known to be solvable efficiently on a quantum comptuer.

>	There are classes of problems in between, solvable but not by a quantum computer. Typically these are competitive games: since there is a competitor with free will, there is no effective way to verify a purported best strategy. So, harder than NP.

These games define the polynomial hierarchy (if the games have a bounded number of rounds) or PSPACE (if the games can have an arbitrarily large number of rounds).

Peter Shor

*(to be pedantic, if factoring is NP-complete, than NP = co-NP, something which theoretical computer scientists don't generally think is true).

peterwshor@aol.com (Peter Shor) writes:

>	As far as I know, Turing did not consider quantum mechanics to be relevant when he formulated Turing machines---a remarkable accomplishment nonetheless.

In fact, Turing's motivation was to find out exactly what a human following an algorithm could do, and after he eliminated everything that was irrelevant, he had the definition of a Turing machine.

>	*(to be pedantic, if factoring is NP-complete, than NP = co-NP, something which theoretical computer scientists don't generally think is true).

More importantly, while factoring is not known to be in P, the corresponding decision problem (is a number prime or composite) _is_ known to be in P, whereas for all known NP-complete problems the search and decision problems are complexity equivalent (and probably must be for every NP-complete problem).

-- Esa Peuha
student of mathematics at the University of Helsinki http://www.helsinki.fi/~peuha/

Back to my home page Contents of This Document