What is the largest separation between quantum and classical query complexity?

Niel de Beaudrap, Not Available Not Available, Not Available Not Available

Scott Aaronson, Andris Ambainis

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 $\Omega(\sqrt{N}/\log N)$ queries (improving an $\Omega(N^{1/4})$ lower bound of Aaronson). Conversely, we show that this 1 versus $\widetilde{\Omega}(\sqrt{N})$ separation is optimal: indeed, any $t$-query quantum algorithm whatsoever can be simulated by an $O(N^{1-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 $\Omega(N^{1-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.”

Scott Aaronson, Andris Ambainis, Andrej Bogdanov +2 more

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

Kamil Khadiev, Vladislav Remidovskii, Timur Bikmullin +1 more

In the paper, we consider the problem of searching for the Largest empty rectangle in a 2D map, and the one-dimensional version of the problem is the problem of searching for the largest empty segment. We present a quantum algorithm for the Largest Empty Square problem and the Largest Empty Rectangle of a fixed width $d$ for $n\times n$-rectangular map. Query complexity of the algorithm is $\tilde{O}(n^{1.5})$ for the square case, and $\tilde{O}(n\sqrt{d})$ for the rectangle with a fixed width $d$ case, respectively. At the same time, the lower bounds for the classical case are $Ω(n^2)$, and $Ω(nd)$, respectively. The Quantum algorithm for the one-dimensional version of the problem has $O(\sqrt{n}\log n\log\log n)$ query complexity. The quantum lower bound for the problem is $Ω(\sqrt{n})$ which is almost equal to the upper bound up to a log factor. The classical lower bound is $Ω(n)$. So, we obtain the quadratic speed-up for the problem.