LIPIcs.ITCS.2023.37.pdf
- Filesize: 0.89 MB
- 22 pages
Document
Quantum Algorithms and the Power of Forgetting
Authors
Andrew M. Childs 
,
Matthew Coudron ,
Amin Shiraz Gilani
-
Part of:
Volume:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
File
Document Identifiers
Author Details
- Joint Center for Quantum Information and Computer Science, College Park, MD, USA
- Department of Computer Science, University of Maryland, College Park, MD, USA
- Institute for Advanced Computer Studies, University of Maryland, MD, USA
- Joint Center for Quantum Information and Computer Science, College Park, MD, USA
- National Institute of Standards and Technology, Gaithersburg, MD, USA
- Department of Computer Science, University of Maryland, College Park, MD, USA
Acknowledgements
We thank Matt Kovacs-Deak for many helpful discussions.
Cite AsGet BibTex
Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum Algorithms and the Power of Forgetting. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.37
https://doi.org/10.4230/LIPIcs.ITCS.2023.37
Abstract
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm [Andrew M. Childs et al., 2003]. Given the name of a special entrance vertex, a quantum walk can find another distinguished exit vertex using polynomially many queries, though without finding any particular path from entrance to exit. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from entrance to exit. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the entrance, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.
Subject Classification
ACM Subject Classification
- Theory of computation → Quantum computation theory
Keywords
- Quantum algorithms
- quantum query complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4), 2021. URL: https://doi.org/10.1145/3488559.
- Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, pages 902-915, 2020. URL: https://doi.org/10.1145/3357713.3384291.
- Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 59-68, 2003. URL: https://doi.org/10.1145/780542.780552.
- Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum algorithms and the power of forgetting. URL: http://arxiv.org/abs/2211.12447.
- Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pages 526-536, 2000. URL: https://doi.org/10.1109/SFCS.2000.892140.
- Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, pages 889-901, 2020. URL: https://doi.org/10.1145/3357713.3384269.
- Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song. A quantum algorithm for computing the unit group of an arbitrary degree number field. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 293-302, 2014. URL: https://doi.org/10.1145/2591796.2591860.
- Sean Hallgren. Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. Journal of the ACM, 54(1):4, 2007. Preliminary version in STOC 2002. URL: https://doi.org/10.1145/1206035.1206039.
- Kiran S. Kedlaya. Quantum computation of zeta functions of curves. Computational Complexity, 15(1):1-19, 2006. URL: https://doi.org/10.1007/s00037-006-0204-7.
-
Dénes Kőnig. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére. Matematikai és Természettudományi Értesítő, 34:104-119, 1916.
- Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073-1078, 1996. URL: https://doi.org/10.1126/science.273.5278.1073.
- Ansis Rosmanis. Quantum snake walk on graphs. Physical Review A, 83(2):022304, 2011. URL: https://doi.org/10.1103/PhysRevA.83.022304.
- Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. Preliminary version in FOCS 1994. URL: https://doi.org/10.1137/S0097539795293172.
- Daniel R. Simon. On the power of quantum computation. SIAM J. Comput., 26(5):1474-1483, 1997. Preliminary version in FOCS 1994. URL: https://doi.org/10.1137/S0097539796298637.