Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR19-179 | 26th December 2019 16:46

#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revision #1
Authors: Avishay Tal
Accepted on: 26th December 2019 16:46
Keywords:

Abstract:

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. $\sqrt{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. $N^{1/2+\Omega(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 $2^{O(k)}$ queries to the inputs.
(2) Requires at least $\tilde{\Omega}(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm.

For any constant $\varepsilon>0$, this gives a $O(1)$ vs. $N^{2/3-\varepsilon}$ 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. $N^{1-\varepsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.

Changes to previous version:

Fixed a major bug in the proof of Lemma 6.1.

### Paper:

TR19-179 | 7th December 2019 07:30

#### Towards Optimal Separations between Quantum and Randomized Query Complexities

TR19-179
Authors: Avishay Tal
Publication: 7th December 2019 16:25
Keywords:

Abstract:

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. $\sqrt{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. $N^{1/2+\Omega(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 $2^{O(k)}$ queries to the inputs.
(2) Requires at least $\tilde{\Omega}(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm.

For any constant $\varepsilon>0$, this gives a $O(1)$ vs. $N^{2/3-\varepsilon}$ 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. $N^{1-\varepsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.

ISSN 1433-8092 | Imprint