Quantum and classical query complexities of local search are polynomially related

ABSTRACT

Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E) a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex x ∈ V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form "what is the value of f on x?" We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous[4] Ald and Aaronson [1] Aar and solves the main open problem in Aar.

REFERENCES

• 1: Scott Aaronson, Lower bounds for local search by quantum arguments, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.465-474, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007358]
• 2: 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]
• 3: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 4: D. Aldous. Minimization algorithms and random walk on the d-cube, Annals of probability 11(2), pp. 403--413, 1983.
• 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: H. Barnum, M. Saks, and M. Szegedy. Quantum decision trees and semidefinite programming, in Proc. of the 18th IEEE Conference on Computational Complexity, pp. 179--193, 2003.
• 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 , Ronald de Wolf, A lower bound for quantum search of an ordered list, Information Processing Letters, v.70 n.5, p.205-209, June 21, 1999 [doi>10.1016/S0020-0190(99)00069-1]
• 10: D. Deutsch, and R. Jozsa. Rapid solution of problems by quantum computation, in Proc. of the Royal Society A, volume 439,1985.
• 11: C. Dürr, and P. Høyer. A quantum algorithm for finding the minimum, quant-ph/9607014, 1996.
• 12: 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]
• 13: P. Høyer, J. Neerbek, and Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness, Algorithmica 34(4), pp. 429--448, 2002.
• 14: 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]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: 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]
• 19: 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
• 20: 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]
• 21: Yves Verhoeven. Local optimization over grids, Unpublished manuscript.
• 22: C. Zalka. Grover's quantum searching algorithm is optimal, Physical Review A 60, pp. 2746--2751, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Theory

Keywords:
PLO, decision trees, local optimization, neighborhood structure, quantum computation, query model