<p>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 <a href="http://en.wikipedia.org/wiki/Grover%27s_algorithm">Grover's algorithm</a> you can achieve the same task in $O(\sqrt{2^n})$.</p>

<p>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 <a href="http://arxiv.org/pdf/quant-ph/9708019v3.pdf">computing the inner product</a> of two strings, one of the hardest problems in communication complexity, has a speedup when using quantum computers.</p>

CC BY-SA 3.0
2014-06-25T15:49:13.977Z
2014-06-25T15:49:13.977Z
lamontap
<p>Artem Kaznatcheev provides an <a href="https://cstheory.stackexchange.com/a/24952/5038">outstanding summary</a> of some key reasons why we expect quantum computers will be fundamentally faster than classical computers, for some tasks.</p>

<p>If you'd like some additional reading, you can read Scott Aaronson's <a href="http://www.scottaaronson.com/democritus/lec10.html" rel="nofollow noreferrer">lecture notes on quantum computing</a>, which discuss the Shor algorithm and other algorithms that admit efficient quantum algorithms but do not seem to admit any efficient classical algorithm.</p>

<p>There <em>is</em> 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 <a href="http://www.scottaaronson.com/democritus/lec14.html" rel="nofollow noreferrer">lecture notes summarizing the arguments others have raised</a> and also read his <a href="http://www.scottaaronson.com/blog/?p=124" rel="nofollow noreferrer">blog post with his view on that debate</a>, 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).</p>

CC BY-SA 3.0
2014-06-26T20:45:48.193Z
"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
CC BY-SA 3.0
2014-06-20T20:31:25.707Z
2014-06-20T20:31:25.707Z
2017-04-13T12:32:28.167Z
D.W.
<p>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.</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/0201143" rel="nofollow">http://arxiv.org/abs/quant-ph/0201143</a>, which discusses specifically the factoring algorithm and how much entanglement it requires.</p>

CC BY-SA 3.0
2014-07-27T14:35:58.760Z
"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](http://arxiv.org/abs/quant-ph/9807006), that are classically simulable), showing that these are not equivalent concepts.
Juan Bermejo Vega
CC BY-SA 3.0
2014-07-27T14:38:36.357Z
Also, you might want to look at [this paper](http://arxiv.org/abs/1204.3107), which shows that little entanglement is enough to do universal quantum computation (for continuous measures of entanglement).
Juan Bermejo Vega
CC BY-SA 3.0
2014-07-30T23:44:44.533Z
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
CC BY-SA 3.0
2014-07-26T17:48:02.253Z
2014-07-26T17:48:02.253Z
costelus
<p>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.  </p>

CC BY-SA 3.0
2014-06-24T01:49:28.547Z
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.
CC BY-SA 3.0
2014-06-25T08:02:22.673Z
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
CC BY-SA 3.0
2014-06-25T08:21:01.917Z
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
CC BY-SA 3.0
2014-06-25T11:57:33.060Z
@NieldeBeaudrap, indeed superposition stems from linearity. personally dont count on unitarity so much (but we'll see)
Nikos M.
CC BY-SA 3.0
2014-06-25T12:20:56.523Z
@Nikos: indeed, you can get [much more  (suspected) power if you consider arbitrary invertible linear operations](http://arxiv.org/abs/quant-ph/0412187). 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
CC BY-SA 3.0
2014-06-25T19:27:52.520Z
@NieldeBeaudrap, ahh, nice ref (plus elucidates further the answer on the other comment about $BPP$, $BQP$, $PP$)
Nikos M.
CC BY-SA 3.0
2014-06-20T21:05:23.587Z
2014-06-20T21:11:07.297Z
2014-06-20T21:11:07.297Z
user3046538
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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:</p>

<ul>
<li><p><a href="http://arxiv.org/ftp/arxiv/papers/1212/1212.3562.pdf" rel="nofollow">State of the Art and Prospects for Quantum Computing</a> / Dyakonov</p></li>
<li><p><a href="http://arxiv.org/abs/1401.3629" rel="nofollow">Prospects for quantum computing: extremely doubtful</a> / Dyakonov</p></li>
</ul>

<p>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.</p>

<ul>
<li><a href="http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/" rel="nofollow">Perpetual Motion of The 21st Century?</a></li>
</ul>

<p>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 <a href="http://en.wikipedia.org/wiki/List_of_fusion_experiments" rel="nofollow">energy-generating fusion experiments</a>.</p>

CC BY-SA 3.0
2014-06-25T00:30:32.813Z
This doesn't answer the question as asked.
D.W.
CC BY-SA 3.0
2014-06-25T01:55:52.970Z
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
CC BY-SA 3.0
2014-06-25T08:31:40.827Z
vzn: Could you envision a similar argument about the limits of applicability of theory versus reality, applied to nondeterministic Turing machines? Is the OP not analogous to asking "Is there a formal proof that **NP** is more powerful than **P**?" and if not, then how does this question differ from the one I imagine?
Niel de Beaudrap
CC BY-SA 3.0
2014-06-25T12:02:01.623Z
+1, personally i like it (maybe others dont), maybe it could be a comment (instead of answer), but being long enough for a comment, i like the links
Nikos M.
CC BY-SA 3.0
2014-06-25T12:46:42.130Z
@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
CC BY-SA 3.0
2014-06-25T15:18:30.467Z
@Niel "playing devils advocate", do not nec agree with all opinions expressed! am not asserting the question about qm speedup will _never_ be answered, am only saying it is not answerable now, and it may be due to incompleteness in the _existing/known_ formalisms. since you raise it, notice how similar the question is to Church-Turing "P-time" _thesis_ (that abstract TMs model all possible physical computation also with accurate timing)! agreed there are similarities to P vs NP. even bell experiments (from 1980s) can be regarded as QM-computing (qubit) like setups. shor 1994 is a milestone.
vzn
CC BY-SA 3.0
2014-06-25T15:27:02.567Z
@vzn: I'm not defending the proposition that quantum computers should be faster. When you say to D.W. that the implicit premise "is pushing the limits of applicability of theory vs reality to the point of being flawed", I wonder what exactly you mean, and why the same criticism couldn't be levelled at nondeterministic Turing machines. Quantum computation is a problem in engineering, *but it is also a topic in the theory of computation*, and in the latter case it is entirely a theoretical topic about a model of computation which we (as a separate concern) hope to physically emulate.
Niel de Beaudrap
CC BY-SA 3.0
2014-06-25T15:33:58.477Z
@niel as facebook says about some relationships, "its complicated", appreciate your interest in the nuances which verge on philosophical, lets carry further discussion to [chat]. you might start by actually reading dyakonov. :\ ... actually scotts _blog page_ cited by D.W. "this doesnt answer the question" cites dyakonov also and summarizes all the arguments well (ofc from his particular "believer lens/pov"). its simply worth noting there are contrarians/nonbelievers (labelled "skeptics" by the believers), and the debate can be carried out endlessly at this time....
vzn
CC BY-SA 3.0
2014-06-25T15:52:45.710Z
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
CC BY-SA 3.0
2014-06-25T16:00:12.893Z
_Dyakonov_ has excellent credentials, surveys the field in a _tour-de-force,_ & the last ref is _highly_ up to date at 2014, and ofc feel free to ignore it all. _"your mileage may vary"_ **:)** & ps @nikos _aka "outcast"_ thx much for the vote & currently saving this answer from negative total pts! **=D**
vzn
CC BY-SA 3.0
2014-06-26T14:16:18.377Z
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 
CC BY-SA 3.0
2014-06-26T14:58:13.537Z
@Peter a lot of QM computing viability apparently hinges on fault tolerance/correction algorithms in QM which there is a large theoretical edifice built up that is mostly/largely empirically/experimentally untested & Dyakonov is not the only one to zoom in on it. there are other examples of large theoretical physics theories that are questioned by significant minorities of expert physicists partly based on lack of physical evidence/testing/falsifiability eg supersymmetry or string theory.... even strong proponents of QM computing might agree _there is no guarantee it will actually work_....
vzn
CC BY-SA 3.0
2014-06-24T20:57:44.030Z
2014-06-24T20:57:44.030Z
vzn
<p>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.</p>

<p>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 &mdash; 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.</p>

<p>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}$ &mdash; 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}$).</p>

<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.</p>

<p>If we start to move to other models of computation, then a particularly easy model to work with is <a href="http://egtheory.wordpress.com/2013/12/09/quantum-query-complexity/" rel="nofollow noreferrer">quantum query complexity</a> (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can <em>prove</em> 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 <a href="https://cstheory.stackexchange.com/q/6077/1037">believe that quadratic is the best possible</a>. 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.</p>

CC BY-SA 3.0
2014-06-24T01:45:34.797Z
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.
CC BY-SA 3.0
2014-06-24T20:29:52.883Z
"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
CC BY-SA 3.0
2014-06-25T08:10:52.987Z
@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
CC BY-SA 3.0
2014-06-25T11:51:38.513Z
@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.
CC BY-SA 3.0
2014-06-25T12:11:39.273Z
@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
CC BY-SA 3.0
2014-06-20T18:32:23.210Z
2014-06-25T08:15:54.060Z
2017-04-13T12:32:28.080Z
Artem Kaznatcheev
<p>Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?</p>

CC BY-SA 3.0
2014-06-20T23:18:17.920Z
seems to be largely still an open question. this can be broken down into two major models. the circuit model which has no physical implementations yet, and the [adiabatic model](http://cstheory.stackexchange.com/questions/16974/is-adiabatic-quantum-computing-as-powerful-as-the-circuit-model) which is utilized by [Dwave](http://en.wikipedia.org/wiki/D-Wave_Systems). circumstantial evidence is [Shors algorithm](http://en.wikipedia.org/wiki/Shors_algorithm) which has no known classical counterpart.
vzn
CC BY-SA 3.0
2014-06-21T01:01:30.390Z
@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 
CC BY-SA 3.0
2014-06-21T01:09:06.043Z
ok. there are some ~10 qubit entanglement setups but technology for separating/matching arbitrary qubits (pairs) of a set via manipulation (as reqd for arbitrary circuits) seems very rudimentary right now. as for "conjectural", anything can be conjectured... DWave/wikipedia states they have a "superconducting adiabatic quantum optimizing processor", maybe you are aware of some ref that contests that claim and asserts it is not & delineates a technical difference between that & "quantum annealing"?
vzn
CC BY-SA 3.0
2014-06-21T13:07:34.783Z
@vzn:  
You could always look at this [wikipedia article](http://en.wikipedia.org/wiki/Quantum_annealing) (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 
CC BY-SA 3.0
2014-06-24T17:08:01.300Z
@PeterShor It sounds like you're making a distinction between AQC and QA as the former being theoretical and the latter the practical implementation. My impression is that DW implements an Ising Hamiltonian that isn't universal (Biamonte, 2008?), and for that reason they call it QA instead. I could certainly be wrong about that.
hadsed
CC BY-SA 3.0
2014-06-24T17:13:17.497Z
@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 
CC BY-SA 3.0
2014-06-24T17:51:31.970Z
@PeterShor I think the universality condition comes in with adiabatic quantum computing vs. adiabatic quantum optimization, so that was my mistake.
hadsed
CC BY-SA 3.0
2014-06-24T20:24:27.630Z
fyi researching something like this awhile back, re this general question, actually the _intuition/ conjecture/ prediction_ that QM computers could/should/would run faster than classical ones at least on certain types of calculations, eg/namely [QM mechanical formulas,](http://cstheory.stackexchange.com/questions/10368/what-is-the-proof-that-quantum-computers-can-efficiently-simulate-arbitrary-quan) goes back to the origins of QM computing with Feynman, the _physicist_, who apparently took it as self-evident... (maybe in the sense in that case simulations were unnecessary?).
vzn
CC BY-SA 3.0
2014-06-24T21:39:22.780Z
@vzn could should or would? conjecture or prediction? can you ever make up your mind about words to use?
Sasho Nikolov
CC BY-SA 3.0
2014-06-25T01:52:49.333Z
the words blur together & cannot be differentiated by solid theory/science ... "yet". thats the point, its interchangeable poetry so far & one should not attempt to make the indefinite definite based on cognitive bias & human (esp researcher) tendency to do so :| ie in short _we dont know_ ... there is _some_ good news in that _most_ or _much_ of the question is apparently captured with formal complexity class defns as summarized in AKs answer...
vzn
CC BY-SA 3.0
2014-06-25T08:40:15.377Z
@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
CC BY-SA 3.0
2014-06-26T20:56:40.237Z
NdB you misread my comments & put words in my mouth. and you do understand Feynman? feynman was singularly brilliant. nevertheless he died 6 years before shor's algorithm was discovered. the qm computing field owes him an early debt but has expanded in many ways he couldnt have envisioned. he did not seem to consider/analyze general purpose (qm) computing much and even admitted this at times eg wrt working with hillis on connectionism/parallelism. he sketched out the basic ideas of qm machines. ofc no one who knows anything about feynman would ever accuse him of "intellectual laziness"...
vzn
CC BY-SA 4.0
2022-03-02T14:26:34.613Z
It might be worth noting, that in a recent related result Bravyi, Gosset, and König (https://arxiv.org/abs/1704.00690) show unconditionally that constant-time parallel quantum algorithms are more powerful than their classical probabilistic counterparts.
Martin Schwarz
<quantum-computing>
Is there a formal proof that quantum computing is or will be faster than classical computing?
Alex Moore-Niemi
# Is there a formal proof that quantum computing is or will be faster than classical computing?

(Asked by: username_0 on 2014-06-20)

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

**Tags:** quantum-computing

> **Comments:**
> **username_1**: seems to be largely still an open question. this can be broken down into two major models. the circuit model which has no physical implementations yet, and the [adiabatic model](http://cstheory.stackexchange.com/questions/16974/is-adiabatic-quantum-computing-as-powerful-as-the-circuit-model) which is utilized by [Dwave](http://en.wikipedia.org/wiki/D-Wave_Systems). circumstantial evidence is [Shors algorithm](http://en.wikipedia.org/wiki/Shors_algorithm) which has no known classical counterpart.  
> **username_2**: @username_1: 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.  
> **username_1**: ok. there are some ~10 qubit entanglement setups but technology for separating/matching arbitrary qubits (pairs) of a set via manipulation (as reqd for arbitrary circuits) seems very rudimentary right now. as for "conjectural", anything can be conjectured... DWave/wikipedia states they have a "superconducting adiabatic quantum optimizing processor", maybe you are aware of some ref that contests that claim and asserts it is not & delineates a technical difference between that & "quantum annealing"?  
> **username_2**: @username_1:   You could always look at this [wikipedia article](http://en.wikipedia.org/wiki/Quantum_annealing) (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".  
> **username_3**: @PeterShor It sounds like you're making a distinction between AQC and QA as the former being theoretical and the latter the practical implementation. My impression is that DW implements an Ising Hamiltonian that isn't universal (Biamonte, 2008?), and for that reason they call it QA instead. I could certainly be wrong about that.  
> **username_2**: @username_3: 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.  
> **username_3**: @PeterShor I think the universality condition comes in with adiabatic quantum computing vs. adiabatic quantum optimization, so that was my mistake.  
> **username_1**: fyi researching something like this awhile back, re this general question, actually the _intuition/ conjecture/ prediction_ that QM computers could/should/would run faster than classical ones at least on certain types of calculations, eg/namely [QM mechanical formulas,](http://cstheory.stackexchange.com/questions/10368/what-is-the-proof-that-quantum-computers-can-efficiently-simulate-arbitrary-quan) goes back to the origins of QM computing with Feynman, the _physicist_, who apparently took it as self-evident... (maybe in the sense in that case simulations were unnecessary?).  
> **username_4**: @username_1 could should or would? conjecture or prediction? can you ever make up your mind about words to use?  
> **username_1**: the words blur together & cannot be differentiated by solid theory/science ... "yet". thats the point, its interchangeable poetry so far & one should not attempt to make the indefinite definite based on cognitive bias & human (esp researcher) tendency to do so :| ie in short _we dont know_ ... there is _some_ good news in that _most_ or _much_ of the question is apparently captured with formal complexity class defns as summarized in AKs answer...  
> **username_5**: @username_1: 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!)  
> **username_1**: NdB you misread my comments & put words in my mouth. and you do understand Feynman? feynman was singularly brilliant. nevertheless he died 6 years before shor's algorithm was discovered. the qm computing field owes him an early debt but has expanded in many ways he couldnt have envisioned. he did not seem to consider/analyze general purpose (qm) computing much and even admitted this at times eg wrt working with hillis on connectionism/parallelism. he sketched out the basic ideas of qm machines. ofc no one who knows anything about feynman would ever accuse him of "intellectual laziness"...  
> **username_6**: It might be worth noting, that in a recent related result Bravyi, Gosset, and König (https://arxiv.org/abs/1704.00690) show unconditionally that constant-time parallel quantum algorithms are more powerful than their classical probabilistic counterparts.  

---

## 6 answers

### Answer by username_13 on 2014-06-20. Score: 24 | Accepted answer

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](http://egtheory.wordpress.com/2013/12/09/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](https://cstheory.stackexchange.com/q/6077/1037). 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.

> **Comments:**
> **username_12**: nice answer, how are $BPP$ and $BQP$ related, i assume (from the answer) that $BPP \subseteq BQP$, yet bounds or conjectures for this?  
> **username_1**: "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....  
> **username_5**: @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.  
> **username_12**: @NieldeBeaudrap, thanks, why arent they equivalent? meaning $BQP \subseteq BPP$? i am missing sth here, isnt (also?) $BPP$ a class for **all** randomized computations?  
> **username_5**: @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.  

---

### Answer by username_7 on 2014-06-25. Score: 8

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](http://en.wikipedia.org/wiki/Grover%27s_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](http://arxiv.org/pdf/quant-ph/9708019v3.pdf) of two strings, one of the hardest problems in communication complexity, has a speedup when using quantum computers.


---

### Answer by username_8 on 2014-06-20. Score: 4

username_13 provides an [outstanding summary](https://cstheory.stackexchange.com/a/24952/5038) 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](http://www.scottaaronson.com/democritus/lec10.html), 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](http://www.scottaaronson.com/democritus/lec14.html) and also read his [blog post with his view on that debate](http://www.scottaaronson.com/blog/?p=124), 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).

> **Comments:**
> **username_1**: "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).  

---

### Answer by username_9 on 2014-07-26. Score: -2

I wanted to respond to the comments of username_5 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.

> **Comments:**
> **username_10**: "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](http://arxiv.org/abs/quant-ph/9807006), that are classically simulable), showing that these are not equivalent concepts.  
> **username_10**: Also, you might want to look at [this paper](http://arxiv.org/abs/1204.3107), which shows that little entanglement is enough to do universal quantum computation (for continuous measures of entanglement).  
> **username_9**: 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.  

---

### Answer by username_11 on 2014-06-20. Score: -2

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.

> **Comments:**
> **username_12**: actually the speedup (e.g in Shor's algorithm) is based on the superposition principle of QM (which is *slightly related* to unitarity)  
> **username_5**: 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.  
> **username_5**: 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.  
> **username_12**: @NieldeBeaudrap, indeed superposition stems from linearity. personally dont count on unitarity so much (but we'll see)  
> **username_5**: @Nikos: indeed, you can get [much more  (suspected) power if you consider arbitrary invertible linear operations](http://arxiv.org/abs/quant-ph/0412187). 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.  
> **username_12**: @NieldeBeaudrap, ahh, nice ref (plus elucidates further the answer on the other comment about $BPP$, $BQP$, $PP$)  

---

### Answer by username_1 on 2014-06-24. Score: -4

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](http://arxiv.org/ftp/arxiv/papers/1212/1212.3562.pdf) / Dyakonov
* [Prospects for quantum computing: extremely doubtful](http://arxiv.org/abs/1401.3629) / 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?](http://rjlipton.wordpress.com/2012/01/30/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](http://en.wikipedia.org/wiki/List_of_fusion_experiments).

> **Comments:**
> **username_8**: This doesn't answer the question as asked.  
> **username_1**: 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...  
> **username_5**: username_1: Could you envision a similar argument about the limits of applicability of theory versus reality, applied to nondeterministic Turing machines? Is the OP not analogous to asking "Is there a formal proof that **NP** is more powerful than **P**?" and if not, then how does this question differ from the one I imagine?  
> **username_12**: +1, personally i like it (maybe others dont), maybe it could be a comment (instead of answer), but being long enough for a comment, i like the links  
> **username_5**: @username_1: 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?  
> **username_1**: @Niel "playing devils advocate", do not nec agree with all opinions expressed! am not asserting the question about qm speedup will _never_ be answered, am only saying it is not answerable now, and it may be due to incompleteness in the _existing/known_ formalisms. since you raise it, notice how similar the question is to Church-Turing "P-time" _thesis_ (that abstract TMs model all possible physical computation also with accurate timing)! agreed there are similarities to P vs NP. even bell experiments (from 1980s) can be regarded as QM-computing (qubit) like setups. shor 1994 is a milestone.  
> **username_5**: @username_1: I'm not defending the proposition that quantum computers should be faster. When you say to username_8 that the implicit premise "is pushing the limits of applicability of theory vs reality to the point of being flawed", I wonder what exactly you mean, and why the same criticism couldn't be levelled at nondeterministic Turing machines. Quantum computation is a problem in engineering, *but it is also a topic in the theory of computation*, and in the latter case it is entirely a theoretical topic about a model of computation which we (as a separate concern) hope to physically emulate.  
> **username_1**: @niel as facebook says about some relationships, "its complicated", appreciate your interest in the nuances which verge on philosophical, lets carry further discussion to [chat]. you might start by actually reading dyakonov. :\ ... actually scotts _blog page_ cited by username_8 "this doesnt answer the question" cites dyakonov also and summarizes all the arguments well (ofc from his particular "believer lens/pov"). its simply worth noting there are contrarians/nonbelievers (labelled "skeptics" by the believers), and the debate can be carried out endlessly at this time....  
> **username_5**: 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.  
> **username_1**: _Dyakonov_ has excellent credentials, surveys the field in a _tour-de-force,_ & the last ref is _highly_ up to date at 2014, and ofc feel free to ignore it all. _"your mileage may vary"_ **:)** & ps @nikos _aka "outcast"_ thx much for the vote & currently saving this answer from negative total pts! **=D**  
> **username_2**: 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.***  
> **username_1**: @Peter a lot of QM computing viability apparently hinges on fault tolerance/correction algorithms in QM which there is a large theoretical edifice built up that is mostly/largely empirically/experimentally untested & Dyakonov is not the only one to zoom in on it. there are other examples of large theoretical physics theories that are questioned by significant minorities of expert physicists partly based on lack of physical evidence/testing/falsifiability eg supersymmetry or string theory.... even strong proponents of QM computing might agree _there is no guarantee it will actually work_....  

---

