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

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

• @vzn: the circuit model has implementation in ion traps, which should soon be able to handle around 10 qubits. The Dwave machine does not implement the adiabatic model, but something called "quantum annealing", which currently is not known to yield even a conjectural speed-up for any problem. – Peter Shor Jun 21 '14 at 1:01
• @vzn: You could always look at this wikipedia article (linked from the article you linked to). Quantum adiabatic computation must stay in the ground state. Quantum annealing need not. From wikipedia: "If the rate of change [in a quantum annealing processor] of the transverse-field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian, i.e., adiabatic quantum computation." DWave recently stopped saying it was doing "quantum adiabatic computing", and started saying it was doing "quantum annealing". – Peter Shor Jun 21 '14 at 13:07
• @hadsed: I am fairly confident that DWave will implement a more versatile Hamiltonian soon, but that won't solve the problem they have that they are operating at a temperature above the energy gap. – Peter Shor Jun 24 '14 at 17:13
• @vzn could should or would? conjecture or prediction? can you ever make up your mind about words to use? – Sasho Nikolov Jun 24 '14 at 21:39
• @vzn: if you think that Feynman wouldn't consider it necessary/useful/good to do simulations, then you don't really understand Richard Feynman. Don't mistake a difference in attitude on his part towards what "knowledge" consists of, with intellectual laziness and a penchant for building castles in the sky. His was an inquisitive and demanding approach to science which is one to be emulated; if he did not concern himself much with mathematical proof in particular, that just indicates that he was not foremost a mathematician. (Nor, however, are you addressing the question as a mathematician!) – Niel de Beaudrap Jun 25 '14 at 8:40

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.

• nice answer, how are $BPP$ and $BQP$ related, i assume (from the answer) that $BPP \subseteq BQP$, yet bounds or conjectures for this? – Nikos M. Jun 24 '14 at 1:45
• "because there is some yet-unknown fundamental physical roadblock..." actually there are many known physical obstacles documented copiously by experimentalists, whether they or others unknown are serious roadblocks is an open question.... – vzn Jun 24 '14 at 20:29
• @Nikos: $\mathsf{BPP \subseteq BQP}$ is a simply proven containment of classes. To sketch: we may characterise $\mathsf{BPP}$ by deterministic (and reversible) computations acting on the input, some work bits prepared as 0s, and some random bits which are either 0 or 1 uniformly at random. In quantum computation, preparing the random bits may be simulated by suitable single-bit unitary transformations (albeit we call them 'qubits' when we allow such transformations). Thus we may easily show that $\mathsf{BPP \subseteq BQP}$, albeit we do not know whether this containment is strict. – Niel de Beaudrap Jun 25 '14 at 8:10
• @NieldeBeaudrap, thanks, why arent they equivalent? meaning $BQP \subseteq BPP$? i am missing sth here, isnt (also?) $BPP$ a class for all randomized computations? – Nikos M. Jun 25 '14 at 11:51
• @Nikos: no, $\mathsf{BPP}$ is not a class for all randomised computations. It has a particular mathematical definition which dictates what problems it contains, and it is not known to contain $\mathsf{BQP}$ or anything like it. For another example, $\mathsf {PP}$ is also a randomised class (where the answer only has to be correct with probability >1/2, albeit not by a significant margin) which contains $\mathsf{P \subseteq BPP \subseteq BQP \subseteq PP}$ and $\mathsf{NP \subseteq PP}$, where all containments are expected to be strict. – Niel de Beaudrap Jun 25 '14 at 12:11

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.

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).

• "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)." this is something of wishful thinking (that permeates the field) bordering on a non sequitur wrt prior sentence, "the debate about whether QM computers can be built in practice, or there are barriers etc". it is possible that scalable QM computers may not be physically realizable and no theoretical or experimental proof will be available, only reports of formidable obstacles (ie nearly the current status of the experimental field). – vzn Jun 26 '14 at 20:45

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.

• actually the speedup (e.g in Shor's algorithm) is based on the superposition principle of QM (which is slightly related to unitarity) – Nikos M. Jun 24 '14 at 1:49
• The "superposition principle" is mathematically equivalent to the statement that quantum distributions transform linearly. Probability vectors also transform linearly. More than "the superposition principle" would be required to explain any quantum / classical separation. – Niel de Beaudrap Jun 25 '14 at 8:02
• Incidentally: while I personally agree that unitarity (as opposed to, say, stochasticity) plays an important role in quantum computation, it is not clear that one can say that it is "the basic edifice" of the subject. Measurement-Based Quantum Computing and Adiabatic Quantum Computing as examples of models of QC where unitarity is put very much in the back seat, and where one would require a non-trivial argument to somehow squeeze unitarity back out, except inasmuch as we have tilted the playing field by describing "universal QC" in terms of the unitary circuit model. – Niel de Beaudrap Jun 25 '14 at 8:21
• @NieldeBeaudrap, indeed superposition stems from linearity. personally dont count on unitarity so much (but we'll see) – Nikos M. Jun 25 '14 at 11:57
• @Nikos: indeed, you can get much more (suspected) power if you consider arbitrary invertible linear operations. I'm just pointing out that superstitions/linearity in itself isn't powerful, because stochastic transformations are also linear, and also act on superpositions — but many researchers suspect $\mathsf {BPP = P}$ despite this. – Niel de Beaudrap Jun 25 '14 at 12:20

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.

• "In my view, all quantum speedups are due to entanglement." Your claim is really open to debate. The role of entanglement in quantum algorithms is not fully well-understood. We know that entanglement is not a sufficient resource to achieve an exponential quantum speed-up (there are maximally entangling quantum circuits, called Clifford circuits, that are classically simulable), showing that these are not equivalent concepts. – Juan Bermejo Vega Jul 27 '14 at 14:35
• Also, you might want to look at this paper, which shows that little entanglement is enough to do universal quantum computation (for continuous measures of entanglement). – Juan Bermejo Vega Jul 27 '14 at 14:38
• I just wanted to say that most interesting quantum algorithms use entanglement. How much it depends on the entanglement measure, and there are papers which argue that too much entanglement is useless. And, yes, entanglement by itself is not enough. – costelus Jul 30 '14 at 23:44

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:

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.

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.

• This doesn't answer the question as asked. – D.W. Jun 25 '14 at 0:30
• in short, the implicit premise that its purely a theoretical question is pushing the limits of applicability of theory vs reality to the point of being flawed... ie theres a modelling issue at the heart of it... do existing formalisms (crossing both TCS and physics!) actually/accurately capture the reality? Dyakonov for one might answer no... and new formalisms are actively being proposed by the minority faction... – vzn Jun 25 '14 at 1:55
• @vzn: with it understood that this could never yield a formal proof one way or the other, could you at least elaborate on how the theoretical component of the "fairly solid 2 decades of both theoretical and experimental research" is pointing towards results which are "not encouraging, lackluster, or are even now verging on a definitive negative answer" as respects the feasibility of quantum computing? – Niel de Beaudrap Jun 25 '14 at 12:46
• In view of Dyanokov's Axiom about precision and exact values, it's not clear that it is I who is delving into the philosophical! Dyanokov seems to be either a hardcore antirealist, a skeptic of quantum mechanics, or both. And it's unclear how those arguments re: precision address bounded-error quantum computation, where the threshold theorem also applies to bounded-precision quantum computation. In short, he doesn't seem up to date on the state of the art of quantum computing, from about 1997 onwards. Don't see much need for real-time interaction, to address skepticism that's not up to date. – Niel de Beaudrap Jun 25 '14 at 15:52
• Going from his abstract and a brief perusal of his paper, Dyakonov's argument seems to be: since the assumptions used in the proof of the fault-tolerance theorem fail are not satisfied the real world, there is no guarantee that quantum computing will actually work. If we used this criterion in general, almost no theoretical results would ever be applicable in practice. – Peter Shor Jun 26 '14 at 14:16