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

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 (as far as I know, would love to hear otherwise) does not yield exponential speedups for any problems.

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 with an 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?

• This paper by Aaronson and Ben-David seems related: arxiv.org/abs/1512.04016 Jan 30 '20 at 7:41
• This is an active area of research, so nobody really knows the answer. (Although I'm willing to be pleasantly surprised if someone does give you a succinct definitive answer here.) Jan 31 '20 at 7:07
• arxiv.org/abs/2001.09642 Feb 13 '20 at 2:52

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!

• Blimey that's a hideous graph! Hah! Thanks for sharing this and these papers – it certainly feels like a piece of the puzzle. Will read and respond with something more thoughtful soon! Apr 21 at 23:25
• For now I'll say this – as I think you hinted – it certainly seems that designing some mathematical object that frustrates a classical algorithm (but is efficiently computed with by a quantum algorithm) does not guarantee that the object (or the algorithms themselves) are revealing of a general principle or structure behind the types of problems for which one algorithm yields an exponential advantage over the other (in this case due to quantum information). I think (and need to think more about this). Apr 21 at 23:36