TY - GEN

T1 - An optimal separation of randomized and Quantum query complexity

AU - Sherstov, Alexander A.

AU - Storozhenko, Andrey A.

AU - Wu, Pei

N1 - Publisher Copyright:
© 2021 Owner/Author.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - We prove that for every decision tree, the absolute values of the Fourier coefficients of given order t?1 sum to at most (cd/t)t/2(1+logn)(t-1)/2, 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 t, becoming trivial already at t=?d. As an application, we obtain, for every integer k?1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k/2 and randomized query complexity ?(n1-1/k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation was polynomially weaker: O(1) versus ?(n2/3-?) for any ?>0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O(logn) versus ?(n1-?) for bounded-error quantum versus randomized communication complexity, for any ?>0. The best previous separation was polynomially weaker: O(logn) versus ?(n2/3-?) (implicit in Tal, FOCS 2020).

AB - We prove that for every decision tree, the absolute values of the Fourier coefficients of given order t?1 sum to at most (cd/t)t/2(1+logn)(t-1)/2, 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 t, becoming trivial already at t=?d. As an application, we obtain, for every integer k?1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k/2 and randomized query complexity ?(n1-1/k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation was polynomially weaker: O(1) versus ?(n2/3-?) for any ?>0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O(logn) versus ?(n1-?) for bounded-error quantum versus randomized communication complexity, for any ?>0. The best previous separation was polynomially weaker: O(logn) versus ?(n2/3-?) (implicit in Tal, FOCS 2020).

UR - http://www.scopus.com/inward/record.url?scp=85108167033&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108167033&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451019

DO - 10.1145/3406325.3451019

M3 - Conference contribution

AN - SCOPUS:85108167033

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1289

EP - 1302

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -