Are quantum computers faster than classical computers?

2015-03-21

We do not know - not from the point of view of computational complexity, anyway.

The complexity class $$\textrm{BQP}$$ (bounded-error quantum polynomial-time) roughly corresponds to the problem that can be solved efficiently with a quantum computer, the same way as problems in $$\textrm{P}$$ can be solved efficiently with a classical computer. BQP is essentially the quantum version of $$\textrm{BPP}$$ (bounded-error probabilistic polynomial-time). For more precise description, see Scott Aaronson’s lecture notes or Wikipedia.

The question in the title corresponds to the question of whether $$\textrm{P}$$ is a strict subset of $$\textrm{BQP}$$. The following hierarchy is known:

$\textrm{P} \subseteq \textrm{BQP} \subseteq \textrm{PSPACE}$

The strictness of these relations is an open question. Proving that quantum computers are faster than classical computers would imply that $$\textrm{P} \subsetneq \textrm{PSPACE}$$, which would be a breakthrough result in classical complexity theory!

Of course, the existence of Shor’s algorithm and some other algorithms that are faster than their classical equivalents do support the idea that quantum computers are more powerful than classical computers. A proof of the contary result would be a surprise.

What about $$\textrm{NP}$$? We do not know much about the relationship between $$\textrm{BQP}$$ and $$\textrm{NP}$$. It is clear that, contrary to the popular culture description, quantum computers won’t allow us to magically solve NP-complete problems efficiently. Scott Aaronson writes in the lecture notes:

[A] quantum computer is not a device that could “try every possible solution in parallel” and then instantly pick the correct one. If we insist on seeing things in terms of parallel universes, then those universes all have to “collaborate” – more than that, have to meld into each other – to create an interference pattern that will lead to the correct answer being observed with high probability.

Comments or questions? Tweet to me or send me an e-mail.