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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.