11
$\begingroup$

Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also factor integers efficiently.

Is there any actual proof quantum computers can solve some problems faster than classical computers?

|cite|improve this question
$\endgroup$
  • $\begingroup$ some of this is formally captured in open complexity class separations such as BPP=?BQP (1st classical, 2nd QM oriented). there is also the problem of implementation that it is not known (in contrast to classical machines) if QM is really physically feasible. etc... may cook some of this into an answer. $\endgroup$ – vzn Dec 6 '15 at 17:25
  • $\begingroup$ Closely related: Why and how is a quantum computer faster than a regular computer? $\endgroup$ – Gilles 'SO- stop being evil' Jul 18 '16 at 21:46
18
$\begingroup$

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Deutsch–Jozsa algorithm is also worth mentioning. Given access to the oracle of a boolean function $f: \{0,1\}^n\rightarrow \left\{0,1\right\}$, which is known to be uniform or constant (by uniform we mean that it is $0$ for exactly half the possible inputs). Clearly any classical algorithm would require at least $2^{n-1}+1$ queries (in a deterministic setting). Quantum computers can decide this using one query. $\endgroup$ – Ariel Dec 5 '15 at 19:46
  • 11
    $\begingroup$ "quarrying the database" -- I think you might be taking the phrase "data mining" a little too literally. :-) $\endgroup$ – David Richerby Dec 5 '15 at 19:53
  • 1
    $\begingroup$ @DavidRicherby damn autocorrect? (; $\endgroup$ – Ran G. Dec 5 '15 at 20:08
  • 3
    $\begingroup$ @ariel I think this deserves an additional answer! why don't you add it? (you can also mention that this gives the ideas for Simon's algorithm which in turn relates to Shor's algorithm) $\endgroup$ – Ran G. Dec 5 '15 at 20:12
  • $\begingroup$ "Any classical solution that succeeds with high probability requires Ω(N) queries to the database" -- Is this true for non-black-box model as well? Is this proven? $\endgroup$ – user976850 Oct 13 '19 at 21:39
4
$\begingroup$

It depends what you consider an actual proof, and what you mean by "faster". From a complexity theoretic perspective, the answer is no -- we don't have such a proof. BQP (the class of problems which can be solved efficiently by a quantum computer) is contained in PSPACE. Being able to prove a separation between BQP and PSPACE would also imply a separation between P and PSPACE, which is not known.

Note that Grover's algorithm only gives a square root speedup, so there is no contradiction.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Welcome! Unfortunately, your answer seems to contradict itself. You say that, "from a complexity theoretic perspective, the answer is no" but then you give one complexity theoretic argument that the answer is "we don't know" and another saying that the answer is "yes". So how is the answer no? $\endgroup$ – David Richerby Dec 6 '15 at 13:21
  • $\begingroup$ @DavidRicherby The question was "Is there any actual proof". The answer to that question is no. If there were a proof, we would also have a proof that P$\ne$PSPACE, which we don't. -- I have edited the answer to clarify the "no". -- P.S.: I don't understand the last part of your comment: Where do I say the answer is "yes"? $\endgroup$ – Norbert Schuch Dec 6 '15 at 13:31
  • $\begingroup$ The question asks if there is an "actual proof quantum computers can solve some problems faster than classical computers". Grover's algorithm is provably faster than any classical algorithm, so the answer is unambiguously "yes." $\endgroup$ – David Richerby Dec 6 '15 at 13:47
  • 1
    $\begingroup$ @DavidRicherby Grover's algorithm is based on an oracle (this is, a black box), which is nothing you meet in real problems. Once you consider the structure of the problem in the oracle (e.g. verifying a solution for an NP-complete problem), it is (afaik) not clear whether the speed-up persists. $\endgroup$ – Norbert Schuch Dec 6 '15 at 13:48
  • 1
    $\begingroup$ This answer is a bit confusing to read. I think it would help to edit the answer to clarify these points and think through exactly what claims you are trying to make and what reasoning you can offer to support those claims. There are two points I think it'd help to clarify: (a) the difference between a polynomial-time speedup vs a larger speedup, (b) the difference between an algorithm with an oracle vs an ordinary algorithm. Then, use those to explain why Grover's algorithm has a speedup but that doesn't contradict your other statements. $\endgroup$ – D.W.♦ Dec 6 '15 at 19:18
-1
$\begingroup$

you ask about "proof" which might be limited to a mathematical level, but the basic question goes much deeper than that. theoreticians will acknowledge its basically still an open question in general about the relative performance of quantum vs classical algorithms and there is probably no simple/ general answer, but with some expert consensus that Shors algorithm seems to be "unusually fast compared to expected best classical speed." fast factoring in a classical computer will break widely held cryptographic security assumptions such as the RSA system.

  • some of this is captured formally in the open complexity class question BPP =? BQP question. these are the analogous classical and quantum classes and the separation is unknown and an active area of research.

  • a closely related question is whether physically QM computers can be built that match the theoretical specifications and a few/ minority of scientists (aka "skeptics") are arguing that there may be noise or scaling laws that prevent QM scaling as envisioned in the theory. in a sense the ultimate "proof" of a QM computer speed must be a physical implementation. (this is similar to the way the Church-Turing thesis is theoretical but seems to ultimately tie into an assertion about physical implementations.) some researchers are talking about Church-Turing analogs in QM computing. see eg Church Turing thesis in a quantum world by Montanaro.

  • relevant to/ impinging on this question/ debate are ongoing substantial/ "heated" (scientific) attempts to benchmark the worlds current "largest" quantum computer by DWave. this is a big topic with a lot of related material, but for a relatively recent overview try D-Wave disputes benchmark study showing sluggish quantum computer / the Register

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.