The relationship between problem structure and exponential speedups under the query model

Question

What problem structure(s) are required to admit an exponential speedup in the universal quantum model of computation under the query model?

Intuitively, it would seem that much of the benefit of the quantum model, as is often suggested, is due to the ability to compute the solution in an exponentially large Hilbert space – i.e. a superposition of exponentially many possible states. We apply functions, encoded as unitary operators, to orchestrate useful interference over the amplitudes of the state space and repeat to a desired precision and measure. However, this is in essence the amplitude amplification framework inspired by Grover, which is not known to yield an exponential speedup for any problem.

So recently, I've been digging into this line of inquiry. Aaronson & Ambainis (2014), Ben-David(2011) Chailloux (2018) (among others) studied the above question, however, to date it seems that it is unresolved (not least because it seems to be a very hard problem from a complexity standpoint). That said, on the basis of existing algorithms, Aaronson and Ambainis suggest:

In the context of most existing quantum algorithms, “structured” basically means that we are trying to determine some global property of an extremely long sequence of numbers, assuming that the sequence satisfies some global regularity. As a canonical example, consider PERIOD-FINDING, the core of Shor’s algorithms for factoring and computing discrete logarithms...The requirement of periodicity is crucial here: it is what lets us use the Quantum Fourier Transform to extract the information we want from a superposition...For other known quantum algorithms, X needs to be (for example) a cyclic shift of quadratic residues or constant on the cosets of a hidden subgroup.

This, as might be presumed, is different from the approach taken by amplitude amplification – setting aside the notion of finding a global property within a sequence with assumed global regularity. So, my question is, dipping below the surface, what is the intuition around the kinds of problems that yield quantum algorithms with an exponential speedup under the query model? Can we simply put it down to period finding and hidden subgroups or is there a higher level intuition that captures the interplay between the problem structure and the properties of quantum information (i.e. entanglement, superposition, and interference) that seem superficially necessary for an exponential speedup?

Answer 1

The Aaronson-Ambainis (AA) conjecture implies that there must be some structure that's exploitable by a quantum algorithm to have any hope to achieve an exponential speedup for decision problems in NP. In his recent survey Aaronson also mentions the black-box welded-tree like problems, but note that a quantum algorithm sees such problems as merely a "path graph" which may be the kind of structure that enables the exponential quantum speedup in the decision problem and is consistent with the AA conjecture.

But, another brilliant algorithm of Yamakawa and Zhandry provides an exponential speedup to a "structureless" problem, and completely sidesteps the AA conjecture by moving to search problems in NP, and not decision problems in NP! The Yamakawa-Zhandry algorithm combines many ideas from quantum computation and coding theory to find a string that concurrently satisfies certain properties related to both random oracles/hashing (such as SHA256) and error correction (such as the Reed-Solomon code).

Once the attention shifts from decision problems to search problems, I suspect that there may be many "structureless" problems whose decision problem is trivial but whose search problem is in BQP but not in BPP. Indeed, going all the way back even to Simon's algorithm we can define the following "structureless" search problem:

• Given a random two-to-one Boolean function $f(x)$ from $n$ bits to $n$ bits that does not necessarily satisfy the Simon promise, find a polynomial number of pairs $(d,y)\in(0,1)^n\times(0,1)^n$ with $d\ne\bf 0$ such that there exists collisions $(x_1,x_2)$ with $f(x_1)=f(x_2)=y$, and also $d\cdot(x_1\oplus x_2)=0$. That is, $(d,y)$ are both $n$-bit strings where $d$ encodes information about the preimages of $y$.

I claim that this is a search problem whose decision variant is trivial, because the function is two-to-one and there must exist many collisions from which to find pairs $(d,y)$. I claim also that this problem has an NP certificate - namely, the tuple $(x_1,x_2,d,y)$, because we can verify that $f(x_1)=f(x_2)=y$ and that $d\cdot(x_1\oplus x_2)=0$. It is also in BQP, with one query to prepare $\sum|x\rangle|f(x)\rangle$, and then to measure the second register in the computational basis to collapse the first register onto the superposition of $(x_1,x_2)$ and to measure the first register in the Hadamard basis to find a string $d$. Furthermore classically there needs to be an exponential number of queries because $f(x)$ could, for example, be a collision-resistant hash which is amenable to the birthday attack but not much else.

Note that in this particular problem (as opposed to Yamakawa-Zhandry), the quantum algorithm does not give witnesses that are classically efficient to verify! That is, the pair $(d,y)$ found by the quantum algorithm is not, in itself, a witness that is classically verifiable, as $(x_1,x_2)$ is also needed for verification.

Answer 2

Gilyén and Vazirani, building on the recent breakthrough of Hastings, give a (sub)-exponential separation for a quantum adiabatic algorithm with no sign problem. They design a graph that can be traversed easily with a quantum adiabatic algorithm but gets stuck in a bunch of dead ends classically, and further can't recognize when it's walking around in a loop. That is, their graph was specifically designed to frustrate classical algorithms.

They hint that the quantum improvement comes from (A) topological properties of the graph, (B) as well as $\ell_1$ sampling classically vs. $\ell_2$ sampling quantumly. See here for a nice video.

To my naivety, neither the topological properties of the graph nor the difference in $\ell_2$ vs. $\ell_1$ sampling appear to have much to do with the kind of structure at play in Shor's algorithm.

Some caveats/notes:

• They base their construction heavily on the "welded-trees" random walk of Childs, et al., which gives an exponential speedup of an oracle problem;
• They compare the quantum adiabatic algorithm to a classical algorithm and count the number of queries performed by the classical algorithm, and so it's not quite a quantum-query vs. classical-query comparison; and
• There's a lot of implication that such adiabatic algorithms with no sign problem are not $\mathsf{BQP}$-complete, and hence are not a universal model of quantum computation. So even a weakened model of quantum computation can still give (sub)-exponential speedups in a query model.

I really like how haphazard their FIG. 1 looks - there's no structure that jumps out!