Lower Bounds for Local Search by Quantum Arguments

DOI10.1137/S0097539704447237zbMath1099.68034OpenAlexW3023447009MaRDI QIDQ5470715

Scott Aaronson

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704447237

zbMATH Keywords

random walkslocal searchquantum computingdecision treesquery complexitylocal optimapolynomial local search

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

On the quantum query complexity of local search in two and three dimensions ⋮ On the black-box complexity of Sperner's Lemma ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Evolutionary algorithms for quantum computers ⋮ Unnamed Item ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization

This page was built for publication: Lower Bounds for Local Search by Quantum Arguments