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. ALONSO, L., REINGOLD,E.M.,AND SCHOTT, R. 1993. Determining the majority. Inf. Proc. Lett. 47,5, 253-255.]]
2. AMBAINIS, A. 1999. A note on quantum black-box complexity of almost all Boolean functions. Inf. Proc. Lett. 71, 1, 5-7. (Also available at http://xxx.lanl.gov/abs/quant-ph/9811080.)]]
3. AMBAINIS, A. 2000. Quantum lower bounds by quantum arguments. In Proceedings of 32nd Annual ACM Symposium on Theory of Computing (Portland, Ove., May 21-23). ACM, New York, pp. 636-643. (quant-ph/0002066.)]]
4. BEALS, R., BUHRMAN, H., CLEVE, R., MOSCA, M., AND DE WOLF, R. 1998. Quantum lower bounds by polynomials. In Proceedings of 39th Annual IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 352-361. (quant-ph/9802049.)]]
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. BENNETT, C. H., BERNSTEIN, E., BRASSARD, G., AND VAZIRANI, U. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput, 26, 5, 1510-1523. (quant-ph/9701001.)]]
7. BONEH, D., AND LIPTON, R. J. 1995. Quantum cryptanalysis of hidden linear functions (extended abstract). In Advances in Cryptology (CRYPTO'95). Lecture Notes in Computer Science, vol. 963. Springer- Verlag, New York, pp. 424-437.]]
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. BRASSARD, G., AND H~YER, P. 1997. An exact quantum polynomial-time algorithm for Simon's problem. In Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems (ISTCS'97). IEEE Computer Society Press, Los Alamitos, Calif., pp. 12-23. (quant-ph/9704027.)]]
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. BRASSARD, G., H~YER,P.,AND TAPP, A. 1997. Quantum algorithm for the collision problem. ACM SIGACT News (Cryptology Column) 28, 14-19. (quant-ph/9705002.)]]
12. BRASSARD, G., H~YER,P.,AND TAPP, A. 1998. Quantum counting. In Proceedings of 25th International Colloquium on Automata Languages and Programming. Lecture Notes in Computer Science, vol. 1443. Springer-Verlag, New York, pp. 820-831. (quant-ph/9805082.)]]
13. BUHRMAN, H., CLEVE, R., AND WIGDERSON, A. 1998. Quantum vs. classical communication and computation. In Proceedings of 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 63-68. (quant-ph/9802040.)]]
14. BUHRMAN, H., CLEVE, R., DE WOLF, R., AND ZALKA,CH. 1999. Bounds for small-error and zeroerror quantum algorithms. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 358-368. (cs.CC/9904019.)]]
15. BUHRMAN, H., D~RR, C., HEILIGMAN, M., H~YER, P., MAGNIEZ, F., SANTHA, M., AND DE WOLF, R. 2001. Quantum algorithms for element distinctness. In Proceedings of 16th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., pp. 131-137. (quant-ph/0007016.)]]
16. BUHRMAN, H., AND DE WOLF, R. 2001. Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci. To appear.]]
17. CLEVE, R. 2000. The query complexity of order-finding. In Proceedings of 15th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., pp. 54-59. (quantph/9911124.)]]
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. VAN,DAM, W. 1998. Quantum oracle interrogation: Getting all information for almost half the price. In Proceedings of 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 362-367. (quant-ph/9805006.)]]
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. FORTNOW, L., AND ROGERS, J. 1999. Complexity limitations on quantum computation. J. Comput. Syst. Sci. 59, 2, 240-252. Conference version in Proceedings of the 13th IEEE conference on Computational Complexity, 1998. (cs.CC/9811023.)]]
28. VON ZUR GATHEN, J., AND ROCHE, J. R. 1997. Polynomials with two values. Combinatorica 17,3, 345-362.]]
29. GROVER, L. K. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of 28th Annual ACM Symposium on Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 212-219. (quant-ph/9605043.)]]
30. GROVER, L. K. 1998. A framework for fast quantum mechanical algorithms. In Proceedings of 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 53-62. (quant-ph/9711043.)]]
31. HAYES, T., KUTIN, S., AND VAN MELKEBEEK, D. 1998. On the quantum complexity of majority. Tech. Rep. TR-98-11. Computer Science Department, Univ. Chicago, Chicago, Ill.]]
32. HOYER, P. 1999. Conjugated operators in quantum algorithms. Phys. Rev. A 59, 5, 3280-3289.]]
33. HOYER, P., NEERBEK, J., AND SHI, Y. 2001. Quantum bounds for ordered searching and sorting. In Proceedings of 28th International Colloquium on Antomata Languages and Programming. Lecture Notes in Computer Science, vol. 2076. Springer-Verlag, New York, pp. 346-357. (quant-ph/0102078.)]]
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. MINSKY, M., AND PAPERT, S. 1968. Perceptrons. MIT Press, Cambridge, Mass., Second, expanded edition 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. MOSCA, M., AND EKERT, A. 1998. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In Proceedings of 1st NASA Quantum Computing and Quantum Communications Confer-ence. Lecture Notes in Computer Science, vol. 1509. Springer-Verlag, New York, pp. 174-188. (quant-ph/ 9903071.)]]
39. NAYAK, A., AND WU, F. 1999. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga., May 1-4). ACM, New York, pp. 384-393. (quant-ph/9804066.)]]
40. NIELSEN,M.A.,AND CHUANG, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, Mass.]]
41. NISAN, N. 1991. CREW PRAMs and decision trees. SIAM J. Comput. 20, 6, 999-1007.]]
42. NISAN, N., AND SZEGEDY, M. 1994. On the degree of Boolean functions as real polynomials. Computat. Complex. 4, 4, 301-313.]]
43. OZHIGOV, Y. 1998. Quantum computer can not speed up iterated applications of a black box. In Proceedings of 1st NASA QCQC conference. Lecture Notes in Computer Science vol. 1509. Springerverlag, New York. (quant-ph/9712051.)]]
44. PATURI, R. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of 24th Annual ACMSymposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 468-474.]]
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. SCHONING, U. 1999. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceedings of 40th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 410-414.]]
50. SERVEDIO,R.A.,AND GORTLER, S. J. 2001. Quantum versus classical learnability. In Proceedings of the 16th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., pp. 138-148. (quant-ph/0007036.)]]
51. SHOR, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM. J. Comput. 26, 5, 1484-1509. (quant-ph/9508027.)]]
52. SIMON, D. 1997. On the power of quantum computation. SIAM J. Comput. 26, 5, 1474-1483.]]
53. VAZIRANI, U. 1998. On the power of quantum computation. Proc. Roy. Soc. London A356. 1759-1768.]]
54. DE WOLF, R. 2000. Characterization of non-deterministic quantum query and quantum communication complexity. In Proceedings of 15th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., pp. 271-278. (cs.CC/0001014.)]]
55. ZALKA,CH. 1999. Grover's quantum searching algorithm is optimal. Phys. Rev. A 60, 2746-2751. (quant-ph/9711070.)]]

Index Terms

• Theory of computation

  • Design and analysis of algorithms

  • Logic

  • Models of computation