Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GAUSSIAN INTERPOLATION:
Reports tagged with Gaussian Interpolation:
TR20-127 | 21st August 2020
Nikhil Bansal, Makrand Sinha

#### $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

Aaronson and Ambainis (SICOMP '18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured ... more >>>

ISSN 1433-8092 | Imprint