8
$\begingroup$

I mean are we certain that they will be able to provide us a huge improvements (in some tasks) compared to clasical computers?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
5
$\begingroup$

The answer is no. We cannot be 100% certain.
Just like we don't have a proof that P $\ne$ NP, there is no proof that NP $\ne$ QMA, though we believe both these inequalities to be true even without proof.

Furthermore, we do not know how the "engineering complexity" scales, so even though Shor's algorithm has exponentially fewer operations to perform than the best known classical algorithm, it might be double exponentially more difficult to implement it physically. See my answer to this question: Are there any estimates on how complexity of quantum engineering scales with size?.

It is also possible that there exists a proof that NP $\ne$ QMA and that the engineering complexity scales linearly, meaning that quantum computers could "provably" have some advantage, but we just do not know of any such proof yet. Until we see a quantum computer give these "huge improvements" for a problem where it is provably better than the best classical algorithm, we have no way of being 100% certain that quantum computers will provide what you ask.

Quantum communication though (not necessarily quantum computing), does have some provable benefits over present day classical communication devices, and one example is the BB84 protocol.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Do you mean $\mathsf{NP \ne QMA}$, or do you perhaps mean $\mathsf{BPP \ne BQP}$? $\endgroup$
    – Niel de Beaudrap
    Sep 25, 2020 at 10:36
  • $\begingroup$ @NieldeBeaudrap Why do you ask that? $\endgroup$
    – user1271772
    Sep 26, 2020 at 5:59
  • $\begingroup$ If the question is whether quantum computers will provably bring an advantage, the more likely class of problems to consider is BQP (problems which polynomial-uniform quantum circuits can decide with bounded error) rather than QMA (yes/no problems for which candidate answers, possibly obtained by some completely other means, have proofs which can be tested by polynomial-uniform quantum circuits with bounded error). The comparison of QMA to NP is basically appropriate in this context (MA would be better), but QMA itself is unusual to invoke for 'quantum advantage'. $\endgroup$
    – Niel de Beaudrap
    Sep 26, 2020 at 10:20
  • $\begingroup$ @NieldeBeaudrap Would you agree that if QMA is bigger than NP, quantum computers have an advantage over classical computers? If so then there is no need to obscure things with complexity classes that no one's ever heard of. The person that asked, is a beginner, so they'll have heard of P vs NP, and QMA is a quantum analog of NP, and is probably more well-known by quantum researchers than BQP or BPP: I've heard chemists talk about QMA completeness and I've seen lots of people talk about QMA in the context of the k-local Hamiltonian problem, but can't remember the last time someone mentioned BQP $\endgroup$
    – user1271772
    Sep 27, 2020 at 1:24
  • $\begingroup$ Maybe you were trying to suggest that we can have: NP = QMA and BPP $\ne$ BQP? $\endgroup$
    – user1271772
    Sep 27, 2020 at 1:26
3
$\begingroup$

There is no absolute certainty. People introduce complexity classes: BPP for the set of problems that a classical computer (with access to a source of randomness) can solve in polynomial time, and BQP for the set of problems that a quantum computer can efficiently solve. We know that BQP contains BPP, but we do not know for certain that there are problems in BQP but not BPP. It is generally believed that there are some. Shor's algorithm for factoring large composite numbers is most typically hailed as a likely candidate, although the best candidate is the algorithm for the Jones polynomial because this problem is known to be the hardest that is efficiently solvable by a quantum computer. But we don't know. It may be that there is an efficient classical algorithm for this problem, and we just haven't been smart enough to find it yet.

What we do know is that with respect to certain oracles (i.e. black boxes that function in particular ways), quantum algorithms do outperform classical ones. You can think of this as "if we program an algorithm in a particular way, how fast can it run?". The advantage of these oracle-based algorithms is that lower bounds can be proven, showing the minimum number of operations required. The classic example of this is Simon's problem. Again, it doesn't mean that there can't be a better way of doing it classically via another route.

The other aspect that is implied by your question is whether a scalable universal quantum computer can actually be built. Until this is actually done, I don't think it can be proven, although it is generally believed that it will happen. There are, however, those who believe there are fundamental limitations that will prevent the construction of a suitable device. Gil Kalai, for example.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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