Document Open Access Logo

A Unified Framework of Quantum Walk Search

Authors Simon Apers, András Gilyén, Stacey Jeffery

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.6.pdf
  • Filesize: 0.64 MB
  • 13 pages

Document Identifiers

Author Details

Simon Apers
  • Université libre de Bruxelles, Brussels, Belgium
  • CWI, Amsterdam, The Netherlands
András Gilyén
  • California Institute of Technology, Pasadena, CA, USA
Stacey Jeffery
  • QuSoft, CWI, Amsterdam, The Netherlands

Funding

  • Apers, Simon: Work done while being partially supported by the CWI-Inria International Lab and the Dutch Research Council (NWO) through QuantERA ERA-NET Cofund project QuantAlgo 680-91-034.
  • Gilyén, András: Funding provided by Samsung Electronics Co., Ltd., for the project "The Computational Power of Sampling on Quantum Computers", as well as by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907).
  • Jeffery, Stacey: Supported by an NWO Veni Innovational Research Grant under project number 639.021.752, an NWO WISE Grant, and QuantERA project QuantAlgo 680-91-03. SJ is a CIFAR Fellow in the Quantum Information Science Program.

Cite AsGet BibTex

Simon Apers, András Gilyén, and Stacey Jeffery. A Unified Framework of Quantum Walk Search. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.6

Abstract

Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Algorithms
  • Quantum Walks
  • Graph Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Andris Ambainis. Quantum walk algorithm for element distinctness. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 22-31, 2004. http://arxiv.org/abs/quant-ph/0311001, URL: https://doi.org/10.1109/FOCS.2004.54.
  2. Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC), page 412–424, 2020. http://arxiv.org/abs/1903.07493, URL: https://doi.org/10.1145/3357713.3384252.
  3. Andris Ambainis, Julia Kempe, and Alexander Rivosh. Coins make quantum walks faster. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1099-1108, 2005. URL: http://arxiv.org/abs/quant-ph/0402107.
  4. Andris Ambainis and Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proceedings of the 49th ACM Symposium on the Theory of Computing (STOC), page 989–1002, 2017. http://arxiv.org/abs/1704.06774, URL: https://doi.org/10.1145/3055399.3055444.
  5. Simon Apers, András Gilyén, and Stacey Jeffery. A unified framework of quantum walk search, 2019. URL: http://arxiv.org/abs/1912.04233.
  6. Simon Apers and Alain Sarlette. Quantum fast-forwarding: Markov chains and graph property testing. Quantum Information and Computation, 19(3&4):181-213, 2019. http://arxiv.org/abs/1804.02321, URL: https://doi.org/10.26421/QIC19.3-4.
  7. Aleksandrs Belovs. Quantum walks and electric networks, 2013. URL: http://arxiv.org/abs/1302.3143.
  8. Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez. Time-efficient quantum walks for 3-distinctness. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 105-122, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_10.
  9. Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. Quantum algorithms for the subset-sum problem. In Proceedings of the 5th International Conference on Post-Quantum Cryptography (PQCrypto), pages 16-33, 2013. URL: https://doi.org/10.1007/978-3-642-38616-9_2.
  10. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 792-809, 2015. http://arxiv.org/abs/1501.01715, URL: https://doi.org/10.1109/FOCS.2015.54.
  11. Harry Buhrman and Robert Špalek. Quantum verification of matrix products. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 880-889, 2006. URL: http://arxiv.org/abs/quant-ph/0409035.
  12. Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12(11&12):901-924, 2012. http://arxiv.org/abs/1202.5822, URL: https://doi.org/10.26421/QIC12.11-12.
  13. Cǎtǎlin Dohotaru and Peter Høyer. Controlled quantum amplification. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 18:1-18:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.18.
  14. Alexander Helm and Alexander May. Subset sum quantumly in 1.17ⁿ. In Proceedings of the 13th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), pages 5:1-5:15, 2018. URL: https://doi.org/10.4230/LIPIcs.TQC.2018.5.
  15. Michael Jarret and Kianna Wan. Improved quantum backtracking algorithms using effective resistance estimates. Physical Review A, 97(2):022337, 2018. http://arxiv.org/abs/1711.05295, URL: https://doi.org/10.1103/PhysRevA.97.022337.
  16. Stacey Jeffery, Robin Kothari, and Frédéric Magniez. Nested quantum walks with quantum data structures. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1474-1485, 2012. URL: http://arxiv.org/abs/1210.1199.
  17. Ghazal Kachigar and Jean-Pierre Tillich. Quantum information set decoding algorithms. In Proceedings of the 8th International Conference on Post-Quantum Cryptography (PQCrypto), pages 69-89, 2017. http://arxiv.org/abs/1703.00263, URL: https://doi.org/10.1007/978-3-319-59879-6_5.
  18. Elena Kirshanova. Improved quantum information set decoding. In Proceedings of the 9th International Conference on Post-Quantum Cryptography (PQCrypto), pages 507-527, 2018. http://arxiv.org/abs/1808.00714, URL: https://doi.org/10.1007/978-3-319-79063-3_24.
  19. Hari Krovi, Frédéric Magniez, Maris Ozols, and Jérémie Roland. Quantum walks can find a marked element on any graph. Algorithmica, 74(2):851-907, 2016. http://arxiv.org/abs/1002.2419, URL: https://doi.org/10.1007/s00453-015-9979-8.
  20. Frédéric Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha. On the hitting times of quantum versus random walks. Algorithmica, 63(1):91-116, 2012. Earlier version in SODA'09. https://arxiv.org/abs/0808.0084. URL: https://doi.org/10.1007/s00453-011-9521-6.
  21. Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 37(2):413-427, 2007. http://arxiv.org/abs/quant-ph/0310134, URL: https://doi.org/10.1137/050643684.
  22. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, 2011. Earlier version in STOC'07. https://arxiv.org/abs/quant-ph/0608026. URL: https://doi.org/10.1137/090745854.
  23. Ashley Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14(15):1-24, 2018. http://arxiv.org/abs/1509.02374, URL: https://doi.org/10.4086/toc.2018.v014a015.
  24. Stephen Piddock. Quantum walk search algorithms and effective resistance, 2019. URL: http://arxiv.org/abs/1912.04196.
  25. Márió Szegedy. Quantum speed-up of Markov chain based algorithms. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 32-41, 2004. http://arxiv.org/abs/quant-ph/0401053, URL: https://doi.org/10.1109/FOCS.2004.53.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact