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 δ over a random guess by making q quantum queries, can also be computed classically with an advantage δ/2 by a randomized decision tree making O q ( N 1−1/2 q δ −2 ) queries. Moreover, they conjectured the k -Forrelation problem — a partial function that can be computed with q = ⌈ k /2 ⌉ quantum queries — to be a suitable candidate for exhibiting such an extremal separation.

Authors

• Nikhil Bansal 0001
• Makrand Sinha

Keywords

• Decision Trees
• Forrelation
• Gaussian Interpolation
• Quantum query complexity
• Stochastic Calculus