I would like to know if there are some specific class of quantum algorithms, under some hypotheses about the noise model behind the quantum gates for which we know that there is an exponential advantage in the presence of noise.

What I mean by that is that even if we assume that quantum gates are noisy, because of some "features" the unitary has, or because the noise has some specific properties (it is biased for instance), we can show that when we increase the problem size the quantum algorithm will keep having an exponential advantage over the best known classical algorithm dedicated to solve the same task?

To be precise, the classical algorithm will require $\exp(Poly_1(n))$ operations while the quantum algorithm $Poly_2(n)$ operations where $Poly_1(n)$ and $Poly_2(n)$ are some polynomes in $n$ ($n$ describes the problem size).

  • $\begingroup$ Let me start with the simpler question: in the absence of noise, are there some specific (non-oracle-based) quantum algorithms for which we know there is an exponential advantage over classical? $\endgroup$
    – DaftWullie
    Apr 13, 2022 at 7:03
  • $\begingroup$ @DaftWullie I don't know what you mean by non-oracle-based but there is Shor algorithm which provides an exponential advantage over the best-known classical algorithm. So the answer is yes for sure. If you are asking if there is a proof that we will never find one day a classical algorithm that outperforms Shor however there is not and this is an open question. $\endgroup$ Apr 13, 2022 at 9:12
  • 1
    $\begingroup$ That's not immediately clear. For instance, there is the paper arxiv.org/abs/1704.00690 by Bravyi, Gosset, and Koenig that indicates that constant-depth quantum circuits might have an advantage over classical circuits. The constructed quantum circuits are deterministic, so if the noise is not too strong, this might still hold. $\endgroup$ Apr 25, 2022 at 7:21
  • $\begingroup$ @MarkusHeinrich Correct, thanks for the ref. I have heard about this paper and I have to read it more carefully =). $\endgroup$ Apr 25, 2022 at 9:07

2 Answers 2


A photon based quantum computer named Jiuzhang in 2020 performed gaussian boson sampling (GBS) (Link to paper) of 76 photons.Researchers are interested in quantum algorithm for Boson sampling using photons. Jiuzhang obtained it in 200 seconds without error correction applied;that would take a classical computer 2.5 billion years. Creating a output state space dimension of ~$10^{30}$. Although it isn't universal but proven a significant magnitute of advantage over classical methods. Unlike Shor’s algorithm where its solution can be efficiently verified; for the GBS, a full certification of the outcome is strongly conjectured to be intractable for classical computation.Setup for Gaussian boson sampling. This "Gaussian boson sampling for quantum computational advantage" video has discussed it in detail. Jiuzhang 2.0 in October 2021 did it for 113 photons with a output state space of $10^{43}$. As far as scaling goes this is what researchers have to say on there paper for Jiuzhang 2.0 on page 6(Link to 2.0 paper).

enter image description here

  • 1
    $\begingroup$ Thank you very much, this is very interesting. I still have a question though. Do you know if there is a proof that this approach would, in the algorithmic sense, keep an exponential advantage? Because maybe the reason why it works here is just because of the specific protocol + the fact photons have low noise + the fact the problem is not "too large". Maybe for some "larger problem" the advantage would break down (because the noise on the photons would "badly accumulate"). This is the main question I am interested to find an answer to. $\endgroup$ Apr 26, 2022 at 15:37
  • 2
    $\begingroup$ The main challenge for scaling up photonic quantum technologies is the lack of perfect quantum light sources. As photonic quantum computer work at room temperature except the detectors(they are at superconducting temperature). There needs to be error correction applied to the detectors for readouts. But the exponential advantage will remain in this case as for photons >40 ; this problem is intractable for classical computers. Also I made a correction in my answer take a look ; it was 1.0 that did it for 76 and 2.0 did it for for 113 . $\endgroup$ Apr 27, 2022 at 11:52
  • $\begingroup$ Thanks! I see what you mean but I am using the term exponential advantage in the mathematical sense. This result is very strong in practice but on a conceptual level I am not sure that it shows that you keep having an exponential advantage in presence of noise. It could be that for a billion of photons, the noise would be too large and one would have to repeat too many times the experiment such that a classical computer would be faster to solve the task. Of course, the classical computer might still take an insane amount of time to solve it (eventually more than billion of years). $\endgroup$ Apr 28, 2022 at 16:37
  • $\begingroup$ But I am interested in the conceptual question rather than the practical aspect in my question. $\endgroup$ Apr 28, 2022 at 16:37

This kind of asymptotic advantage strikes me as obviously impossible, or maybe even ill-defined, because without error correction the quantum computer can only do O(1) gates before your signal is swamped by noise. I think if you found a solution that avoided this problem, it would just secretly be a form of error correction.

This limitation also applies to classical computers. It's just that the in-practice O(1) breakdown size is many orders of magnitude larger; I estimate somewhere around $10^{18}$ operations (whereas quantum is currently somewhere around $10^{3}$).

This doesn't prove there are not intermediate cases where an un-error-corrected quantum computer is a benefit. It just implies you can always make things big enough that it fails. You need a scalable strategy for dealing with noise to maintain asymptotic advantages.

  • $\begingroup$ Hello, thanks for your answer. While I agree that for a general algorithm it is impossible, for me it doesn't exclude the fact it could work for some specific structures. I have in mind two examples: in some algorithms randomness can be used as a tool (in classical monte Carlo technique you use it to avoid being trapped in local minima when you are trying to find the minimum of some Hamiltonians). It could be that quantum noise could (if it follows some specific features) be a "friend" that plays this role of helping you for instance. $\endgroup$ Apr 25, 2022 at 9:04
  • $\begingroup$ Another thing I am thinking of is that for some algorithms you only measure a tiny portion of all your qubits. If your circuit and the noise have nice properties it could be that the noise would not impact too much those specific qubits. Of course, those are just vague intuitions, maybe it is impossible but I don't see why we couldn't find some specific examples in which you can scale with noise. Those were the motivations behind my question. $\endgroup$ Apr 25, 2022 at 9:17
  • $\begingroup$ @StarBucK I have no proof that it's impossible, and yes maybe there are some sideways attacks that get to it. But my intuition is that those ideas will have non-negligible overlap with error correction. I'm not even sure that "don't do error correction" makes sense as a limitation; it's too fuzzy. $\endgroup$ Apr 25, 2022 at 17:20
  • $\begingroup$ I see what you mean. You are probably right. The purpose of my question was to find if there are some "obvious" examples I didn't think about and to look for such papers (like "oh yeah obviously for such specific circuits we have an advantage kept"). It seems that it is either not possible or really not obvious if that exists. This was what I was interested to check (the other answer is interesting but from my current understanding it doesn't prove the complexity advantage kept when noise is "enabled"). $\endgroup$ Apr 26, 2022 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.