Hybrid Quantum-classical Search Algorithms
ACM Transactions on Quantum Computing · 30.06.2024 · 5 (2) · 1-18
DOI: 10.1145/3648573 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Quantum Computing, online erschienen am 23.04.2024. Verfasst von Ansis Rosmanis. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 21 Literaturangaben. Gefördert von: JSPS KAKENHI, MEXT Quantum Leap Flagship Program.
Abstract (Originalsprache)
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.
Förderung
- JSPS KAKENHI
- MEXT Quantum Leap Flagship Program
Zitieren
APA
Rosmanis, A. (2024). Hybrid Quantum-classical Search Algorithms. ACM Transactions on Quantum Computing, 5(2), 1-18. https://doi.org/10.1145/3648573
Vancouver
Rosmanis A. Hybrid Quantum-classical Search Algorithms. ACM Transactions on Quantum Computing. 2024;5(2):1-18. doi:10.1145/3648573
BibTeX
@article{Rosmanis2024,
author = {Rosmanis, Ansis},
title = {Hybrid Quantum-classical Search Algorithms},
journal = {ACM Transactions on Quantum Computing},
year = {2024},
volume = {5},
number = {2},
pages = {1--18},
doi = {10.1145/3648573}
}
EUVIMED