On the quantum query complexity of local search in two and three dimensions
From MaRDI portal
Publication:835649
DOI10.1007/s00453-008-9170-6zbMath1192.68283OpenAlexW2032556376MaRDI QIDQ835649
Xiaoming Sun, Andrew Chi-Chih Yao
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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Path search in the pyramid and in other graphs
Cites Work
- On the power of Ambainis lower bounds
- Enhanced algorithms for local search
- Minimization algorithms and random walk on the d-cube
- How easy is local search?
- Local optimization on graphs
- Theorems in the additive theory of numbers
- Polynomial degree vs. quantum query complexity
- Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
- New upper and lower bounds for randomized and quantum local search
- On algorithms for discrete and approximate brouwer fixed points
- Estimates for the concentration function of combinatorial number theory and probability
- Strengths and Weaknesses of Quantum Computing
- Über ein Problem von Erdös und Moser
- Lower Bounds for Local Search by Quantum Arguments
- Fundamentals of Computation Theory
- Quantum lower bounds by quantum arguments
- Quantum and classical query complexities of local search are polynomially related
This page was built for publication: On the quantum query complexity of local search in two and three dimensions
