A new quantum lower bound method,: with applications to direct product theorems and time-space tradeoffs

ABSTRACT

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.

REFERENCES

• 1: Scott Aaronson , Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM (JACM), v.51 n.4, p.595-605, July 2004 [doi>10.1145/1008731.1008735]
• 2: Scott Aaronson, Limitations of Quantum Advice and One-Way Communication, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.320-332, June 21-24, 2004 [doi>10.1109/CCC.2004.16]
• 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: Andris Ambainis, Polynomial Degree vs. Quantum Query Complexity, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.230, October 11-14, 2003
• 5: Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.22-31, October 17-19, 2004 [doi>10.1109/FOCS.2004.54]
• 6: A. Ambainis. A new quantum lower bound method, with an application to strong direct product theorem for quantum search. quant-ph/0508200, 26 Aug 2005.
• 7: H. Barnum, M. Saks, and M. Szegedy. Quantum query complexity and semi-definite programming. In Proc. of 18th Conference on Computational Complexity, p. 179--193, 2003.
• 8: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001 [doi>10.1145/502090.502097]
• 9: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 10: M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4--5):493--505, 1998.
• 11: G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, p. 53--74. 2002.
• 12: 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
• 13: 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]
• 14: Don Coppersmith , T. J. Rivlin, The growth of polynomials bounded at equally spaced points, SIAM Journal on Mathematical Analysis, v.23 n.4, p.970-983, July 1992 [doi>10.1137/0523054]
• 15: E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. A limit on the speed of quantum computation in determining parity. Physical Review Letters, 81:5442--5444, 1998.
• 16: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 17: 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]
• 18: P. Hoyer, M. Mosca, and R. de Wolf. Quantum search on bounded-error inputs. In Proc. of 30th ICALP'03, volume 2719 of LNCS, p. 291--299. Springer, 2003.
• 19: P. Hoyer, J. Neerbek, and Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34(4):429--448, 2002.
• 20: Hartmut Klauck , Robert Spalek , Ronald de Wolf, Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.12-21, October 17-19, 2004 [doi>10.1109/FOCS.2004.52]
• 21: Sophie Laplante , Frederic Magniez, Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.294-304, June 21-24, 2004 [doi>10.1109/CCC.2004.17]
• 22: Frédéric Magniez , Miklos Santha , Mario Szegedy, Quantum algorithms for the triangle problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 23: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 24: 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]
• 25: 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]
• 26: A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, mathematics, 67(1):159--176, 2003.
• 27: T. J. Rivlin. Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory. Wiley-Interscience, second edition, 1990.
• 28: Ronen Shaltiel, Towards Proving Strong Direct Product Theorems, Proceedings of the 16th Annual Conference on Computational Complexity, p.107, June 18-21, 2001
• 29: R. Špalek and M. Szegedy. All quantum adversary methods are equivalent. Theory of Computing, 2(1):1--18, 2006.
• 30: S. Zhang. On the power of Ambainis's lower bounds. Theoretical Computer Science,339(2--3):241--256,2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Keywords:
direct product theorems, lower bounds, quantum computing, time-space tradeoffs