Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QUANTUM-CLASSICAL SEPARATION:
Reports tagged with Quantum-classical separation:
TR20-128 | 3rd September 2020
Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

#### An Optimal Separation of Randomized and Quantum Query Complexity

Revisions: 1

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\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 ... more >>>

ISSN 1433-8092 | Imprint