Quantum and classical query complexities of local search are polynomially related
From MaRDI portal
Publication:5896965
DOI10.1007/s00453-008-9169-zzbMath1191.68310OpenAlexW2008758668MaRDI QIDQ5896965
Publication date: 31 August 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9169-z
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of Ambainis lower bounds
- Erratum to: Local optimization on graphs
- On total functions, existence theorems and computational complexity
- Enhanced algorithms for local search
- Minimization algorithms and random walk on the d-cube
- How easy is local search?
- Local optimization on graphs
- A lower bound for quantum search of an ordered list
- Dividing and conquering the square
- Quantum complexities of ordered searching, sorting, and element distinctness
- Polynomial degree vs. quantum query complexity
- A new quantum lower bound method,
- New upper and lower bounds for randomized and quantum local search
- Quantum lower bounds for the collision and the element distinctness problems
- On the Complexity of 2D Discrete Fixed Point Problem
- Rapid solution of problems by quantum computation
- On the Power of Quantum Computation
- Strengths and Weaknesses of Quantum Computing
- Quantum lower bounds by polynomials
- Lower Bounds for Local Search by Quantum Arguments
- Quantum Query Complexity of Some Graph Problems
- Fundamentals of Computation Theory
- Quantum lower bounds by quantum arguments
This page was built for publication: Quantum and classical query complexities of local search are polynomially related
