David Tweed
Sep23-04, 04:46 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>\nGoogle is your friend:\n\nhttp://www.fact-index.com/q/qu/quantum_computer.html\n\nhas answers to most of your detailled questions.\n\nHowever, I\'ll take a stab at answering your first question, because I\'m\nnot aware of any web-source which gives an overview before jumping in to\ndetails. It\'s basically a rehash of part of David Deutsch\'s "The Fabric of\nReality".\n\n>How does QC relate to CC?\n\nOne way to look at this is historically: Turing (& other people like\nChurch who turned out to be working on the foundations of computability\ntheory) were trying to find some way of analysing what sorts of\n"information processing" was possible in the physical world in a way\nthat whilst clearly physically realizable (in an idealized limiting case\nof infinite resources) whilst abstracting away as many inconsequential\nphysical details as possible. (I\'m trying to avoid the phrase\ncomputability here because the mathematical notion of computability was\nmore an outcome of the investigation rather than a motivation for it.)\nSo the Turing machine is a sort of machine built using the elementary\nphysical operations are making marks on tape, moving the tape and changing\ninternal state (where these operations behave as in classical physics).\nAlgorithmics relates to what information processing can be done with these\noperations and the relative execution time (in terms of numbers of\noperations). It turns out that of most of the various fundamental models\nof computation, the sets of physical operations enable both the same\ninformation processing and the same execution times, which arguably is\nwhat makes algorithmics such an effective subject to study. (Imagine if\nwhat you could compute and/or dramatic changes in asymptotic execution\ntime differed from computing device to computing device...)\n\nHowever, David Deutsch (one of the pioneers of QC) has a neat line about\nhow when building the Turing machine model "Turing thought he understood\nthe physics of marks on tape works". Our current best quantum mechanical\nmodels of physics say it\'s possible build elementary physical operations\nof computation that manipulate entangled superpositions of states\naccording to the exact rules of quantum mechanics for sets of states which\nare arbitrary size. (You can debate the experimental/theoretical\njustification for such hypotheses.) As I understand it (AIUI), this\nquantum mechanics based model of physical computation doesn\'t change the\nfundamental range of what information processing is possible (that is,\nwhat is computable) but does have some sequences of quantum operations\n(algorithms) which produce the same result as classical algorithms but\nwith a smaller asymptotic execution time. However, AIUI it\'s not the case\nthat all classical algorithms can be converted to quantum algorithms which\nhave asymptotically lower execution times, and there\'s no small\ndescription of how quantum complexity theory relates to all the various\nclassical complexity classes, and indeed many open questions about how\nthey relate.\n\nSo quantum computing is what classical computing would be, except you use\nquantum mechanical physics and all its possiblities in your elementary\nphysical operations rather than classical physics. The question of what\nchanges occur to algorithms depends whether you can relate something about\nyour problem to an operation with different quantum and classical time\ncomplexities: appropriately expressed the idea behind Shor\'s algorithm\nworks on a quantum or classical computer, but its because of\nsuperpositions & the quantum fourier transforms different asymptotic\ncomplexity the algorithm has different time complexities in QC and CC.\nIt\'s not just convertability of algorithms between CC and QC but also how\nthe complexity changes.\n\nHopefully this high level overview will make the more detailled stuff on\nthe web more approachable.\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</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>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
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