Lower bounds for local search by quantum arguments

DOI10.1145/1007352.1007358zbMath1192.68256OpenAlexW2067046685WikidataQ130928292 ScholiaQ130928292MaRDI QIDQ3580990

Scott Aaronson

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.1007358

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Quantum separation of local search and fixed point computation ⋮ Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ⋮ Ranking-based black-box complexity ⋮ Polynomial degree vs. quantum query complexity ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ On the power of Ambainis lower bounds ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Enhanced algorithms for local search

This page was built for publication: Lower bounds for local search by quantum arguments