Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(N/logN) queries (improving an Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(N) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N1−1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [ SIAM J. Comput., 37 (2008), pp. 1387--1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus Ω(N1−1/2t) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what is arguably the simplest BQP-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”