Quantum lower bounds by polynomials

ABSTRACT

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1}^N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O(Ts⁶) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

REFERENCES

• 1: Laurent Alonso , Edward M. Reingold , René Schott, Determining the majority, Information Processing Letters, v.47 n.5, p.253-255, Oct. 8, 1993 [doi>10.1016/0020-0190(93)90135-V]
• 2: Andris Ambainis, A note on quantum black-box complexity of almost all Boolean functions, Information Processing Letters, v.71 n.1, p.5-7, July 30, 1999 [doi>10.1016/S0020-0190(99)00079-4]
• 3: Andris Ambainis, Quantum lower bounds by quantum arguments, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.636-643, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335394]
• 4: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum Lower Bounds by Polynomials, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.352, November 08-11, 1998
• 5: BEIGEL, R. 1993. The polynomial method in circuit complexity. In Proceedings of the 8th IEEE Structure in Complexity Theory Conference. IEEE Computer Society Press, Los Alamitos, Calif., pp. 82- 95.
• 6: Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
• 7: Dan Boneh , Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.424-437, August 27-31, 1995
• 8: BOYER, M., BRASSARD, G., H~YER,P.,AND TAPP, A. 1998. Tight bounds on quantum searching. Fortschritte der Physik 46, 4-5, 493-505. (quant-ph/9605034.)
• 9: Gilles Brassard , Peter Hoyer, An Exact Quantum Polynomial-Time Algorithm for Simon's Problem, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.12, June 17-19, 1997
• 10: BRASSARD, G., H~YER, P., MOSCA, M., AND TAPP, A. 2000. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millenium Volume. AMS Contemporary Mathematics Series.
• 11: Gilles Brassard , Peter Høyer , Alain Tapp, Quantum cryptanalysis of hash and claw-free functions, ACM SIGACT News, v.28 n.2, p.14-19, June 1997 [doi>10.1145/261342.261346]
• 12: Gilles Brassard , Peter Høyer , Alain Tapp, Quantum Counting, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.820-831, July 13-17, 1998
• 13: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 14: Harry Buhrman , Richard Cleve , Ronald de Wolf , Christof Zalka, Bounds for Small-Error and Zero-Error Quantum Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.358, October 17-18, 1999
• 15: Harry Buhrman , Ronald de Wolf , Christoph Dürr , Mark Heiligman , Peter Hyer , Frédéric Magniez , Miklos Santha, Quantum Algorithms for Element Distinctness, Proceedings of the 16th Annual Conference on Computational Complexity, p.131, June 18-21, 2001
• 16: Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
• 17: Richard Cleve, The Query Complexity of Order-Finding, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.54, July 04-07, 2000
• 18: CLEVE, R., EKERT, A., MACCHIAVELLO, C., AND MOSCA, M. 1998. Quantum algorithms revisited. Proc. Roy. Soc. London A454, 339-354. (quant-ph/9708016.)
• 19: Wim van Dam, Quantum Oracle Interrogation: Getting All Information for Almost Half the Price, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.362, November 08-11, 1998
• 20: VAN DAM W., AND HALLGREN, S. 2000. Efficient quantum algorithms for shifted quadratic character problems. (quant-ph/0011067.)
• 21: DEUTSCH, D., AND JOZSA, R. 1992. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A439, 553-558.
• 22: EHLICH, H., AND ZELLER, K. 1964. Schwankung von Polynomen zwischen Gitterpunkten. Math. Z. 86, 41-44.
• 23: FARHI, E., GOLDSTONE, J., GUTMANN, S., AND SIPSER, M. 1998. A limit on the speed of quantum computation in determining parity. Phys. Rev. Lett. 81, 5442-5444.
• 24: FARHI, E., GOLDSTONE, J., GUTMANN, S., AND SIPSER, M. 1999a. How many functions can be distinguished with k quantum queries? Phys. Rev. A 60, 6, 4331-4333. (quant-ph/9901012.)
• 25: FARHI, E., GOLDSTONE, J., GUTMANN, S., AND SIPSER, M. 1999b. Invariant quantum algorithms for insertion into an ordered list. (quant-ph/9901059.)
• 26: FENNER, S., FORTNOW, L., KURTZ, S., AND LI, L. 1993. An oracle builder's toolkit. In Proceedings of the 8th IEEE Structure in Complexity Theory Conference. IEEE Computer Society Press, Los Alamitos, Calif., pp. 120-131.
• 27: Lance Fortnow , John Rogers, Complexity limitations on Quantum computation, Journal of Computer and System Sciences, v.59 n.2, p.240-252, Oct. 1999 [doi>10.1006/jcss.1999.1651]
• 28: VON ZUR GATHEN, J., AND ROCHE, J. R. 1997. Polynomials with two values. Combinatorica 17,3, 345-362.
• 29: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 30: Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
• 31: Thomas Hayes , Samuel Kutin , Dieter Van Melkebeek, On the Quantum Complexity of Majority, University of Chicago, Chicago, IL, 1998
• 32: HOYER, P. 1999. Conjugated operators in quantum algorithms. Phys. Rev. A 59, 5, 3280-3289.
• 33: Peter Høyer , Jan Neerbek , Yaoyun Shi, Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.346-357, July 08-12, 2001
• 34: JOZSA, R. 1991. Characterizing classes of functions computable by quantum parallelism. Proc. Roy. Soc. London A435, 563-574.
• 35: KITAEV, A. Y. 1995. Quantum measurements and the Abelian stabilizer problem. (quant-ph/9511026.)
• 36: Marvin L. Minsky , Seymour A. Papert, Perceptrons: expanded edition, MIT Press, Cambridge, MA, 1988
• 37: MOSCA, M. 1998. Quantum searching, counting and amplitude amplification by eigenvector analysis. In MFCS'98 Workshop on Randomized Algorithms, pp. 90-100.
• 38: Michele Mosca , Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.174-188, February 17-20, 1998
• 39: Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301349]
• 40: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 41: Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
• 42: Noam Nisan , Mario Szegedy, On the degree of Boolean functions as real polynomials, Computational Complexity, v.4 n.4, p.301-313, Oct. 1994 [doi>10.1007/BF01263419]
• 43: Yuri Ozhigov, Quantum Computer Can Not Speed Up Iterated Applications of a Black Box, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.152-159, February 17-20, 1998
• 44: Ramamohan Paturi, On the degree of polynomials that approximate symmetric Boolean functions (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.468-474, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129758]
• 45: RIVLIN,T.J.,AND CHENEY, E. W. 1966. A comparison of uniform approximations on an interval and a finite subset thereof. SIAM J. Numer. Anal. 3, 2, 311-320.
• 46: SAKS, M., AND WIGDERSON, A. 1986. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proceedings of 27th IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 29-38.
• 47: SAKS, M. E., AND WERMAN, M. 1991. On computing majority by comparisons. Combinatorica 11,4, 383-387.
• 48: SANTHA, M. 1991. On the Monte Carlo decision tree complexity of read-once formulae. In Proceedings of the 6th IEEE Structure in Complexity Theory Conference. IEEE Computer Society Press, Los Alamitos, Calif., pp. 180-187.
• 49: Uwe Schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.410, October 17-18, 1999
• 50: Rocco A. Servedio , Steven J. Gortler, Quantum versus Classical Learnability, Proceedings of the 16th Annual Conference on Computational Complexity, p.138, June 18-21, 2001
• 51: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 52: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 53: VAZIRANI, U. 1998. On the power of quantum computation. Proc. Roy. Soc. London A356. 1759-1768.
• 54: Ronald de Wolf, Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.271, July 04-07, 2000
• 55: ZALKA,CH. 1999. Grover's quantum searching algorithm is optimal. Phys. Rev. A 60, 2746-2751. (quant-ph/9711070.)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
Quantum computing, black-box model, lower bounds, polynomial method, query complexity