Urs Schreiber
Mar22-05, 02:23 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>M. Rasetti is a theorist from Torino university. He says he is working\non trying to figure out if quantum computation (QC) is fundamentally\nstronger than classical Turing-like computations. In other words, if\nQC can solve problems which are not in P in polynomial time.\n\nI know that there is a meme floating around some brains which says\nthat if you had a quantum system goverened by a Hamiltonian whose\ndiscrete eigenvalues are a sufficiently hard to compute function of\nthe integers you could, by measuring these eigenvalues in a suitably\nprepared system, essentially compute this function and hence solve\nnot-P problems in polynomial time.\n\nThis argument I always found rather less than convincing. It suffices\nto note that by precisely the same argument you could claim that a\nclassical analog computer may compute NP problems easily: Just\npartition classical phase space into a denumerable number of subsets\nand pick a system whose energy is a non-computable function of the\nordinal associated to each such subset. Up to some smoothness issues\nthis is precisely the analogous idea as above -- and clearly not a\nreasonable way to get a stronger-than-classical computer.\n\nWhat Rasetti is talking about sounds much more sophisticated -- though\nin the end it seems to reduce to more or less the above argument. Or\ndoes it?\n\nSo the idea is that there may be more types of quantum computers than\ncurrently considered in the standard literature. In particular, so\nRasetti\'s idea, using systems that have to be described by quantum\n<em>field</em> theory one might be able to (in principle) construct\nnew and more powerful types of quantum computers.\n\nThis idea apparently goes back to Michael Friedman, who first proposed\nthat non-abelian topological quantum field theories might exhibit\nfeatures necessary so support a model of computation capable of\nsolving not-P problems in polynomial time?\n\nApparently Friedman, Kitaev and Wang in particular proposed that\nChern-Simons theory is a promising candidate.\n\nI have not yet managed to talk to Rasetti and ask him some questions\nabout his work, but if I understood correctly what he said in a talk\nthe idea is this:\n\nThe computation of non-abelian holonomy as well as that of Jones\npolynomials is not in P. Since the observables of CS theory are\nprecisely these quantities all we have to do is to set up a system\nwhich is goverened by CS theory, somehow prepare it to be in a given\nknot state and then observe its observables. Since these will be not-P\nfunctions of these knots, we effectively have an analog quantum\ncomputer which computes not-P problems easily.\n\nDoes that make sense? Isn\'t it precisely the same idea as mentioned at\nthe very beginning, that given any system whose observables are a\nnot-P function of its states it superficially looks like a device that\ncomputes not-P problems in polynomial time.\n\nI have the feeling that something is wrong here.\n\nI also feel that there should be a high-brow theoretical answer for\nwhat is wrong or why this is not wrong and am surprised that among\nQC-theorists there apparetly is no clarity about this.\n\nSo for me the conclusion of Rasetti\'s talk is currently just that if\nyou are willing to be interested in systems whose observables are\nnon-P funtons of their states, then some quantum field theories in\ngeneral and Chern-Simons theory in particular suggst themselves as\nlaboratories since they do enjoy this property naturally.\n\nIt seems to me that the issue here is related to the general question\nin as much we want to regard analog computers as computers when it\ncomes to complexity issues. I am not a computation theorist so what I\nam saying here will sound crude to those who are, but let me say it\nanyway:\n\nClearly when talking about computational complexity one has to remove\nanalog computers from the picture somehow. For instance protein\nfolding is a famouns hard problem. It remains hard, even though I can\nfigure out how a protein folds easily by just synthesizing it and\nseeing how it folds. That\'s an analog computation and I bet it scales\nlinearly with the size of the protein. You might rather want to call\nit an experiment, though.\n\nAnd that\'s the point, I think. It\'s an experiment rather than a\ncomputation. And the same is true for the Chern-Simons computer\nproposed by Rasetti et al. They propose to make experiments in field\ntheory and regard the measurement of the outcome as a calculation.\n\nFor practical purposes that may be fine. If I really want to know the\nvalue of some Jones polynomial and I really find it easier to come up\nwith a system governed by CS theory, prepare it suitably and measure\nits observables somehow with sufficient accuracy, than to compute the\npolynomial on a digital computer up to that accuracy then that\'s fine\nI guess.\n\nBut\n\na) this has little to do with quantum computation and is all about\nanalog computers, and\n\nb) it does hence not show that quantum computers are inherently more\npowerful than classical ones.\n\nI assume the problem is related to the fact that we really want to\nstudy _universal_ computers, not just special-purpose ones. I believe\nthe problem is to figure out if a _universal_ quantum computer is more\npowerful than the universal Turing machine.\n\n(This message is also available at\nhttp://golem.ph.utexas.edu/string/archives/000534.html )\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>M. Rasetti is a theorist from Torino university. He says he is working
on trying to figure out if quantum computation (QC) is fundamentally
stronger than classical Turing-like computations. In other words, if
QC can solve problems which are not in P in polynomial time.
I know that there is a meme floating around some brains which says
that if you had a quantum system goverened by a Hamiltonian whose
discrete eigenvalues are a sufficiently hard to compute function of
the integers you could, by measuring these eigenvalues in a suitably
prepared system, essentially compute this function and hence solve
not-P problems in polynomial time.
This argument I always found rather less than convincing. It suffices
to note that by precisely the same argument you could claim that a
classical analog computer may compute NP problems easily: Just
partition classical phase space into a denumerable number of subsets
and pick a system whose energy is a non-computable function of the
ordinal associated to each such subset. Up to some smoothness issues
this is precisely the analogous idea as above -- and clearly not a
reasonable way to get a stronger-than-classical computer.
What Rasetti is talking about sounds much more sophisticated -- though
in the end it seems to reduce to more or less the above argument. Or
does it?
So the idea is that there may be more types of quantum computers than
currently considered in the standard literature. In particular, so
Rasetti's idea, using systems that have to be described by quantum
<em>field</em> theory one might be able to (in principle) construct
new and more powerful types of quantum computers.
This idea apparently goes back to Michael Friedman, who first proposed
that non-abelian topological quantum field theories might exhibit
features necessary so support a model of computation capable of
solving not-P problems in polynomial time?
Apparently Friedman, Kitaev and Wang in particular proposed that
Chern-Simons theory is a promising candidate.
I have not yet managed to talk to Rasetti and ask him some questions
about his work, but if I understood correctly what he said in a talk
the idea is this:
The computation of non-abelian holonomy as well as that of Jones
polynomials is not in P. Since the observables of CS theory are
precisely these quantities all we have to do is to set up a system
which is goverened by CS theory, somehow prepare it to be in a given
knot state and then observe its observables. Since these will be not-P
functions of these knots, we effectively have an analog quantum
computer which computes not-P problems easily.
Does that make sense? Isn't it precisely the same idea as mentioned at
the very beginning, that given any system whose observables are a
not-P function of its states it superficially looks like a device that
computes not-P problems in polynomial time.
I have the feeling that something is wrong here.
I also feel that there should be a high-brow theoretical answer for
what is wrong or why this is not wrong and am surprised that among
QC-theorists there apparetly is no clarity about this.
So for me the conclusion of Rasetti's talk is currently just that if
you are willing to be interested in systems whose observables are
non-P funtons of their states, then some quantum field theories in
general and Chern-Simons theory in particular suggst themselves as
laboratories since they do enjoy this property naturally.
It seems to me that the issue here is related to the general question
in as much we want to regard analog computers as computers when it
comes to complexity issues. I am not a computation theorist so what I
am saying here will sound crude to those who are, but let me say it
anyway:
Clearly when talking about computational complexity one has to remove
analog computers from the picture somehow. For instance protein
folding is a famouns hard problem. It remains hard, even though I can
figure out how a protein folds easily by just synthesizing it and
seeing how it folds. That's an analog computation and I bet it scales
linearly with the size of the protein. You might rather want to call
it an experiment, though.
And that's the point, I think. It's an experiment rather than a
computation. And the same is true for the Chern-Simons computer
proposed by Rasetti et al. They propose to make experiments in field
theory and regard the measurement of the outcome as a calculation.
For practical purposes that may be fine. If I really want to know the
value of some Jones polynomial and I really find it easier to come up
with a system governed by CS theory, prepare it suitably and measure
its observables somehow with sufficient accuracy, than to compute the
polynomial on a digital computer up to that accuracy then that's fine
I guess.
But
a) this has little to do with quantum computation and is all about
analog computers, and
b) it does hence not show that quantum computers are inherently more
powerful than classical ones.
I assume the problem is related to the fact that we really want to
study _universal_ computers, not just special-purpose ones. I believe
the problem is to figure out if a _universal_ quantum computer is more
powerful than the universal Turing machine.
(This message is also available at
http://golem.ph.utexas.edu/string/archives/000534.html )
on trying to figure out if quantum computation (QC) is fundamentally
stronger than classical Turing-like computations. In other words, if
QC can solve problems which are not in P in polynomial time.
I know that there is a meme floating around some brains which says
that if you had a quantum system goverened by a Hamiltonian whose
discrete eigenvalues are a sufficiently hard to compute function of
the integers you could, by measuring these eigenvalues in a suitably
prepared system, essentially compute this function and hence solve
not-P problems in polynomial time.
This argument I always found rather less than convincing. It suffices
to note that by precisely the same argument you could claim that a
classical analog computer may compute NP problems easily: Just
partition classical phase space into a denumerable number of subsets
and pick a system whose energy is a non-computable function of the
ordinal associated to each such subset. Up to some smoothness issues
this is precisely the analogous idea as above -- and clearly not a
reasonable way to get a stronger-than-classical computer.
What Rasetti is talking about sounds much more sophisticated -- though
in the end it seems to reduce to more or less the above argument. Or
does it?
So the idea is that there may be more types of quantum computers than
currently considered in the standard literature. In particular, so
Rasetti's idea, using systems that have to be described by quantum
<em>field</em> theory one might be able to (in principle) construct
new and more powerful types of quantum computers.
This idea apparently goes back to Michael Friedman, who first proposed
that non-abelian topological quantum field theories might exhibit
features necessary so support a model of computation capable of
solving not-P problems in polynomial time?
Apparently Friedman, Kitaev and Wang in particular proposed that
Chern-Simons theory is a promising candidate.
I have not yet managed to talk to Rasetti and ask him some questions
about his work, but if I understood correctly what he said in a talk
the idea is this:
The computation of non-abelian holonomy as well as that of Jones
polynomials is not in P. Since the observables of CS theory are
precisely these quantities all we have to do is to set up a system
which is goverened by CS theory, somehow prepare it to be in a given
knot state and then observe its observables. Since these will be not-P
functions of these knots, we effectively have an analog quantum
computer which computes not-P problems easily.
Does that make sense? Isn't it precisely the same idea as mentioned at
the very beginning, that given any system whose observables are a
not-P function of its states it superficially looks like a device that
computes not-P problems in polynomial time.
I have the feeling that something is wrong here.
I also feel that there should be a high-brow theoretical answer for
what is wrong or why this is not wrong and am surprised that among
QC-theorists there apparetly is no clarity about this.
So for me the conclusion of Rasetti's talk is currently just that if
you are willing to be interested in systems whose observables are
non-P funtons of their states, then some quantum field theories in
general and Chern-Simons theory in particular suggst themselves as
laboratories since they do enjoy this property naturally.
It seems to me that the issue here is related to the general question
in as much we want to regard analog computers as computers when it
comes to complexity issues. I am not a computation theorist so what I
am saying here will sound crude to those who are, but let me say it
anyway:
Clearly when talking about computational complexity one has to remove
analog computers from the picture somehow. For instance protein
folding is a famouns hard problem. It remains hard, even though I can
figure out how a protein folds easily by just synthesizing it and
seeing how it folds. That's an analog computation and I bet it scales
linearly with the size of the protein. You might rather want to call
it an experiment, though.
And that's the point, I think. It's an experiment rather than a
computation. And the same is true for the Chern-Simons computer
proposed by Rasetti et al. They propose to make experiments in field
theory and regard the measurement of the outcome as a calculation.
For practical purposes that may be fine. If I really want to know the
value of some Jones polynomial and I really find it easier to come up
with a system governed by CS theory, prepare it suitably and measure
its observables somehow with sufficient accuracy, than to compute the
polynomial on a digital computer up to that accuracy then that's fine
I guess.
But
a) this has little to do with quantum computation and is all about
analog computers, and
b) it does hence not show that quantum computers are inherently more
powerful than classical ones.
I assume the problem is related to the fact that we really want to
study _universal_ computers, not just special-purpose ones. I believe
the problem is to figure out if a _universal_ quantum computer is more
powerful than the universal Turing machine.
(This message is also available at
http://golem.ph.utexas.edu/string/archives/000534.html )