All reports by Author Nikhil Bansal:

__
TR20-127
| 21st August 2020
__

Nikhil Bansal, Makrand Sinha#### $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

Revisions: 2

Nikhil Bansal, Makrand Sinha

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 >>>