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

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