# 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 '18 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.) – Squeamish Ossifrage Mar 15 '18 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). – Toby Hawkins Mar 15 '18 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. – Squeamish Ossifrage Mar 15 '18 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'. – Discrete lizard Mar 19 '18 at 8:49

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 '18 at 17:02
• @glS I added a sentence which I think should cut to the crux of the difference. Does that help? – Squeamish Ossifrage Apr 7 '18 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.

The paper is on the arxiv here, but here's a quick summary. 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. 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 '18 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.