On the quantum query complexity of local search in two and three dimensions

DOI10.1007/S00453-008-9170-6MaRDI QIDQ835649zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

local searchquantum query complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

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

Cites work

• Enhanced algorithms for local search
• Estimates for the concentration function of combinatorial number theory and probability
• Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
• Fundamentals of Computation Theory
• How easy is local search?
• Local optimization on graphs
• Lower Bounds for Local Search by Quantum Arguments
• Minimization algorithms and random walk on the d-cube
• New upper and lower bounds for randomized and quantum local search
• On algorithms for discrete and approximate brouwer fixed points
• On the power of Ambainis lower bounds
• Polynomial degree vs. quantum query complexity
• Quantum and classical query complexities of local search are polynomially related
• Quantum lower bounds by quantum arguments
• Strengths and Weaknesses of Quantum Computing
• Theorems in the additive theory of numbers
• Über ein Problem von Erdös und Moser

Cited in

(8)

• Path search in the pyramid and in other graphs
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• 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
• 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)