Lower Bounds for Local Search by Quantum Arguments
From MaRDI portal
Publication:5470715
DOI10.1137/S0097539704447237zbMath1099.68034MaRDI QIDQ5470715
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
random walks; local search; quantum computing; decision trees; query complexity; local optima; polynomial local search
60G50: Sums of independent random variables; random walks
81P68: Quantum computation
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search, Quantum and classical query complexities of local search are polynomially related, Unnamed Item, On the quantum query complexity of local search in two and three dimensions, On the black-box complexity of Sperner's Lemma, Evolutionary algorithms for quantum computers, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, All Classical Adversary Methods are Equivalent for Total Functions