Lower bounds for local search by quantum arguments

ABSTRACT

The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube 0,1ⁿ, we show a lower bound of Ω(2^n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2^n/2/n²) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension d≥3.

REFERENCES

• 1: Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509999]
• 2: D. Aharonov and O. Regev. Approximating the shortest and closest vector in a lattice to within √n are in NP ∩ coNP, unpublished.
• 3: D. Aldous. Minimization algorithms and random walk on the d-cube, Annals of Probability 11(2):403--413, 1983.
• 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 lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002 [doi>10.1006/jcss.2002.1826]
• 6: T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question, SIAM J. Comput. 4:431--442, 1975.
• 7: 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]
• 8: 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]
• 9: 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
• 10: 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]
• 11: R. Diestel. Graph Theory (2nd edition), Springer-Verlag, 2000.
• 12: S. Droste, T. Jansen, and I. Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization, ECCC TR03-048, 2003.
• 13: C. Dürr and P. Høyer. A quantum algorithm for finding the minimum, 1996. quant-ph/9607014.
• 14: E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292:472--476, 2001. quant-ph/0104129.
• 15: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 16: Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780560]
• 17: Donna C. Llewellyn , Craig A. Tovey, Dividing and conquering the square, Discrete Applied Mathematics, v.43 n.2, p.131-153, May 1993 [doi>10.1016/0166-218X(93)90004-8]
• 18: Donna Crystal Llewellyn , Craig Tovey , Michael Trick, Local optimization on graphs, Discrete Applied Mathematics, v.23 n.2, p.157-178, May 1989 [doi>10.1016/0166-218X(89)90025-5]
• 19: Nimrod Megiddo , Christos H. Papadimitriou, On total functions, existence theorems and computational complexity, Theoretical Computer Science, v.81 n.2, p.317-324, April 30 1991 [doi>10.1016/0304-3975(91)90200-L]
• 20: C. H. Papadimitriou. Talk at UC Berkeley, February 6, 2003.
• 21: Miklos Santha , Mario Szegedy, Quantum and classical query complexities of local search are polynomially related, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007427]
• 22: Yaoyun Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.513-519, November 16-19, 2002

INDEX TERMS

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

General Terms:
Theory

Keywords:
PLS, local optima, local search, quantum computing, query complexity (black box, decision tree)