Quantum Computer Algorithms [Archive]

dar7yl

Sep21-04, 04:04 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\nMany claims have been made lately about the existance of "Quantum Computing"\nand the use of entangled photons (among other techniques) to instantiate\nsuch QC\'s. (See Scientific American, September 2004, p36, "A group ... has\nentangled five particles, ... the minimum needed for standard error\ncorrection").\n\nMy experience with computers has mostly been with the classic "von Neumann"\narchitecture, a variant of the other-classical "Turing Machine" universal\ncalculator. I will refer to this as "Classic Computing".\n\nWithin Classic Computing, there has evolved the concept of Algorithms, which\nare codified representations of operations which may be performed using the\narchitecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5\nnot yet published). for ISBN\'s see\nhttp://www-cs-faculty.stanford.edu/~knuth/taocp.html )\n\nI have seen a few references to QC algorithms, but have yet to wrap my puny\nhuman brain around the math involved. (\nhttp://www.wordiq.com/definition/Shor\'s_algorithm ). This aludes to an\nalgorithm for Quantum Fourier Transform (\nhttp://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027.pdf ) which is of\ninterest to me, in a signal-processing sort of way.\n\nI am trying to reconcile my in-depth experience with Classical Computing\n(CC) with my meagre knowledge of Quantum Computing (QC).\n\nHow does QC relate to CC?\nCan you translate CC algorithms into the QC realm? And vice-versa?\nCan you develop a Turing Machine that mimics a QC? (ie, a simulator)\nWhat problem domains can be solved using QC? What can\'t?\nHow practical are QC\'s? ie, how far away from actual computations being\nperformed?\nIf a simulator is possible (see above), does it not follow that the\nsimulator can be used to solve NP-complete problems?. That\'s assuming that\nthe simulator can work in polynomial time.\n\nregards,\nDar7yl.\n\n\n\n\n\n\n\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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?
Can you develop a Turing Machine that mimics a QC? (ie, a simulator)
What problem domains can be solved using QC? What can't?
How practical are QC's? ie, how far away from actual computations being
performed?
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.

regards,
Dar7yl.

Ralph Hartley

Sep24-04, 08:10 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>dar7yl wrote:\n\n> My experience with computers has mostly been with the classic "von Neumann"\n> architecture, a variant of the other-classical "Turing Machine" universal\n> calculator. I will refer to this as "Classic Computing".\n\nA quantum computer is similar, except that it can do a couple of extra\noperations. A "nondeterministic Turing machine" and a "quantum computer"\nare very similar concepts (they are both members a class of concepts, the\n"counting classes"). They all compute the same functions, but the\ncomplexity may be different.\n\nIt is not known if they are actually the same (complexity wise), or if\neither is the same as an ordinary Turing machine, but it is presumed that\nthey are not.\n\nThe difference is that while a nondeterministic Turing machine is a totally\nabstract notion, a quantum computer is something you might be able to\nactually build.\n\n> Within Classic Computing, there has evolved the concept of Algorithms, which\n> are codified representations of operations which may be performed using the\n> architecture.\n>\n> I have seen a few references to QC algorithms\n\nJust as nondeterministic algorithms are sequences of operations that can be\nperformed on a nondeterministic machine, quantum algorithms can be\nperformed on a quantum computer.\n\n> How does QC relate to CC?\n> Can you translate CC algorithms into the QC realm?\n\nCC algorithms are a subset of QC algorithms, so that translation is trivial.\n\n> And vice-versa?\n\nYes. Some people seem to think that because quantum computers involve\n"amplitudes" from the continuous set of complex numbers, quantum computers\nhave an uncountable number of states. But that is generally not so. The\ntotal number of reachable states is countable (just as for a classical\ncomputer), and at ant fixed time after starting the number of possible\nstates is finite (just as for a classical computer).\n\nFor any quantum algorithm there is a classical algorithm that computes a\nrepresentation of its state as a function of time.\n\nFine print that doesn\'t really matter: the classical computer needs access\nto a random number generator, and the simulation is only statistically the\nsame (i.e. the probability of producing a representation is the same as the\nprobability that the QC will be in the represented state), which is all\nthat can be required, since different runs of the same QC are only\nstatistically the same as each other.\n\nAnticipating your next question:\n\n> Can you develop a Turing Machine that mimics a QC? (ie, a simulator)\n\nYes. But it is generally believed that no simulator can work in polynomial\ntime. The status of this belief is similar to the belief that P!=NP, fairly\n"obviously" true, but no real prospect of a proof.\n\nThe obvious way to simulate a quantum computation is exponential.\n\n> What problem domains can be solved using QC? What can\'t?\n\nThere are some problems for which there are quantum algorithms faster than\nthe best known classical algorithm.\n\nSimulating a physical quantum system is the most obvious and diverse class,\nbut there are also problems of general interest.\n\nFactoring is the best known example. Actually, such problems seem to be\nsurprisingly rare, all fit into a few classes.\n\nThey would, however, have a substantial economic impact (both positive and\nnegative). Especially in cryptography.\n\n> How practical are QC\'s? ie, how far away from actual computations being\n> performed?\n\nStill a ways. You noted a report of five particles being entangled. When we\ncan reliably do a thousand or so, error correction starts to make headway,\nand you should be able to do lots.\n\nThat we don\'t know for sure that my last statement is true, reflects the\ndifficulties of the theoretical side of quantum computation. Which even\nthough it has received lots of attention, in my opinion needs much more.\n\n> If a simulator is possible (see above), does it not follow that the\n> simulator can be used to solve NP-complete problems?.\n\nNo. So far as we know, BQP (the quantum equivalent of P) is neither a\nsuperset nor a subset of NP.\n\nIn other words, NP-complete problems are *not* among those that are known\nto be polynomial on a quantum computer.\n\nThere are fewer problems (like "what is the output of a given quantum\ncomputer") believed to be in BQP but not in NP, but I *would* have heard of\nany proof that none exist.\n\nBoth quantum and nondeterministic computers "do many computations in\nparallel" in a sense, but in two *different* senses (and neither in the\nobvious sense).\n\nAlso,\n\n> assuming that the simulator can work in polynomial time.\n\nThis is quite likely false (it is true iff BQP=P).\n\nIf you are at all interested, get the book _Quantum Computation and Quantum\nInformation_ by Nielsen and Chuang. It is well written, complete (as of\n2000 which is good enough to start with), and does not assume knowledge of\neither computation or quantum mechanics.\n\nRalph Hartley\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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

Nick Maclaren

Sep24-04, 08:11 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>In article <kyJ3d.96249\\$XP3.18686@edtnps84>,\n"dar7yl" <no_reply@accepted.org> writes:\n|>\n|> Many claims have been made lately about the existance of "Quantum Computing"\n|> and the use of entangled photons (among other techniques) to instantiate\n|> such QC\'s. (See Scientific American, September 2004, p36, "A group ... has\n|> entangled five particles, ... the minimum needed for standard error\n|> correction").\n\nSome people believe that the problem of converting between a serial\nstate and entanglement and back again may be exponentially complex,\nin which case there will never be a useful quantum computer. Others\ndisagree. I don\'t have a clue, but should be interested to hear\ninformed options :-)\n\n|> Within Classic Computing, there has evolved the concept of Algorithms, which\n|> are codified representations of operations which may be performed using the\n|> architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5\n|> not yet published). for ISBN\'s see\n|> http://www-cs-faculty.stanford.edu/~knuth/taocp.html )\n\nAlgorithms can be rather more general. For example, some of the ones\nused in statistics operate on probability distributions, which are\nmore general than any state in a von Neumann computer.\n\n|> I have seen a few references to QC algorithms, but have yet to wrap my puny\n|> human brain around the math involved. (\n|> http://www.wordiq.com/definition/Shor\'s_algorithm ). This aludes to an\n|> algorithm for Quantum Fourier Transform (\n|> http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027.pdf ) which is of\n|> interest to me, in a signal-processing sort of way.\n\nActually, it tackles a much harder problem, that of discrete logarithms.\nAs far as I know, it is the only known quantum computer algorithm that\nwould have any practical effect. It would have the effect of making\ncurrent public key encryption methods (RSA, SSH etc.) useless, and\nwould thereafter be used only by number theorists.\n\n|> I am trying to reconcile my in-depth experience with Classical Computing\n|> (CC) with my meagre knowledge of Quantum Computing (QC).\n|>\n|> How does QC relate to CC?\n\nEffectively by adding a few extra primitives, that take exponential\ntime on a classical computer and polynomial on a quantum one. That\nis a crude analogy, and someone else may explain better.\n\n|> Can you translate CC algorithms into the QC realm? And vice-versa?\n\nYes - just map each bit to a quantum state. And, to some extent\nvice versa, though you might get an exponential increase in\ncomplexity or time.\n\n|> Can you develop a Turing Machine that mimics a QC? (ie, a simulator)\n\nYes, but possibly very expensively or slowly - see above.\n\n|> What problem domains can be solved using QC? What can\'t?\n\nEffectively factorisation and discrete logarithms, as far as I know.\nThere are a couple of others (e.g. searching), but they don\'t seem\nto offer any significant advantages over classical methods.\n\n|> How practical are QC\'s? ie, how far away from actual computations being\n|> performed?\n\nSee my first point - I don\'t know, and should be interested to hear.\n\n|> If a simulator is possible (see above), does it not follow that the\n|> simulator can be used to solve NP-complete problems?. That\'s assuming that\n|> the simulator can work in polynomial time.\n\nWhich it can\'t - unless factorisation is in P :-)\n\nAnyway. NP complete problems are among the most trivial of hard\nproblems. Because they are search problems with a cheap check,\nthere are almost always empirical search techniques (often using\nproperties of the way the problem was created) that can find the\nanswer faster. Whereupon it can be checked.\n\nThe main exceptions are ones like public key encryption (assuming\nthat factorisation is not in P) where the problem creators have\ndeliberately set out to ensure that such empirical search techniques\nwon\'t work.\n\n\nRegards,\nNick Maclaren.\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>In article <kyJ3d.96249$XP3.18686@edtnps84>,
"dar7yl" <no_reply@accepted.org> 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.

Patrick Powers

Sep24-04, 08:14 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>David Tweed <dtweed@inf.ed.ac.uk> wrote in message news:<Pine.LNX.4.44.0409221833350.8694-100000@slim.inf.ed.ac.uk>...\n> However, David Deutsch (one of the pioneers of QC) has a neat line about\n> how when building the Turing machine model "Turing thought he understood\n> the physics of marks on tape works".\n\nI don\'t agree.\n\nComputations proved by Turing to be impossible would still be\nimpossible on a quantum computer because solution brings\ncontradiction.\n\nThe sort of computations that a quantum computer is meant for are\nthose believed to be in NP. An informal definition is a puzzle that\nis too expensive to solve, but the solution if known can be verified\neasily. The classic example is factoring certain composite numbers.\n\nTuring did consider such problems. In his terminology, these can be\nsolved by a "nondeterministic computation." This confusing term means\nthat while searching for a solution somehow the correct choice is\nalways made. If you think about it, you will see that this is very\nmuch the same as the definition of NP.\n\nSo now we have uncomputable problems, which cannot be solved, and NP\nproblems, which a quantum computer could do. There are classes of\nproblems in between, solvable but not by a quantum computer.\nTypically these are competitive games: since there is a competitor\nwith free will, there is no effective way to verify a purported best\nstrategy. So, harder than NP.\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>David Tweed <dtweed@inf.ed.ac.uk> wrote in message news:<Pine.LNX.4.44.0409221833350.8694-100000@slim.inf.ed.ac.uk>...
> 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.

!Q

Sep24-04, 09:22 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>dar7yl wrote:\n> Many claims have been made lately about the existance of "Quantum Computing"\n> and the use of entangled photons (among other techniques) to instantiate\n> such QC\'s. (See Scientific American, September 2004, p36, "A group ... has\n> entangled five particles, ... the minimum needed for standard error\n> correction").\n>\n> My experience with computers has mostly been with the classic "von Neumann"\n> architecture, a variant of the other-classical "Turing Machine" universal\n> calculator. I will refer to this as "Classic Computing".\n>\n> Within Classic Computing, there has evolved the concept of Algorithms, which\n> are codified representations of operations which may be performed using the\n> architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5\n> not yet published). for ISBN\'s see\n> http://www-cs-faculty.stanford.edu/~knuth/taocp.html )\n>\n> I have seen a few references to QC algorithms, but have yet to wrap my puny\n> human brain around the math involved. (\n> http://www.wordiq.com/definition/Shor\'s_algorithm ). This aludes to an\n> algorithm for Quantum Fourier Transform (\n> http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027.pdf ) which is of\n> interest to me, in a signal-processing sort of way.\n>\n> I am trying to reconcile my in-depth experience with Classical Computing\n> (CC) with my meagre knowledge of Quantum Computing (QC).\n>\n> How does QC relate to CC?\n> Can you translate CC algorithms into the QC realm? And vice-versa?\n\nYes\n\n> Can you develop a Turing Machine that mimics a QC? (ie, a simulator)\nYes (to a degree, exponential in time)\n> What problem domains can be solved using QC? What can\'t?\n\nSame as classical computing. The main attraction to QC is the\npossibility of changing the complexity classes of algorithms.\n\n> How practical are QC\'s? ie, how far away from actual computations being\n> performed?\n\n\nI\'ll leave this to someone else to elaborate on but my feeling is that\nwe are a long way away from quantum computers that are large enough to\nsolve /real world/ problems.\n\n\n> If a simulator is possible (see above), does it not follow that the\n> simulator can be used to solve NP-complete problems?. That\'s assuming that\n> the simulator can work in polynomial time.\n\n\nSimulator works in exponential time\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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

Aaron Denney

Sep26-04, 03:21 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>["Followup-To:" header set to sci.physics.research.]\nOn 2004-09-24, Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:\n>|> Within Classic Computing, there has evolved the concept of Algorithms, which\n>|> are codified representations of operations which may be performed using the\n>|> architecture. (see "The Art of Computer Programming, Vols 1..3 (Vols 4, 5\n>|> not yet published). for ISBN\'s see\n>|> http://www-cs-faculty.stanford.edu/~knuth/taocp.html )\n>\n> Algorithms can be rather more general. For example, some of the ones\n> used in statistics operate on probability distributions, which are\n> more general than any state in a von Neumann computer.\n\nWhat do you mean? Probability distributions can be represented to any\ndegree of precision by a state of a standard von Neumann computer.\n\n--\nAaron Denney\n-><-\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>["Followup-To:" header set to sci.physics.research.]
On 2004-09-24, Nick Maclaren <nmm1@cus.cam.ac.uk> 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
-><-

Nicolaas Vroom

Sep27-04, 03:31 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\n\n"dar7yl" <no_reply@accepted.org>\nschreef in bericht news:kyJ3d.96249\\$XP3.18686@edtnps84...\n>\n> How does QC relate to CC?\n> Can you develop a Turing Machine that mimics a QC? (ie, a simulator)\n> If a simulator is possible (see above), does it not follow that the\n> simulator can be used to solve NP-complete problems?.\n> That\'s assuming that\n> the simulator can work in polynomial time.\n\nThe question is can you simulate a Quantum Computer QC on a\nDigital Computer DC.\nBefore you can answer that question you must have a clear\ndefinition of what means to simulate and what is a QC.\n(You use the word mimics)\nTo start with the last (without going into the details) a QC\noperates (uses) the concepts of entanglement and superposition.\nA DC does not use those concepts.\nIn that respect you can not simulate a QC on a DC.\n\nThe same problem you have with the question can you simulate\nan Analog Computer AC on a DC.\nIn an Analog Computer all analog components work in parallel,\nsimultaneous. In a DC (even with a multiprocessor) in some way\nor an other the processes are linked sequential.\nThat means you can not simulate in that respect an AC on a DC.\n\nThat does not mean that you can not solve the same problems\non an AC versus a DC and on a QC versus a DC.\nIMO yes, you can solve the same problems on each\nhowever there is a clear timing and accuracy issue.\n\nA much more interesting question is can you simulate\na QC on a an AC and if not what you have to do to make it\npossible.\nThe issue again here is superposition and entanglement\nand a clear definition what each means.\nIMO it should be possible depending on the type of\nimplementation of the quantum processes.\n\nNicolaas Vroom\nhttp://users.pandora.be/nicvroom/\n\n\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>"dar7yl" <no_reply@accepted.org>
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
http://users.pandora.be/nicvroom/

Esa A E Peuha

Sep27-04, 03:44 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>nmm1@cus.cam.ac.uk (Nick Maclaren) writes:\n\n> Actually, it tackles a much harder problem, that of discrete logarithms.\n> As far as I know, it is the only known quantum computer algorithm that\n> would have any practical effect. It would have the effect of making\n> current public key encryption methods (RSA, SSH etc.) useless, and\n> would thereafter be used only by number theorists.\n\nNot quite. Certainly some encryption methods (like Diffie-Hellman and\nRSA) would be broken, but there are others that would be completely\nunaffected by solving the problem of discrete logarithms. SSH isn\'t an\nencryption method, it\'s a protocol that can use any available method, so\nit would only be affected for a short transition period.\n\n--\nEsa Peuha\nstudent of mathematics at the University of Helsinki\nhttp://www.helsinki.fi/~peuha/\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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/

Peter Shor

Sep27-04, 10:20 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\nfrisbieinstein@yahoo.com (Patrick Powers) wrote in message news:<9511688f.0409231857.b61cf4f@posting.google.c om>...\n> David Tweed <dtweed@inf.ed.ac.uk> wrote in message news:<Pine.LNX.4.44.0409221833350.8694-100000@slim.inf.ed.ac.uk>...\n> > However, David Deutsch (one of the pioneers of QC) has a neat line about\n> > how when building the Turing machine model "Turing thought he understood\n> > the physics of marks on tape works".\n>\n> I don\'t agree.\n>\n> Computations proved by Turing to be impossible would still be\n> impossible on a quantum computer because solution brings\n> contradiction.\n\nI want to both agree and disagree with you. Turing\'s uncomputable\nproblems are still uncomputable in the quantum computer model, but\nI think that\'s because (as far as we know) physics has turned out\nto be a Turing-computable system. As far as I know, Turing did not\nconsider quantum mechanics to be relevant when he formulated Turing\nmachines---a remarkable accomplishment nonetheless.\n\nWhat I think you mean is that Turing\'s diagonalization proof that\nuncomputable functions exist still works even for quantum computers\n(and would indeed still work even for hypothetical machines that can\ncompute uncomputable functions).\n\n> The sort of computations that a quantum computer is meant for are\n> those believed to be in NP. An informal definition is a puzzle that\n> is too expensive to solve, but the solution if known can be verified\n> easily. The classic example is factoring certain composite numbers.\n\nThe classic examples are probably 3-SAT and the Travelling Salesman\nProblem. These are both NP-complete, and thus quite possibly harder\nthan and provably no easier than factoring, which is not NP-complete*.\n\n>\n> Turing did consider such problems.\n\nHe did? That would be news for historians of computer science. The\nfirst time that NP seems to have been proposed (long before it was\nnamed) is in a letter from Kurt Goedel to John von Neumann in 1956,\ntwo years after Turing\'s untimely death.\n\n> In his terminology, these can be\n> solved by a "nondeterministic computation." This confusing term means\n> that while searching for a solution somehow the correct choice is\n> always made. If you think about it, you will see that this is very\n> much the same as the definition of NP.\n>\n> So now we have uncomputable problems, which cannot be solved, and NP\n> problems, which a quantum computer could do.\n\nNP-complete problems are not known to be solvable efficiently on\na quantum comptuer.\n\n> There are classes of\n> problems in between, solvable but not by a quantum computer.\n> Typically these are competitive games: since there is a competitor\n> with free will, there is no effective way to verify a purported best\n> strategy. So, harder than NP.\n\nThese games define the polynomial hierarchy (if the games have a bounded\nnumber of rounds) or PSPACE (if the games can have an arbitrarily large\nnumber of rounds).\n\nPeter Shor\n\n*(to be pedantic, if factoring is NP-complete, than NP = co-NP, something\nwhich theoretical computer scientists don\'t generally think is true).\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>frisbieinstein@yahoo.com (Patrick Powers) wrote in message news:<9511688f.0409231857.b61cf4f@posting.google.com>...
> David Tweed <dtweed@inf.ed.ac.uk> wrote in message news:<Pine.LNX.4.44.0409221833350.8694-100000@slim.inf.ed.ac.uk>...
> > 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).

David Tweed

Sep28-04, 02:28 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>frisbieinstein@yahoo.com (Patrick Powers) wrote\n\n|> However, David Deutsch (one of the pioneers of QC) has a neat line\nabout\n|> how when building the Turing machine model "Turing thought he\nunderstood\n|> the physics of marks on tape works".\n|\n|I don\'t agree.\n|\n|Computations proved by Turing to be impossible would still be\n|impossible on a quantum computer because solution brings\n|contradiction.\n\nI tried (in my typical broken English :-) ) to point out later in that\nparagraph that the what is computable does not change between classical\nand quantum computers, it\'s that sometimes (to the best of our current\nknowledge) asymptotic execution time of algorithms for solving problems\ndiffers between classical and quantum algorithms. But the real point I was\ntrying to make is that computability theory is often (at least from what\nI\'ve seen) presented as an entirely mathematical notion, whereas it\'s\nmore of the form\n\nGIVEN THAT you can do these things in the physical world (physics)\nTHEN building up with these elements these things are possible, these\naren\'t, if you had an oracle which could.... then ..., etc (mathematics)\n\ni.e., it\'s sort of a tower of mathematics built upon some foundations\nwhich come from physics. The quote about Turing thinking he understood the\nphysics of marks on tape is supposed to show that you might have to\nre-evaluate the scope of physical `information processing\' afresh if your\nidea of what\'s physically possible changes. (As originally mentioned,\nturns out the shift from classical to quantum doesn\'t change what\'s\ncomputable, but does change some asymptotic complexities. And there are\ncertainly people trying to come up with some example of a physical\noperation which changes what\'s computable, eg,\n\nhttp://portal.acm.org/citation.cfm?id=1011190\n\nalthough I\'m unqualified to rate whether these ideas are sensible or not.)\n\n|The sort of computations that a quantum computer is meant for are\n|those believed to be in NP. An informal definition is a puzzle that\n|is too expensive to solve, but the solution if known can be verified\n|easily. The classic example is factoring certain composite numbers.\n|\n|Turing did consider such problems. In his terminology, these can be\n|solved by a "nondeterministic computation." This confusing term means\n|that while searching for a solution somehow the correct choice is\n|always made. If you think about it, you will see that this is very\n|much the same as the definition of NP.\n\nI\'ve only a passing knowledge of quantum computation, but it\'s not clear\nto me that nondeterministic computation is _precisely_ how quantum\ncomputation differs from classical computation. In particular, I can\'t\npoint at some element of Shor\'s algorithm and say `aha: that step is a\nnon-deterministic computation\' , where non-deterministic is used the in\ncomputer sense of `magically making the correct choice at some point\'.\n(There are certainly elements there that I can relate to the classical\ncomputational notion of probabilistic computation.) I\'d certainly be\ninterested in a brief, readable reference (paper or web) that clarified\nthe relation between non-deterministic & quantum computation.\n\nIncidentally, it\'s not obvious to me why easy verifiability need be\nimportant for quantum computer algorithms? And certainly most minimisation\nproblems are easy to state yet solutions don\'t come with any simple\nproperty to verify that a solution is a global minimum. And there\'s\nsome work on function minimisation using quantum computing:\n\nwww.iqc.ca/seminar/abstracts/081103.html\n\n|So now we have uncomputable problems, which cannot be solved, and NP\n|problems, which a quantum computer could do. There are classes of\n|problems in between, solvable but not by a quantum computer.\n|Typically these are competitive games: since there is a competitor\n|with free will, there is no effective way to verify a purported best\n|strategy. So, harder than NP.\n\nThis bit loses me.\n\n--\n__cheers, dave____________________________________________\n www.inf.ed.ac.uk/people/staff/David_Tweed.html\ntel: +44 131 651 3447 fax: +44 131 651 3435\nX wrote a book about this, which Y was carrying around for\na long time with little discernible effect -- John Baez\n\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>frisbieinstein@yahoo.com (Patrick Powers) wrote

|> 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 tried (in my typical broken English :-) ) to point out later in that
paragraph that the what is computable does not change between classical
and quantum computers, it's that sometimes (to the best of our current
knowledge) asymptotic execution time of algorithms for solving problems
differs between classical and quantum algorithms. But the real point I was
trying to make is that computability theory is often (at least from what
I've seen) presented as an entirely mathematical notion, whereas it's
more of the form

GIVEN THAT you can do these things in the physical world (physics)
THEN building up with these elements these things are possible, these
aren't, if you had an oracle which could.... then ..., etc (mathematics)

i.e., it's sort of a tower of mathematics built upon some foundations
which come from physics. The quote about Turing thinking he understood the
physics of marks on tape is supposed to show that you might have to
re-evaluate the scope of physical `information processing' afresh if your
idea of what's physically possible changes. (As originally mentioned,
turns out the shift from classical to quantum doesn't change what's
computable, but does change some asymptotic complexities. And there are
certainly people trying to come up with some example of a physical
operation which changes what's computable, eg,

http://portal.acm.org/citation.cfm?id=1011190

although I'm unqualified to rate whether these ideas are sensible or not.)

|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.

I've only a passing knowledge of quantum computation, but it's not clear
to me that nondeterministic computation is _precisely_ how quantum
computation differs from classical computation. In particular, I can't
point at some element of Shor's algorithm and say `aha: that step is a
non-deterministic computation' , where non-deterministic is used the in
computer sense of `magically making the correct choice at some point'.
(There are certainly elements there that I can relate to the classical
computational notion of probabilistic computation.) I'd certainly be
interested in a brief, readable reference (paper or web) that clarified
the relation between non-deterministic & quantum computation.

Incidentally, it's not obvious to me why easy verifiability need be
important for quantum computer algorithms? And certainly most minimisation
problems are easy to state yet solutions don't come with any simple
property to verify that a solution is a global minimum. And there's
some work on function minimisation using quantum computing:

www.iqc.ca/seminar/abstracts/081103.html

|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.

This bit loses me.

--
__{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

Ralph Hartley

Sep28-04, 10:20 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\nDavid Tweed wrote:\n\n> I\'ve only a passing knowledge of quantum computation, but it\'s not clear\n> to me that nondeterministic computation is _precisely_ how quantum\n> computation differs from classical computation.\n\nIt isn\'t, certainly not *precisely*, but they are related.\n\nThey are both connected to the number of accepting paths there are in a\nnon-deterministic computation (of polynomial length).\n\nIn the case of NP the question is "is there at least one path". For Co-NP\nit is "are there zero paths" (intuitively those questions seem the same,\nbut they aren\'t, at least not when you look at the formal versions).\n\nFor QC you assign (by a simple rule) a number to each path, which may be\npositive or negative (or complex, but that can be proven not to matter),\nand ask "what is the square of the sum of the accepting paths?"\n\nComplexity theorists study many others, like "is the number of paths\ndivisible by k?"\n\nQC isn\'t particularly special from a theoretical point of view. If there\nwasn\'t at least the hope that QCs could actually be built, it wouldn\'t merit\nmuch study.\n\nThe relative complexity of *all* of these problem classes is *unknown*, but\nnone are harder than #P, which is "how many paths are there?"\n\n> In particular, I can\'t point at some element of Shor\'s algorithm and say\n> `aha: that step is a non-deterministic computation\' , where\n> non-deterministic is used the in computer sense of `magically making the\n> correct choice at some point\'. (There are certainly elements there that\n> I can relate to the classical computational notion of probabilistic\n> computation.)\n\nRight, QC is *NOT* the same as NP. Factoring is in BQP, and also *happens*\nto be in NP (and Co-NP as well), but there *are* problems in BQP that are\n*not* known to be in NP (they are mostly questions about quantum systems).\n\nSo *no* problem known to be in BQP is known to be NP complete, and *no*\nproblem known to be in NP is known to be BQP complete (or BQP hard, no\nproblems are known to be BQP complete).\n\nSo far as we can tell NP and BQP are completely incomparable, neither is a\nsubset of the other. NP (and NP complete) problems do seem to pop up much\nmore often.\n\n> I\'d certainly be interested in a brief, readable reference (paper or\n> web) that clarified the relation between non-deterministic & quantum\n> computation.\n\nI liked:\n\nhttp://people.cs.uchicago.edu/~fortnow/papers/quantview.pdf\n\nHere is a quote:\n> Many researchers, though, shy away from quantum complexity because it\n> appears that a deep knowledge of physics is necessary to understand BQP.\n> Also most papers use a strange form of notation that make their results\n> appear more dificult than they really are.\n\n> This paper argues that one can think about BQP as just a regular\n> complexity class, conceptually not much diferent than its probabilistic\n> cousin BPP.\n\nIt does require a little background in complexity theory, but none in QM.\nIt explains correctly what I may have garbled.\n\n> Incidentally, it\'s not obvious to me why easy verifiability need be\n> important for quantum computer algorithms? And certainly most\n> minimisation problems are easy to state yet solutions don\'t come with\n> any simple property to verify that a solution is a global minimum.\n\nAs I explained above, it is indeed not obvious. In fact it is most likely\nnot so!\n\nfrisbieinstein@yahoo.com (Patrick Powers) wrote:\n> |So now we have uncomputable problems, which cannot be solved, and NP\n> |problems, which a quantum computer could do.\n\nThat is a common confusion.\n\nRalph Hartley\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>David Tweed wrote:

> I've only a passing knowledge of quantum computation, but it's not clear
> to me that nondeterministic computation is _precisely_ how quantum
> computation differs from classical computation.

It isn't, certainly not *precisely*, but they are related.

They are both connected to the number of accepting paths there are in a
non-deterministic computation (of polynomial length).

In the case of NP the question is "is there at least one path". For Co-NP
it is "are there zero paths" (intuitively those questions seem the same,
but they aren't, at least not when you look at the formal versions).

For QC you assign (by a simple rule) a number to each path, which may be
positive or negative (or complex, but that can be proven not to matter),
and ask "what is the square of the sum of the accepting paths?"

Complexity theorists study many others, like "is the number of paths
divisible by k?"

QC isn't particularly special from a theoretical point of view. If there
wasn't at least the hope that QCs could actually be built, it wouldn't merit
much study.

The relative complexity of *all* of these problem classes is *unknown*, but
none are harder than #P, which is "how many paths are there?"

> In particular, I can't point at some element of Shor's algorithm and say
> `aha: that step is a non-deterministic computation' , where
> non-deterministic is used the in computer sense of `magically making the
> correct choice at some point'. (There are certainly elements there that
> I can relate to the classical computational notion of probabilistic
> computation.)

Right, QC is *NOT* the same as NP. Factoring is in BQP, and also *happens*
to be in NP (and Co-NP as well), but there *are* problems in BQP that are
*not* known to be in NP (they are mostly questions about quantum systems).

So *no* problem known to be in BQP is known to be NP complete, and *no*
problem known to be in NP is known to be BQP complete (or BQP hard, no
problems are known to be BQP complete).

So far as we can tell NP and BQP are completely incomparable, neither is a
subset of the other. NP (and NP complete) problems do seem to pop up much
more often.

> I'd certainly be interested in a brief, readable reference (paper or
> web) that clarified the relation between non-deterministic & quantum
> computation.

I liked:

http://people.cs.uchicago.edu/~fortnow/papers/quantview.pdf

Here is a quote:
> Many researchers, though, shy away from quantum complexity because it
> appears that a deep knowledge of physics is necessary to understand BQP.
> Also most papers use a strange form of notation that make their results
> appear more dificult than they really are.

> This paper argues that one can think about BQP as just a regular
> complexity class, conceptually not much diferent than its probabilistic
> cousin BPP.

It does require a little background in complexity theory, but none in QM.
It explains correctly what I may have garbled.

> Incidentally, it's not obvious to me why easy verifiability need be
> important for quantum computer algorithms? And certainly most
> minimisation problems are easy to state yet solutions don't come with
> any simple property to verify that a solution is a global minimum.

As I explained above, it is indeed not obvious. In fact it is most likely
not so!

frisbieinstein@yahoo.com (Patrick Powers) wrote:
> |So now we have uncomputable problems, which cannot be solved, and NP
> |problems, which a quantum computer could do.

That is a common confusion.

Ralph Hartley

Esa A E Peuha

Sep28-04, 11:50 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>peterwshor@aol.com (Peter Shor) writes:\n\n> As far as I know, Turing did not\n> consider quantum mechanics to be relevant when he formulated Turing\n> machines---a remarkable accomplishment nonetheless.\n\nIn fact, Turing\'s motivation was to find out exactly what a human\nfollowing an algorithm could do, and after he eliminated everything that\nwas irrelevant, he had the definition of a Turing machine.\n\n> *(to be pedantic, if factoring is NP-complete, than NP = co-NP, something\n> which theoretical computer scientists don\'t generally think is true).\n\nMore importantly, while factoring is not known to be in P, the\ncorresponding decision problem (is a number prime or composite) _is_\nknown to be in P, whereas for all known NP-complete problems the search\nand decision problems are complexity equivalent (and probably must be\nfor every NP-complete problem).\n\n--\nEsa Peuha\nstudent of mathematics at the University of Helsinki\nhttp://www.helsinki.fi/~peuha/\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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/