ABSTRACT
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N1-1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus Ω(N1-1/2t) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."
- S. Aaronson. BQP and the polynomial hierarchy. In Proc. STOC, 2010. arXiv:0910.4698. Google ScholarDigital Library
- A. Ambainis. Polynomial degree vs. quantum query complexity. J. Comput. Sys. Sci., 72(2):220--238, 2006. Earlier version in FOCS 2003. quant-ph/0305028. Google ScholarDigital Library
- R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778--797, 2001. Earlier version in FOCS 1998, pp. 352--361. quant-ph/9802049. Google ScholarDigital Library
- J. N. de Beaudrap, R. Cleve, and J. Watrous. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449--461, 2002. quant-ph/0011065.Google ScholarCross Ref
- H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig. Quantum property testing. SIAM J. Comput., 37(5):1387--1400, 2008. Earlier version in SODA 2003. quant-ph/0201117. Google ScholarDigital Library
- S. Chakraborty, E. Fischer, A. Matsliah, and R. de Wolf. New results on quantum property testing. In Proc. FSTTCS, pages 145--156, 2010. arXiv:1005.0523.Google Scholar
- A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proc. STOC, pages 59--68, 2003. quant-ph/0209131. Google ScholarDigital Library
- R. Cleve. The query complexity of order-finding. Inf. Comput., 192(2):162--171, 2004. Earlier version in CCC'00. quant-ph/9911124. Google ScholarDigital Library
- I. Dinur, E. Friedgut, G. Kindler, and R. O'Donnell. On the Fourier tails of bounded functions over the discrete cube. In Proc. STOC, pages 437--446, 2006. Google ScholarDigital Library
- A. Drucker. Improved direct product theorems for randomized query complexity. Computational Complexity, 21(2):197--244, 2012. Earlier version in CCC'11. ECCC TR10-080. Google ScholarDigital Library
- S. Fenner and Y. Zhang. A note on the classical lower bound for a quantum walk algorithm. quant-ph/0312230v1, 2003.Google Scholar
- A. Montanaro and R. de Wolf. A survey of quantum property testing. arXiv:1310.2035, 2013.Google Scholar
- B. Reichardt. Reflections for quantum query algorithms. In Proc. SODA, pages 560--569, 2011. arXiv:1005.1601. Google ScholarDigital Library
- P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484--1509, 1997. Earlier version in FOCS 1994. quant-ph/9508027. Google ScholarDigital Library
- D. Simon. On the power of quantum computation. In Proc. FOCS, pages 116--123, 1994. Google ScholarDigital Library
Index Terms
- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Recommendations
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the ...
Query complexity in errorless hardness amplification
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniquesAn errorless circuit for a boolean function is one that outputs the correct answer or "don't know" on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that ...
A Tight Characterization of NP with 3 Query PCPs
FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer ScienceIt is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-...
Comments