Tight bounds for randomized and quantum local search
DOI10.1137/06066775XzbMATH Open1194.68119OpenAlexW2070060459MaRDI QIDQ3575155FDOQ3575155
Authors: Shengyu Zhang 
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/06066775x
Recommendations
- New upper and lower bounds for randomized and quantum local search
- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- Lower bounds for local search by quantum arguments
- Quantum and randomized lower bounds for local search on vertex-transitive graphs
- Lower Bounds for Local Search by Quantum Arguments
optimizationrandomized algorithmlocal searchquantum algorithmquantum query complexityrandomized decision tree complexity
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Cited In (16)
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Lower Bounds for Local Search by Quantum Arguments
- Quantum and classical query complexities of local search are polynomially related
- Quantum and classical query complexities of local search are polynomially related
- Enhanced algorithms for local search
- Quantum separation of local search and fixed point computation
- 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 search of spatial regions
- Query complexity of approximate equilibria in anonymous games
- New upper and lower bounds for randomized and quantum local search
- Lower bounds for local search by quantum arguments
- On barren plateaus and cost function locality in variational quantum algorithms
- Quantum Separation of Local Search and Fixed Point Computation
- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- TFNP: an update
This page was built for publication: Tight bounds for randomized and quantum local search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575155)
