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(Ts6) 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.
- ALONSO, L., REINGOLD,E.M.,AND SCHOTT, R. 1993. Determining the majority. Inf. Proc. Lett. 47,5, 253-255.]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.)]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- BUHRMAN, H., AND DE WOLF, R. 2001. Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci. To appear.]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- CLEVE, R., EKERT, A., MACCHIAVELLO, C., AND MOSCA, M. 1998. Quantum algorithms revisited. Proc. Roy. Soc. London A454, 339-354. (quant-ph/9708016.)]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- VAN DAM W., AND HALLGREN, S. 2000. Efficient quantum algorithms for shifted quadratic character problems. (quant-ph/0011067.)]]Google Scholar
- DEUTSCH, D., AND JOZSA, R. 1992. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A439, 553-558.]]Google ScholarCross Ref
- EHLICH, H., AND ZELLER, K. 1964. Schwankung von Polynomen zwischen Gitterpunkten. Math. Z. 86, 41-44.]]Google ScholarCross Ref
- 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.]]Google ScholarCross Ref
- 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.)]]Google ScholarCross Ref
- FARHI, E., GOLDSTONE, J., GUTMANN, S., AND SIPSER, M. 1999b. Invariant quantum algorithms for insertion into an ordered list. (quant-ph/9901059.)]]Google Scholar
- 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.]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- VON ZUR GATHEN, J., AND ROCHE, J. R. 1997. Polynomials with two values. Combinatorica 17,3, 345-362.]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- HOYER, P. 1999. Conjugated operators in quantum algorithms. Phys. Rev. A 59, 5, 3280-3289.]]Google ScholarCross Ref
- 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.)]] Google ScholarDigital Library
- JOZSA, R. 1991. Characterizing classes of functions computable by quantum parallelism. Proc. Roy. Soc. London A435, 563-574.]]Google ScholarCross Ref
- KITAEV, A. Y. 1995. Quantum measurements and the Abelian stabilizer problem. (quant-ph/9511026.)]]Google Scholar
- MINSKY, M., AND PAPERT, S. 1968. Perceptrons. MIT Press, Cambridge, Mass., Second, expanded edition 1988.]] Google ScholarDigital Library
- MOSCA, M. 1998. Quantum searching, counting and amplitude amplification by eigenvector analysis. In MFCS'98 Workshop on Randomized Algorithms, pp. 90-100.]]Google Scholar
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- NIELSEN,M.A.,AND CHUANG, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, Mass.]] Google ScholarDigital Library
- NISAN, N. 1991. CREW PRAMs and decision trees. SIAM J. Comput. 20, 6, 999-1007.]] Google ScholarDigital Library
- NISAN, N., AND SZEGEDY, M. 1994. On the degree of Boolean functions as real polynomials. Computat. Complex. 4, 4, 301-313.]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 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.]]Google ScholarDigital Library
- SAKS, M. E., AND WERMAN, M. 1991. On computing majority by comparisons. Combinatorica 11,4, 383-387.]]Google ScholarCross Ref
- 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.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- 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.)]] Google ScholarDigital Library
- SIMON, D. 1997. On the power of quantum computation. SIAM J. Comput. 26, 5, 1474-1483.]] Google ScholarDigital Library
- VAZIRANI, U. 1998. On the power of quantum computation. Proc. Roy. Soc. London A356. 1759-1768.]]Google Scholar
- 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.)]] Google ScholarDigital Library
- ZALKA,CH. 1999. Grover's quantum searching algorithm is optimal. Phys. Rev. A 60, 2746-2751. (quant-ph/9711070.)]]Google ScholarCross Ref
Index Terms
- Quantum lower bounds by polynomials
Recommendations
Quantum lower bounds for the collision and the element distinctness problems
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f(i) = f(j), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of ...
Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher
Computing and CombinatoricsAbstractThe Even-Mansour (EM) cipher is one of the famous constructions for a block cipher. Kuwakado and Morii demonstrated that a quantum adversary can recover its n-bit secret keys only with nonadaptive quantum queries. While the security of the EM ...
Quantum lower bound for recursive Fourier sampling
We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its ...
Comments