More Web Proxy on the site http://driver.im/

Article

Lower bounds for local search by quantum arguments

Author:

Scott AaronsonAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 465 - 474

https://doi.org/10.1145/1007352.1007358

Published: 13 June 2004 Publication History

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]

S. Aaronson. Quantum lower bound for the collision problem, Proc. ACM STOC, pp. 635--642, 2002. quant-ph/0111102.

Digital Library

[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]

A. Ambainis. Polynomial degree vs. quantum query complexity, Proc. IEEE FOCS, pp. 230--239, 2003. quant-ph/0305028.

Digital Library

[5]

A. Ambainis. Quantum lower bounds by quantum arguments, J. Comput. Sys. Sci. 64:750--767, 2002. Earlier version in STOC 2000. quant-ph/0002066.

Digital Library

[6]

T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question, SIAM J. Comput. 4:431--442, 1975.

Digital Library

[7]

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials, J. ACM 48(4):778--797, 2001. Earlier version in FOCS 1998. quant-ph/9802049.

Digital Library

[8]

C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing, SIAM J. Comput. 26(5):1510--1523, 1997. quant-ph/9701001.

Digital Library

[9]

H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for small-error and zero-error quantum algorithms, Proc. IEEE FOCS, pp. 358--368, 1999. cs. CC/9904019.

Digital Library

[10]

H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey, Theoretical Comput. Sci. 288:21--43, 2002.

Digital Library

[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.

Digital Library

[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]

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis. How easy is local search?, J. Comput. Sys. Sci. 37:79--100, 1988.

Digital Library

[16]

I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proc. ACM STOC, pp. 106--115, 2003. quant-ph/0208062.

Digital Library

[17]

D. C. Llewellyn and C. Tovey. Dividing and conquering the square, Discrete Appl. Math 43:131--153, 1993.

Digital Library

[18]

D. C. Llewellyn, C. Tovey, and M. Trick. Local optimization on graphs, Discrete Appl. Math 23:157--178, 1989. Erratum: 46:93--94, 1993.

Digital Library

[19]

N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems, and computational complexity, Theoret. Comp. Sci. 81:317--324, 1991.

Digital Library

[20]

C. H. Papadimitriou. Talk at UC Berkeley, February 6, 2003.

[21]

M. Santha and M. Szegedy. Quantum and classical query complexities of local search are polynomially related, this Proceedings, 2004.

Digital Library

[22]

Y. Shi. Quantum lower bounds for the collision and the element distinctness problems, Proc. IEEE FOCS, pp. 513--519, 2002. quant-ph/0112086.

Digital Library

Cited By

Tang YSu S(2014)Application of Grover's Quantum Search Algorithm to Solve the Transcendental Logarithm ProblemProceedings of the 2014 Tenth International Conference on Computational Intelligence and Security10.1109/CIS.2014.166(445-449)Online publication date: 15-Nov-2014
https://dl.acm.org/doi/10.1109/CIS.2014.166
Fiorini SMassar SPokutta STiwary Hde Wolf RKarloff HPitassi T(2012)Linear vs. semidefinite extended formulationsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2213988(95-106)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2213988
Liu L(2011)Parallel Search Optimization for Storage VirtualizationSecurity and Policy Driven Computing10.1201/b10472-6(103-133)Online publication date: 18-Jan-2011
https://doi.org/10.1201/b10472-6
Show More Cited By

Index Terms

Lower bounds for local search by quantum arguments
1. Theory of computation
  1. Models of computation

Recommendations

Quantum lower bounds by polynomials

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 ...
Lower Bounds for Local Search by Quantum Arguments

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 $\left\{0,1\right\}^n$, we show a lower bound of $\Omega\left(2^{n/...
New upper and lower bounds for randomized and quantum local search
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
471
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang YSu S(2014)Application of Grover's Quantum Search Algorithm to Solve the Transcendental Logarithm ProblemProceedings of the 2014 Tenth International Conference on Computational Intelligence and Security10.1109/CIS.2014.166(445-449)Online publication date: 15-Nov-2014
https://dl.acm.org/doi/10.1109/CIS.2014.166
Fiorini SMassar SPokutta STiwary Hde Wolf RKarloff HPitassi T(2012)Linear vs. semidefinite extended formulationsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2213988(95-106)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2213988
Liu L(2011)Parallel Search Optimization for Storage VirtualizationSecurity and Policy Driven Computing10.1201/b10472-6(103-133)Online publication date: 18-Jan-2011
https://doi.org/10.1201/b10472-6
Chen XSun XTeng S(2010)Quantum Separation of Local Search and Fixed Point ComputationAlgorithmica10.5555/3118243.311859556:3(364-382)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.5555/3118243.3118595
Kerenidis I(2009)Quantum multiparty communication complexity and circuit lower boundsMathematical Structures in Computer Science10.1017/S096012950800726319:1(119-132)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1017/S0960129508007263
Chen XSun XTeng S(2009)Quantum Separation of Local Search and Fixed Point ComputationAlgorithmica10.1007/s00453-009-9289-056:3(364-382)Online publication date: 25-Feb-2009
https://doi.org/10.1007/s00453-009-9289-0
Dinh HRussell A(2008)Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive GraphsProceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques10.1007/978-3-540-85363-3_31(385-401)Online publication date: 25-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85363-3_31
Chen XSun XTeng S(2008)Quantum Separation of Local Search and Fixed Point ComputationProceedings of the 14th annual international conference on Computing and Combinatorics10.1007/978-3-540-69733-6_18(170-179)Online publication date: 27-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69733-6_18
Ju YTsai IKuo S(2007)Quantum Circuit Design and Analysis for Database Search ApplicationsIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2007.90784554:11(2552-2563)Online publication date: Nov-2007
https://doi.org/10.1109/TCSI.2007.907845
(2007)Author IndexProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2007.14(735-736)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1109/FOCS.2007.14
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents