# Are there problems in which quantum computers are known to provide an exponential advantage?

It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks.

One of the most commonly cited examples of a problem in which quantum computers would outperform classical devices is $\text{Factoring}$, but then again, it is also not known whether $\text{Factoring}$ is also efficiently solvable with a classical computer (that is, whether $\text{Factoring}\in \text{P}$).

For other commonly cited problems in which quantum computers are known to provide an advantage, such as database search, the speedup is only polynomial.

Are there known instances of problems in which it can be shown (either proved or proved under strong computational complexity assumptions) that quantum computers would provide an exponential advantage?

• I would say the answer is no if you restrict the problems to be decision problem, because there are sampling problems (e.g. BosonSampling and IQP) for which an exponential quantum advantage has been shown (or rather, proven under strong assumptions). There may be others that I don't know.
– glS
Mar 15, 2018 at 14:49
• Note that there are already many subexponential-cost classical algorithms for factoring. (There is a substantial gap between polynomial and exponential costs.) Mar 15, 2018 at 22:19
• As heather says, this is currently not know since the limits of classical (and quantum) computers are not known. The criteria you set forth in your question ultimately require the answerer to go even beyond proving the relationship beyond P and NP. I'd suggest you reword your question to ask for other likely examples (as well as factoring). Mar 15, 2018 at 23:18
• The practical consequences of a quantum speedup, e.g. for whether Shor's algorithm can actually outperform the classical GNFS, are also not necessarily implied by asymptotic relations of the growth curves of the costs. See this answer for a bit more about the asymptotic vs. concrete setting, and why questions around P = NP are a bit of a red herring for cryptography and practical performance comparisons. Mar 15, 2018 at 23:28
• @SqueamishOssifrage Exactly. I'd like to add that equating membership of P with 'efficient' is more wishful thinking by computer scientists than absolute truth. The idea is that, once it has shown that a problem lies in P, even if its something ghastly like $O(n^{1235436546})$, there will be improvements shaving it off to something similar to $O(n^3)$, a bit closer to the cosy 'conditional lower bounds'. To credit, this has usually happened in the past. But this is no guarantee and as for the practicality there even exist 'linear' algorithms that are considered 'unimplementable'. Mar 19, 2018 at 8:49

## 5 Answers

Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is the only solution, this means $f$ is 1-to-1; otherwise there is a nonzero $s$ such that $f(x) = f(x + s)$ for all $x$, which, because $2 = 0$, means $f$ is 2-to-1.

What is the cost to any prescribed probability of success, on a classical or quantum computer, of distinguishing a uniform random 1-to-1 function from a uniform random 2-to-1 function satisfying this property, if each option (1-to-1 or 2-to-1) has equal probability?

I.e., I secretly flip a coin fairly; if I get heads I hand you a black box (classical or quantum, resp.) circuit for a uniform random 1-to-1 function $f$, whereas if I get tails I hand you a black box circuit for a uniform random 2-to-1 function $f$. How much do you have to pay to get a prescribed probability of success $p$ of telling whether I got heads or tails?

This is the scenario of Simon's algorithm. It has esoteric applications in nonsensical cryptanalysis,* and it was an early instrument in studying the complexity classes BQP and BPP and an early inspiration for Shor's algorithm.

Simon presented a quantum algorithm (§3.1, p. 7) that costs $O(n + |f|)$ qubits and expected $O(n \cdot T_f(n) + G(n))$ time for probability near 1 of success, where $T_f(n)$ is the time to compute a superposition of values of $f$ on an input of size $n$ and where $G(n)$ is the time to solve an $n \times n$ system of linear equations in $\mathbb F_2$.

Simon further sketched a proof (Theorem 3.1, p. 9) that a classical algorithm evaluating $f$ at no more than $2^{n/4}$ distinct discrete values cannot guess the coin with advantage better than $2^{-n/2}$ over a uniform random guess.

In some sense, this answers your question positively: A quantum computation requiring a linear number of evaluations of random function on a quantum superposition of inputs can attain much better success probability than a classical computation requiring an exponential number of evaluations of a random function on discrete inputs, in the size of the inputs. But in another sense it doesn't answer your question at all, because it could be that for every particular function $f$ there is a faster way to compute the search.

The Deutsch–Jozsa algorithm serves as a similar illustration for a slightly different artificial problem to study different complexity classes, P and EQP, figuring out the details of which is left as an exercise for the reader.

* Simon's is nonsensical for cryptanalysis because only an inconceivably confused idiot would feed their secret key into the adversary's quantum circuit to use on a quantum superposition of inputs, but for some reason it makes a splash every time someone publishes a new paper on using Simon's algorithm to break idiots' keys with imaginary hardware, which is how all these attacks work. Exception: It is possible that this might break white-box cryptography, but the security story for white-box cryptography even against classical adversaries is not promising.

• interesting, thanks for the answer. Can you expand as to why this is not proof that $\text{BQP}\neq\text{BPP}$? I guess the answer is something along the lines of this showing an oracular separation, as opposite to a "regular" one, but I'm not versed enough in these topics to really say. I think a brief discussion of this would improve the answer.
– glS
Mar 21, 2018 at 17:02
• @glS I added a sentence which I think should cut to the crux of the difference. Does that help? Apr 7, 2018 at 4:55

Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is more or less nonexistent...), but a recent result by Bravyi et. al presented a class of '2D Hidden Linear Function problems' that provably use fewer resources on a quantum parallel device.

Here is a quick summary of the paper Sergey Bravyi, David Gosset and Robert Koenig, Quantum advantage with shallow circuits. The quantum advantage is in the depth of the parallel circuit, so the number of threads one can split the problem into under bounded fan-in. The problem is given a $$N\times N$$ matrix $$A$$ and an input vector $$b$$, one can define a quadratic form $$q$$ and a special subspace for that form. The "hidden linear function problem"'s goal is to find a linearization for that quadratic function on a special subspace.

A classical probablistic circuit is constrained to ~$$\log{N}$$ depth, if you want your computation to succeed with probability $$>7/8$$ (you probably want it to succeed with at least this probability). A quantum circuit can do it with constant depth, so that's a big improvement.

The proof essentially amounts to a specific graph state being difficult for a classical circuit to simulate, this sub-result was proven slightly earlier by Jonathan Barrett, Carlton M. Caves, Bryan Eastin, Matthew B. Elliott and Stefano Pironio, Modeling Pauli measurements on graph states with nearest-neighbor classical communication. Then the rest of the paper shows that the greater class of problems contains this difficult problem.

The complexity class of decision problems efficiently solvable on a classical computer is called BPP (or P, if you don't allow randomness, but these are suspected to be equal anyway). The class of problems efficiently solvable on a quantum computer is called BQP. If a problem exists for which a quantum computer provides an exponential speedup, then this would imply that BPP $$\neq$$ BQP. However, the BQP versus BPP question is a major open question in theoretical computer science, so no such problem has been proven to exist (and if you find one, you'll definitely win all kinds of awards).

On the other hand, as the other answer mentions, there are black-box ("oracle") problems relative to which we know that $$\textbf{BPP}^O \neq \textbf{BQP}^O$$, like Simon's algorithm. This provides evidence, though not a proof, that BPP $$\neq$$ BQP in the real world.

• great answer, thanks. I didn't restrict myself to decision problems in the question though. Could you add a mention to what happens when one considers different kinds of problems, like sampling problems for example? Also, are you able to expand a bit on the reason why the oracular inequivalence of BPP and BQP provides evidence for BPP$\neq$BQP "in the real world"?
– glS
Mar 28, 2018 at 14:35

Whilst I cannot supply a formal proof, the simulation of (the temporal evolution) of a quantum system is believed to be such a case: There is no known better way to do this on a classical computer than in exponential time but a quantum computer can trivially do it in polynomial time.

The idea of such a quantum simulator (see also wikipedia article) is in fact how quantum computers got first proposed.

• +1 because I think this is in fact the quantum computers' main promise: by enabling us to simulate matter efficiently and accurately they will accelerate innovation. However, I would not say that quantum computers can simulate other quantum systems "trivially". For example, encoding fermionic states in qubits is non-trivial (see e.g. Bravyi-Kitaev transform). Quantum circuit to evolve a given Hamiltonian is also non-trivial (see e.g. Trotterization) and involves trade-offs between time and accuracy (remember that a quantum computer generally has a fixed set of gates). Feb 2, 2021 at 19:19
• @AdamZalcman I might have to formalize a question that I have about this, but what is meant by "encoding fermionic states in qubits" and how is that not related to Hamiltonian simulation thereof? This goes back to an earlier question of mine about Feynman's original motivation and his excitement about bosons but his hesitancy about fermions, along with the responses to Feynman's conjecture. What did Bravyi-Kitaev do with fermions that's different from what Lloyd and the other Trotterizers/other Hamiltonian simulators did? Sep 14, 2022 at 21:20
• @AdamZalcman I think I see. The problem addressed by Bravyi-Kitaev etc. is to map a wavefunction of electrons (fermions) onto a wavefunction of qubits (two-level systems), evolve the qubits according to the appropriate Hamiltonian, and then map the wavefunction of qubits back onto that of the electrons, such that the "diagrams commute" and the phases pick up the right parity. Hamiltonian simulation, however, maps a Hamiltonian onto a sequence of unitary gates acting on qubits, such that the overall unitary is "close to" $e^{-iHt}$. Here, qubits are not fermions but a different beast. Sep 14, 2022 at 22:40
• @MarkS Yeah, that's a good summary. Also, I didn't mean to single out fermions. Simulating bosonic systems also has its challenges. For example, state space is infinite-dimensional, so any encoding into a qubit system suffers truncation error that needs to be minimized. I meant to use fermions as an example to highlight that quantum simulation, while certainly promising and practical, isn't trivial even for quantum computers. Sep 14, 2022 at 23:27
• @AdamZalcman thanks! It’s somewhat profound to ponder the difference between bosons, fermions, and qubits. Fermions naively have the sign problem, which bosons don’t. However, Aaronson and Arkhipov noted that bosons’ sampling behavior is driven by the permanent, which is computationally much harder than fermion sampling, which is given by the determinant. Sep 15, 2022 at 1:15

Here is one example of exponential speedup. It is to find eigenvalues and eigenvectors of a local Hamiltonian using the quantum fast Fourier transform Daniel S. Abrams, Seth Lloyd, A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.

• Abrams and Lloyd's paper is a nice extension of Feynman's original ideas, mentioned below. As an aside and unrelated, it's fun reading these mid-late '90's quantum computing articles - they have such nice and quaint quirks, like liberally using $>$ being used instead of $\rangle$, not using circuit diagrams, etc. What we would now call a quantum Fourier transform, or QFT, is referred to as a quantum fast Fourier transform, or quantum FFT. Jan 27, 2022 at 15:55