One of the most active research directions in quantum computing currently is establishing quantum supremacy results: coming up with computational tasks which a quantum algorithm can solve super-polynomially faster than a classical algorithm. In this talk we look at the particular computational model of query complexity: where the algorithm has to evaluate a known function on an unknown input; it can access the input by asking queries to an oracle and has to minimize the number of queries. Internal computations are assumed to have no cost. We can define the quantum variant of query complexity where the quantum algorithm has access to an oracle representing the input and can ask queries in superposition.
One of the long-standing questions in this direction is the following: given a quantum query algorithm for a Boolean function (defined on a subset of the Boolean hypercube with at least inverse polynomial density) making d queries, does there exist a classical query algorithm which makes at most poly(d) queries and approximates the output probability of the quantum algorithm on most inputs? We shall discuss the body of previous work done on this question: weak results that are known, a recent attempt to resolve the conjecture which turned out to have a fatal flaw and our attempts to fix the argument.
