Lower Bounds for Local Search by Quantum Arguments

DOI10.1137/S0097539704447237MaRDI QIDQ5470715zbMATH OpenOpenAlexFDO

Authors 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

decision treeslocal optimalocal searchpolynomial local searchquantum computingquery complexityrandom walks

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for local search by quantum arguments
• Tight bounds for randomized and quantum local search
• New upper and lower bounds for randomized and quantum local search
• Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
• Quantum and randomized lower bounds for local search on vertex-transitive graphs
• On the quantum query complexity of local search in two and three dimensions
• Quantum and classical query complexities of local search are polynomially related
• Quantum and classical query complexities of local search are polynomially related
• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments

Cited in

(23)

• Dividing and conquering the square
• Evolutionary algorithms for quantum computers
• Exponential lower bounds for polytopes in combinatorial optimization
• New upper and lower bounds for randomized and quantum local search
• Quantum and randomized lower bounds for local search on vertex-transitive graphs
• All classical adversary methods are equivalent for total functions
• Quantum Separation of Local Search and Fixed Point Computation
• Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
• Tight bounds for randomized and quantum local search
• Lower bounds for local search by quantum arguments
• Lower bounds of a quantum search for an extreme point
• 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
• Quantum and classical query complexities of local search are polynomially related
• scientific article; zbMATH DE number 7716603 (Why is no real title available?)
• How to trap a gradient flow
• Total NP search problems with abundant solutions
• The randomized query complexity of finding a Tarski fixed point on the Boolean hypercube
• Tarski lower bounds from multi-dimensional herringbones
• On the quantum query complexity of local search in two and three dimensions
• On the black-box complexity of Sperner's Lemma
• Quantum separation of local search and fixed point computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470715)