6
$\begingroup$

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

$\endgroup$
3
$\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.

$\endgroup$
1
$\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.

$\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.