Quantum and classical query complexities of local search are polynomially related
From MaRDI portal
Publication:5901075
DOI10.1145/1007352.1007427zbMath1192.68266OpenAlexW2015919213WikidataQ130927173 ScholiaQ130927173MaRDI QIDQ5901075
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007427
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Related Items (6)
On the quantum query complexity of local search in two and three dimensions ⋮ On the black-box complexity of Sperner's Lemma ⋮ Quantum separation of local search and fixed point computation ⋮ Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ⋮ Enhanced algorithms for local search ⋮ Combinatorial auctions with endowment effect
This page was built for publication: Quantum and classical query complexities of local search are polynomially related
