Fetching the paper…

Reading the bibliography…

An Optimal Separation of Randomized and Quantum Query Complexity · Around

2020

An Optimal Separation of Randomized and Quantum Query Complexity

Sherstov, Alexander A., Storozhenko, Andrey A., Wu, Pei

Original
PDF
Post on X

Understand

We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.

This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020).
The bounds prior to our work degraded rapidly with $\ell,$ becoming trivial already at $\ell=\sqrt{d}.$ As an application, we obtain, for every integer $k\geq1,$ a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $k$ and randomized query complexity $\tilde{\Omega}(n^{1-\frac{1}{2k}}).$ This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021).
Prior to our work, the best known separation was polynomially weaker: $O(1)$ versus $\Omega(n^{2/3-\epsilon})$ for any $\epsilon>0$ (Tal, FOCS 2020).

Built on

D. Deutsch and R. Jozsa
1992
Earlier work this paper cites.
L. K. Grover
1996
Earlier work this paper cites.
E. Bernstein and U. V. Vazirani
1997
Earlier work this paper cites.
P. W. Shor
1997
Earlier work this paper cites.
D. R. Simon
1997
Earlier work this paper cites.
H. Buhrman, R. Cleve, and A. Wigderson
1998
Earlier work this paper cites.
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf
2001
Earlier work this paper cites.
H. Buhrman and R. de Wolf
2002
Earlier work this paper cites.
R. O’Donnell and R. A. Servedio
2007
Earlier work this paper cites.
H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig
2008
Earlier work this paper cites.

Similar

R. de Wolf
Original
2008
Cited alongside, same era.
S. Jukna
2011
Cited alongside, same era.
O. Regev and B. Klartag
2011
Cited alongside, same era.
R. O’Donnell
2014
Cited alongside, same era.
S. Aaronson, S. Ben-David, and R. Kothari
2016
Cited alongside, same era.
P. Gopalan, R. A. Servedio, and A. Wigderson
2016
Cited alongside, same era.
T. Steinke, S. P. Vadhan, and A. Wan
2017
Cited alongside, same era.

Then

A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, and T. Pitassi
2019
Later among the works it cites.
H. Huang
2019
Later among the works it cites.
Available at https://arxiv.org/abs/2004.13231 , 2020
Original
S. Aaronson, S. Ben-David, R. Kothari, and A. Tal · 2020
Closest in time.
Available at https://arxiv.org/abs/2008.07003 , 2020
Original
N. Bansal and M. Sinha · 2020
Closest in time.
D. Gavinsky
2020
Closest in time.
J. Blasiok, P. Ivanov, Y. Jin, C. H. Lee, R. A. Servedio, and E. Viola
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

S. Aaronson and A. Ambainis

2018

Cited alongside, same era.

E. Chattopadhyay, P. Hatami, K. Hosseini, and S. Lovett

2018

Cited alongside, same era.

E. Chattopadhyay, P. Hatami, O. Reingold, and A. Tal

2018

Cited alongside, same era.

Available at https://arxiv.org/abs/2102.06963 , 2021

S. Bravyi, D. Gosset, D. Grier, and L. Schaeffer · 2021

Closest in time.

U. Girish, A. Tal, and K. Wu

2021

Closest in time.

Report TR22-034

C. H. Lee, E. Pyne, and S. P. Vadhan · 2022

Closest in time.