On the quantum query complexity of local search in two and three dimensions
DOI10.1007/S00453-008-9170-6zbMATH Open1192.68283OpenAlexW2032556376MaRDI QIDQ835649FDOQ835649
Andrew Chi-Chih Yao, Xiaoming Sun
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-9170-6
Recommendations
- Quantum and classical query complexities of local search are polynomially related
- Quantum and classical query complexities of local search are polynomially related
- Tight bounds for randomized and quantum local search
- Lower bounds for local search by quantum arguments
- Lower Bounds for Local Search by Quantum Arguments
- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- Quantum and randomized lower bounds for local search on vertex-transitive graphs
- New upper and lower bounds for randomized and quantum local search
- On exact quantum query complexity
- Quantum Separation of Local Search and Fixed Point Computation
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Cites Work
- Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
- Estimates for the concentration function of combinatorial number theory and probability
- Strengths and Weaknesses of Quantum Computing
- How easy is local search?
- Theorems in the additive theory of numbers
- Über ein Problem von Erdös und Moser
- Polynomial degree vs. quantum query complexity
- Quantum lower bounds by quantum arguments
- Local optimization on graphs
- Minimization algorithms and random walk on the d-cube
- On algorithms for discrete and approximate brouwer fixed points
- On the power of Ambainis lower bounds
- New upper and lower bounds for randomized and quantum local search
- Enhanced algorithms for local search
- Lower Bounds for Local Search by Quantum Arguments
- Fundamentals of Computation Theory
- Quantum and classical query complexities of local search are polynomially related
Cited In (8)
- Path search in the pyramid and in other graphs
- Lower Bounds for Local Search by Quantum Arguments
- Quantum search in a possible three-dimensional complex subspace
- Quantum and classical query complexities of local search are polynomially related
- How to trap a gradient flow
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- On the deterministic complexity of searching local maxima
- Impact of global and local interaction on quantum spatial search on chimera graph
This page was built for publication: On the quantum query complexity of local search in two and three dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835649)
