Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 02/09/05 

Date: 9 Feb 2005 20:26:04 GMT

Ralph Hartley <hartley@aic.nrl.navy.mil> wrote:
>examachine@gmail.com wrote:
>> Ralph Hartley wrote:
>>
>>> For any number n of connected qbits, and any acceptable error epsilon,
>>> a classical machine can simulate the quantum one. But the
>>> computational effort required grows with decreasing epsilon and grows
>>> (almost certainly exponentially) with n.
>>
>> I haven't seen any proof of exponential speedup
>
>I said *almost* certainly. The status of BPP?=BQP (the big quantum
>complexity question) is almost exactly the same as P?=NP. Strongly
>suspected to be true, but without much prospect of a proof.

er, the usual quibble, what is suspected to be true?
P is strongly suspected to be -not- equal to NP; what is the case for
(BPP, BQP)? I was also under the impression that BPP is strongly suspected
to be equal to P (but those strong suspicions are not as strong as the
P!=NP ones).

>> Isn't it more likely that there is just a polynomial speedup? (Like quadratic)
>
>Only if there are (classical) polynomial algorithms for factoring and
>discrete logarithms. Both problems *are* polynomial on a Quantum computer,
>and both are strongly suspected *not* to be polynomial on a classical computer.

but subexponential. (that is not terribly beyond polynomial)

>Quite a bit of effort has gone into *trying* to find polynomial algorithms
>for those problems. Modern crypto protocols would essentially collapse if
>one were found.

yes, but cryptology wouldn't collapse, because there -are- non-number
theoretic methods that use a provable NP-complete problem (I can't
remember exactly what these are, I just remember that there are some).

Mitch