ECCC-Report TR20-127https://eccc.weizmann.ac.il/report/2020/127Comments and Revisions published for TR20-127en-usTue, 17 Nov 2020 16:12:55 +0200
Revision 2
| $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity |
Nikhil Bansal,
Makrand Sinha
https://eccc.weizmann.ac.il/report/2020/127#revision2 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 the $k$-Forrelation problem --- a partial function that can be computed with $q = \lceil k/2 \rceil$ quantum queries --- to be a suitable candidate for exhibiting such an extremal separation.
We prove their conjecture by showing a tight lower bound of $\widetilde{\Omega}(N^{1-1/k})$ for the randomized query complexity of $k$-Forrelation, where the advantage $\delta = 2^{-O(k)}$. By standard amplification arguments, this gives an explicit partial function that exhibits an $O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$ separation between bounded-error quantum and randomized query complexities, where $\epsilon>0$ can be made arbitrarily small. Our proof also gives the same bound for the closely related but non-explicit $k$-Rorrelation function introduced by Tal (FOCS `20).
Our techniques rely on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, give a more general statement. We show that to prove lower bounds for $k$-Forrelation against a family of functions, it suffices to bound the $\ell_1$-weight of the Fourier coefficients between levels $k$ and $(k-1)k$. We also prove new interpolation and integration by parts identities that might be of independent interest in the context of rounding high-dimensional Gaussian vectors. Tue, 17 Nov 2020 16:12:55 +0200https://eccc.weizmann.ac.il/report/2020/127#revision2
Revision 1
| $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity |
Nikhil Bansal,
Makrand Sinha
https://eccc.weizmann.ac.il/report/2020/127#revision1 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 the $k$-Forrelation problem --- a partial function that can be computed with $q = \lceil k/2 \rceil$ quantum queries --- to be a suitable candidate for exhibiting such an extremal separation. \medskip
We prove their conjecture by showing a tight lower bound of $\widetilde{\Omega}(N^{1-1/k})$ for the randomized query complexity of $k$-Forrelation, where the advantage $\delta = 2^{-O(k)}$. By standard amplification arguments, this gives an explicit partial function that exhibits an $O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$ separation between bounded-error quantum and randomized query complexities, where $\epsilon>0$ can be made arbitrarily small. Our proof also gives the same bound for the closely related but non-explicit $k$-Rorrelation function introduced by Tal (FOCS `20). \medskip
Our techniques rely on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, give a more general statement. We show that to prove lower bounds for $k$-Forrelation against a family of functions, it suffices to bound the $\ell_1$-weight of the Fourier coefficients between levels $k$ and $(k-1)k$. We also prove new interpolation and integration by parts identities that might be of independent interest in the context of rounding high-dimensional Gaussian vectors. Mon, 16 Nov 2020 23:44:10 +0200https://eccc.weizmann.ac.il/report/2020/127#revision1
Paper TR20-127
| $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity |
Nikhil Bansal,
Makrand Sinha
https://eccc.weizmann.ac.il/report/2020/127Aaronson 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 the $k$-Forrelation problem --- a partial function that can be computed with $q = \lceil k/2 \rceil$ quantum queries --- to be a suitable candidate for exhibiting such an extremal separation.
We prove their conjecture by showing a tight lower bound of $\widetilde{\Omega}_k(N^{1-1/k})$ for the randomized query complexity of $k$-Forrelation, where the advantage $\delta = 1/\mathrm{polylog}^k(N)$ and $\widetilde{\Omega}_k$ hides $\mathrm{polylog}^k(N)$ factors. Our proof relies on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, shows a more general statement, that to prove lower bounds for $k$-Forrelation against a family of functions, it suffices to bound the $\ell_1$-weight of the Fourier coefficients at levels $k, 2k, 3k, \ldots, (k-1)k$ for functions in the family.Fri, 21 Aug 2020 22:02:19 +0300https://eccc.weizmann.ac.il/report/2020/127