Quantum Separation of Local Search and Fixed Point Computation

DOI10.1007/978-3-540-69733-6_18zbMATH Open1148.68382OpenAlexW1755121999MaRDI QIDQ3511325FDOQ3511325

Authors: Xi Chen, Xiaoming Sun, Shang-Hua Teng 

Publication date: 10 July 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_18

Recommendations

• Quantum separation of local search and fixed point computation
• Tight bounds for randomized and quantum local search
• Lower bounds for local search by quantum arguments
• Lower Bounds for Local Search by Quantum Arguments
• New upper and lower bounds for randomized and quantum local search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Cited In (5)

• On the black-box complexity of Sperner's Lemma
• Quantum separation of local search and fixed point computation
• On the quantum query complexity of local search in two and three dimensions
• Engineering local optimality in quantum Monte Carlo algorithms
• On barren plateaus and cost function locality in variational quantum algorithms

This page was built for publication: Quantum Separation of Local Search and Fixed Point Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511325)