Is there a formal proof that quantum computing is or will be faster than classical computing?

Question

Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?

Answer 1

This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural.

The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\mathsf{BPP}$ (for randomized). The quantum counterpart of these classes is $\mathsf{BQP}$. All three classes are subsets of $\mathsf{PSPACE}$ (a very powerful class). However, our current methods of proof are not strong enough to definitively show that $\mathsf{P}$ is not the same thing as $\mathsf{PSPACE}$. Thus, we do not know how to formally separate $\mathsf{P}$ from $\mathsf{BQP}$ either — since $\mathsf{P \subseteq BQP \subseteq PSPACE}$, separating those two classes is harder than the already formidable task of separating $\mathsf{P}$ from $\mathsf{PSPACE}$. (If we could prove $\mathsf{P \ne BQP}$, we would immediately obtain a proof that $\mathsf{P \ne PSPACE}$, so proving $\mathsf{P \ne BQP}$ has to be at least as hard as the already-very-hard problem of proving $\mathsf{P \ne PSPACE}$). For this reason, within the current state of the art, it is difficult to obtain a rigorous mathematical proof showing that quantum computing will be faster than classical computing.

Thus, we usually rely on circumstantial evidence for complexity class separations. Our strongest and most famous evidence is Shor's algorithm that it allows us to factor in $\mathsf{BQP}$. In contrast, we do not know of any algorithm that can factor in $\mathsf{BPP}$ — and most people believe one doesn't exist; that is part of the reason why we use RSA for encryption, for instance. Roughly speaking, this implies that it is possible for a quantum computer to factor efficiently, but suggests that it may not be possible for a classical computer to factor efficiently. For these reasons, Shor's result has suggested to many that $\mathsf{BQP}$ is strictly more powerful than $\mathsf{BPP}$ (and thus also more powerful than $\mathsf{P}$).

I don't know of any serious arguments that $\mathsf{BQP = P}$, except from those people that believe in much bigger complexity class collapses (which are a minority of the community). The most serious arguments I have heard against quantum computing come from stances closer to the physics and argue that $\mathsf{BQP}$ does not correctly capture the nature of quantum computing. These arguments typically say that macroscopic coherent states are impossible to maintain and control (e.g., because there is some yet-unknown fundamental physical roadblock), and thus the operators that $\mathsf{BQP}$ relies on cannot be realized (even in principle) in our world.

If we start to move to other models of computation, then a particularly easy model to work with is quantum query complexity (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can prove that (for some problems) quantum algorithms can achieve a quadratic speedup, although we can also show that for total functions we cannot do better than a power-6 speed up and believe that quadratic is the best possible. For partial functions, it is a totally different story, and we can prove that exponential speed ups are achievable. Again, these arguments rely on a belief that we have a decent understanding of quantum mechanics and there isn't some magical unknown theoretical barrier to stopping macroscopic quantum states from being controlled.

Answer 2

For computational complexity, there is no proof that quantum computers are better than classical computers because of how hard it is to obtain lower-bounds on the hardness of problems. However, there are settings in which a quantum computer provably does better than a classical one. The most famous of these examples is in the blackbox model in which you have access via blackbox to a function $f:\{0,1\}^n\mapsto \{0,1\}$ and you want to find the unique $x$ for which $f$ evaluates to 1. The complexity measure in this case is the number of calls to $f$. Classicaly, you cannot do better than guessing $x$ at random which takes on average $\Omega(2^n)$ queries to $f$. However, using Grover's algorithm you can achieve the same task in $O(\sqrt{2^n})$.

For further provable separations, you can look into communication complexity where we know how to prove lower bounds. There are tasks that two quantum computers communicating through a quantum channel can accomplish with less communication than two classical computers. For example computing the inner product of two strings, one of the hardest problems in communication complexity, has a speedup when using quantum computers.

Answer 3

Artem Kaznatcheev provides an outstanding summary of some key reasons why we expect quantum computers will be fundamentally faster than classical computers, for some tasks.

If you'd like some additional reading, you can read Scott Aaronson's lecture notes on quantum computing, which discuss the Shor algorithm and other algorithms that admit efficient quantum algorithms but do not seem to admit any efficient classical algorithm.

There is a debate about whether quantum computers can be built in practice: is BQP an accurate model of reality, or is there something that might prevent us from building a quantum computer, either for engineering reasons or because of fundamental physical barriers? You can read Scott Aaronson's lecture notes summarizing the arguments others have raised and also read his blog post with his view on that debate, but we probably won't have a definitive answer until someone actually builds a quantum computer that can do non-trivial tasks (such as factor large numbers).

Answer 4

The basic edifice of quantum computing is the Unitary transform, this is the primary tool for having speedup in many algortithms in the literature. Algorithms that use Unitaries use number/graph theoretic properties of problems at hand - period finding, speed ups in quantum walks, etc. Speedups in natural problems are still elusive - as pointed out. Whether factoring large numbers is the end in itself for quantum computing, is still an open question. Other open questions such QNC, its seperation from NC could still provide elusive clues about what quantum computers may do. But, if the goal of quantum computer is to factor large numbers - it may yet be feasible, in itself in some future, with scary implications (of course to personal privacy)! Whether the unitary binds the model of computation in some way or a new paradigm of physical reality is needed - is anybodies guess.

Answer 5

I wanted to respond to the comments of Niel de Beaudrap regarding the source for quantum speedups, but I can't comment. I don't know if I can post an answer.

In my view, all quantum speedups are due to entanglement. The only algorithm where we can do something faster than classical computers without using entangled states is Deutsch-Jozsa for computing the parity of two bits. If we discuss about asymptotic speed-ups, entanglement is necessary, and in fact a lot of it. If a quantum algorithm needs a small amount of entanglement, it can be simulated efficiently classically. I can point out the paper http://arxiv.org/abs/quant-ph/0201143, which discusses specifically the factoring algorithm and how much entanglement it requires.

Answer 6

this is nearly the same core question that is driving something like hundreds of millions, or possibly billions of dollars of QM computing research initiatives both public and private worldwide. the question is being attacked at the same time both experimentally and theoretically and advances on each side carry over to the other side.

the question does attempt to neatly separate the theoretical and pragmatic/ experimental aspects of this question, but an experimentalist or engineer would argue they are tightly coupled, inseparable, and that historical progress so far on the challenge is evidence/ proof of that.

the following point is certainly not going to win any popularity contests (possibly due somewhat to the well-known/ observed bias that negative results are rarely reported scientifically), but it is worth noting that there is a minority/contrarian opinion promoted by various credible, even elite researchers that QM computing may or will never materialize physically due to insurmountable implementation challenges, and there is even some theoretical justification/analysis for this (but maybe more from theoretical physics than TCS). (and note that some may have doubts but are not willing to go on record questioning the "dominant paradigm".) the main arguments are based on inherent QM noisiness, the Heisenberg uncertainty principle, and the fundamental experimental messiness of QM setups, etc.

there are now a fairly solid 2 decades of both theoretical and experimental research and the minority faction would argue that the results so far are not encouraging, lackluster, or are even now verging on a definitive negative answer.

one of the most outspoken proponents of the negative view (bordering on extreme/ scathing!) is Dyakonov but who nevertheless argues the case passionately based on all the angles:

• State of the Art and Prospects for Quantum Computing / Dyakonov

• Prospects for quantum computing: extremely doubtful / Dyakonov

one may accuse Dyakonov of near polemicism but it serves as a nearly symmetric counterpoint to some QM computing proponents who have a fervent belief in the opposing position (that there is nearly absolutely no question of its future/eventual/inevitable viability). another major theoretician arguing for inherent limitations in QM computing (based on noise) is Kalai. here is an extended debate between him and Harrow on the subject.

• Perpetual Motion of The 21st Century?

it is also natural to draw some at least loose analogy to another massive/complex physics project that so far has not achieved its ultimate goal after decades of attempts and optimistic early predictions, that of energy-generating fusion experiments.