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?