Simon's problem asks the following: determine if a function
f:{0,1}n→{0,1}n is one-to-one or if there exists a unique
s∈{0,1}n such that
f(x)=f(x⊕s) for all
x∈{0,1}n, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every
f requires
2Ω(n) queries to
f. Simon showed that there is a quantum algorithm that can solve this promise problem for every
f using only
O(n) quantum queries to
f. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions
f:Fpn→Fpn. We give a short proof that
O(n) quantum queries is optimal even when we are additionally promised that
f is linear. This is somewhat surprising because for linear functions there even exists a classical
n-query algorithm.
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.
In 2009, using the
Fourier Checking problem, Aaronson claimed to construct the relativized worlds such that
BQP⊂BPPpath and
BQP⊂SZK. However, there are subtle errors in the original proof. In this paper, we point out the issues, and rescue these two separations by using more sophisticated constructions. Meanwhile, we take the opportunity to study the complexity classes
BPPpath and
SZK. We give general ways to construct functions which are hard for
SZK and
BPPpath (in the query complexity sense). Using these techniques, we give alternative construction for the oracle separation
BQP⊂SZK, using only Simon's problem. We also give new oracle separations for
PSZK from
BPPpath and
PSZK from
QSK. The latter result suggests that
PSZK might be strictly larger than
SZK.