<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>\nGiven a function f:{0,1}^n --> {0,1}, would it be possible to use the\nShor Oracle to figure out if f is constant?\n\nWith this I mean: determine the period on the output qbit, obtained\napplying a quantum implementation of f over the input qbits put in\nsuperpositioned state. I guess that the period would be 1 iff the\nfunction is constant?\n\nIf this was feasible, then P=NP because the SAT problem could be\naddressed in polynomial time by performing a binary search on the\ninput space.\n\n(Browsing through non-constant input spaces (properly setting selected\ninput qbits to 0 or 1), one could quickly converge to an input (if\nany) which satisfies the given boolean function.)\n\nThanks,\nDavide Della Casa\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>Given a function f:{0,1}^n --> {0,1}, would it be possible to use the
Shor Oracle to figure out if f is constant?
With this I mean: determine the period on the output qbit, obtained
applying a quantum implementation of f over the input qbits put in
superpositioned state. I guess that the period would be 1 iff the
function is constant?
If this was feasible, then P=NP because the SAT problem could be
addressed in polynomial time by performing a binary search on the
input space.
(Browsing through non-constant input spaces (properly setting selected
input qbits to or 1), one could quickly converge to an input (if
any) which satisfies the given boolean function.)
Thanks,
Davide Della Casa
Peter Shor
Jul9-04, 04:49 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>\ndavidedc <davidedc@yahoo.com> wrote in message news:<40eaf3b9\\$1@news.sentex.net>...\n> Given a function f:{0,1}^n --> {0,1}, would it be possible to use the\n> Shor Oracle to figure out if f is constant?\n>\n> With this I mean: determine the period on the output qbit, obtained\n> applying a quantum implementation of f over the input qbits put in\n> superpositioned state. I guess that the period would be 1 iff the\n> function is constant?\n>\n> If this was feasible, then P=NP because the SAT problem could be\n> addressed in polynomial time by performing a binary search on the\n> input space.\n>\n> (Browsing through non-constant input spaces (properly setting selected\n> input qbits to 0 or 1), one could quickly converge to an input (if\n> any) which satisfies the given boolean function.)\n>\n> Thanks,\n> Davide Della Casa\n\nNo. You can use it to find out whether it\'s approximately constant\n(but you can do that classically by just sampling a bunch of random\npoints). Quantum periodicity-finding only gives an approximate\nanswer, so if a function is close to a function with some period, you\'ll\nprobably get that period as the output.\n\nPeter Shor\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>davidedc <davidedc@yahoo.com> wrote in message news:<40eaf3b9$1@news.sentex.net>...
> Given a function f:{0,1}^n --> {0,1}, would it be possible to use the
> Shor Oracle to figure out if f is constant?
>
> With this I mean: determine the period on the output qbit, obtained
> applying a quantum implementation of f over the input qbits put in
> superpositioned state. I guess that the period would be 1 iff the
> function is constant?
>
> If this was feasible, then P=NP because the SAT problem could be
> addressed in polynomial time by performing a binary search on the
> input space.
>
> (Browsing through non-constant input spaces (properly setting selected
> input qbits to or 1), one could quickly converge to an input (if
> any) which satisfies the given boolean function.)
>
> Thanks,
> Davide Della Casa
No. You can use it to find out whether it's approximately constant
(but you can do that classically by just sampling a bunch of random
points). Quantum periodicity-finding only gives an approximate
answer, so if a function is close to a function with some period, you'll
probably get that period as the output.
Peter Shor
Greg Kuperberg
Aug16-04, 01:56 PM
<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\ndavidedc <davidedc@yahoo.com> wrote in message news:<40eaf3b9\\$1@news.sentex.net>...\n> Given a function f:{0,1}^n --> {0,1}, would it be possible to use the\n> Shor Oracle to figure out if f is constant?\n>\n> With this I mean: determine the period on the output qbit, obtained\n> applying a quantum implementation of f over the input qbits put in\n> superpositioned state. I guess that the period would be 1 iff the\n> function is constant?\n\nAs Peter Shor pointed out, Shor\'s algorithm works with statistical\napproximations. In other words it will find some p such that f(x) =\nf(x+p) holds either always or at least usually. This is no help for\nthe hard case of your question.\n\n> If this was feasible, then P=NP because the SAT problem could be\n> addressed in polynomial time by performing a binary search on the\n> input space.\n\nFirst, the correct statement is that if there is a quantum polynomial\ntime algorithm to determine if an arbitrary f is constant,\nthen BQP contains NP. BQP, not P, is the complexity class for\nquantum polynomial time. Unlike P, BQP it is not a priori a subset\nof NP.\n\nSecond, the best algorithm for your question is the Grover search,\nwhich can find a solution to f(x) = 1 in time O(sqrt(2^n)). This is\na surprising result, because a classical blind search of course takes\nlinear time. But O(sqrt(2^n)) is not polynomial time. Moreover, if you\nsequester f in a black box, then it is a theorem that Grover\'s algorithm\nis optimal.\n\nIndeed, one way to state the P vs NP problem is by asking: How much do\nyou lose by sequestering the function f in a black box? If P = NP, then\nyou could miraculously solve the equation f(x) = 1 in polynomial time,\nfor any f computable in polynomial time, in effect by analyzing the\nalgorithm to compute f.\n\n--\n/\\ Greg Kuperberg (UC Davis)\n/ \\\n\\ / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/\n\\/ * All the math that\'s fit to e-print *\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>davidedc <davidedc@yahoo.com> wrote in message news:<40eaf3b9$1@news.sentex.net>...
> Given a function f:{0,1}^n --> {0,1}, would it be possible to use the
> Shor Oracle to figure out if f is constant?
>
> With this I mean: determine the period on the output qbit, obtained
> applying a quantum implementation of f over the input qbits put in
> superpositioned state. I guess that the period would be 1 iff the
> function is constant?
As Peter Shor pointed out, Shor's algorithm works with statistical
approximations. In other words it will find some p such that f(x) =
f(x+p) holds either always or at least usually. This is no help for
the hard case of your question.
> If this was feasible, then P=NP because the SAT problem could be
> addressed in polynomial time by performing a binary search on the
> input space.
First, the correct statement is that if there is a quantum polynomial
time algorithm to determine if an arbitrary f is constant,
then BQP contains NP. BQP, not P, is the complexity class for
quantum polynomial time. Unlike P, BQP it is not a priori a subset
of NP.
Second, the best algorithm for your question is the Grover search,
which can find a solution to f(x) = 1 in time O(\sqrt(2^n)). This is
a surprising result, because a classical blind search of course takes
linear time. But O(\sqrt(2^n)) is not polynomial time. Moreover, if you
sequester f in a black box, then it is a theorem that Grover's algorithm
is optimal.
Indeed, one way to state the P vs NP problem is by asking: How much do
you lose by sequestering the function f in a black box? If P = NP, then
you could miraculously solve the equation f(x) = 1 in polynomial time,
for any f computable in polynomial time, in effect by analyzing the
algorithm to compute f.
--
/\ Greg Kuperberg (UC Davis)
/ \\ / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/
\/ * All the math that's fit to e-print *