Explanation for non-PhD's (my qualifications: I do some quantum research, and the other day I was at Aaron's talk he refers to, and briefly talked to him afterw

Explanation for non-PhD's (my qualifications: I do some quantum research, and the other day I was at Aaron's talk he refers to, and briefly talked to him afterward). The overarching problem is whether we can prove that quantum algorithms are exponentially faster than classical algorithms. We believe it's true for things like factoring or discrete log (maybe), but these are conjectural because proving lower bounds for general classical algorithms is really really hard. One the other hand, there are other problem models in which we can prove quantum algorithms are much faster than classical algorithms. These generally take the form of a "black-box query" model. Here is one example: there is a hidden boolean function f(x), and you get the promise that it has one of two properties (which are mutually exclusive). You get to query inputs x and receive outputs f(x), and you want to determine which of the two properties it has. The simplest example of such a problem is determining whether a function is contstant or is 0 on exactly half of the inputs and 1 on the other half. Classically you have to query 2^(n-1) + 1 inputs in the worst case. If you're allowed to give queries which are quantum superpositions of some inputs, then you can actually do it with one query. [1] The model studied by Aaronson and Ambainis et al. is a slightly different kind of black box model, but with a similar flavor. You know f and you get query access to the bits of an unknown input x. You want to compute f(x) with as few queries as possible. Clearly you can do it with N queries where x has N bits, but some quantum algorithms can do it in 1 query by making a quantum query. In that model the goal is still to show the biggest gap in the number of needed queries between quantum algorithms and classical algorithms (possibly with randomness). Also people are interested in the difference between classical algorithms with randomness and without randomness, and in addition to proving the biggest quantum/classical gap, Amabainis et al refute a major conjecture about the biggest possible randomized/determinstic classical gap. [1]: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorith...