Document Open Access Logo

Quantum Algorithm for Path-Edge Sampling

Authors Stacey Jeffery, Shelby Kimmel , Alvaro Piedrafita

PDF
Thumbnail PDF

File

LIPIcs.TQC.2023.5.pdf
  • Filesize: 1 MB
  • 28 pages

Document Identifiers

Author Details

Stacey Jeffery
  • QuSoft and CWI, Amsterdam, The Netherlands
Shelby Kimmel
  • Middlebury College, VT, USA
Alvaro Piedrafita
  • QuSoft and CWI, Amsterdam, The Netherlands

Funding

Shelby Kimmel and Stacey Jeffery: sponsored by the U.S. Army Research Office and this work was accomplished under Grant Number W911NF-20-1-0327. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
  • Jeffery, Stacey: supported by NWO Klein project number OCENW.Klein.061, and the European Union (ERC, ASC-Q, 101040624). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. SJ is a CIFAR Fellow in the Quantum Information Science Program.

Acknowledgements

We thank Jana Sotáková and Mehrdad Tahmasbi for insightful discussions about path finding via edge sampling.

Cite AsGet BibTex

Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithm for Path-Edge Sampling. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.TQC.2023.5

Abstract

We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Quantum query complexity
  • Theory of computation → Algorithm design techniques
Keywords
  • Algorithm design and analysis
  • Query complexity
  • Graph algorithms
  • Span program algorithm
  • Path finding
  • Path detection

Metrics

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

Related Versions

References

  1. Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):1-9, 2021. Google Scholar
  2. Noel T. Anderson, Jay-U Chung, Shelby Kimmel, Da-Yeon Koh, and Xiaohan Ye. Improved quantum query complexity on easier inputs. arXiv preprint arXiv:2303.00217, 2023. Google Scholar
  3. Simon Apers and Stephen Piddock. Elfs, trees and quantum walks. arXiv preprint arXiv:2211.16379, 2022. Google Scholar
  4. Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4:241, 2020. Google Scholar
  5. Salman Beigi, Leila Taghavi, and Artin Tajdini. Time- and query-optimal quantum algorithms based on decision trees. ACM Transactions on Quantum Computing, 3(4):1-31, 2022. Google Scholar
  6. Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), pages 207-216. IEEE, 2012. Google Scholar
  7. Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), pages 193-204. Springer, 2012. Google Scholar
  8. Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Information & Computation, 18(1-2):18-50, 2018. Google Scholar
  9. Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended learning graphs for triangle finding. Algorithmica, 82(4):980-1005, 2020. Google Scholar
  10. Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6(4):312-340, 1996. Google Scholar
  11. Denis X. Charles, Kristen E. Lauter, and Eyal Z. Goren. Cryptographic hash functions from expander graphs. Journal of Cryptology, 22:93-113, 2007. URL: https://doi.org/10.1007/s00145-007-9002-x.
  12. 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 (STOC 2003), pages 59-68, 2003. Google Scholar
  13. Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum algorithms and the power of forgetting. arXiv preprint arXiv:2211.12447, 2022. Google Scholar
  14. Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339-354, 1998. URL: https://doi.org/10.1098/rspa.1998.0164.
  15. Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita. Span programs and quantum time complexity. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), pages 26:1-26:14, 2020. Google Scholar
  16. Luca De Feo, David Jao, and Jérome Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematial Cryptology, 8:209-247, 2014. URL: https://doi.org/10.1515/jmc-2012-0015.
  17. Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:14, 2019. URL: https://doi.org/10.4230/LIPIcs.TQC.2019.6.
  18. Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, 2006. Google Scholar
  19. Steven D. Galbraith and Frederik Vercauteren. Computational problems in supersingular elliptic curve isogenies. Quantum Information Processing, 17(265), 2018. URL: https://doi.org/10.1007/s11128-018-2023-6.
  20. Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude estimation. npj Quantum Information, 7(1):52, March 2021. URL: https://doi.org/10.1038/s41534-021-00379-1.
  21. Tsuyoshi Ito and Stacey Jeffery. Approximate Span Programs. Algorithmica, 81(6):2158-2195, 2019. URL: https://doi.org/10.1007/s00453-018-0527-1.
  22. Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithms for Connectivity and Related Problems. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.49.
  23. Stacey Jeffery. Quantum subroutine composition. arXiv preprint arXiv:2209.14146, 2022. Google Scholar
  24. Stacey Jeffery. Span programs and quantum space complexity. Theory of Computing, 18(1):1-49, 2022. Google Scholar
  25. Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. URL: https://doi.org/10.22331/q-2017-08-17-26.
  26. Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithm for path-edge sampling. arXiv preprint arXiv:2303.03319, 2023. Google Scholar
  27. Stacey Jeffery and Sebastian Zur. Multidimensional quantum walks, with application to k-distinctness. arXiv preprint arXiv:2208.13492, 2022. Google Scholar
  28. Mauricio Karchmer and Avi Wigderson. On span programs. In Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 102-111, 1993. Google Scholar
  29. A. Yu Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026, 1995. URL: http://arxiv.org/abs/quant-ph/9511026.
  30. Troy Lee, Frédéric Magniez, and Miklos Santha. A learning graph based quantum query algorithm for finding constant-size subgraphs. Chicago Journal of Theoretical Computer Science, 18(1), 2011. URL: https://doi.org/10.4086/cjtcs.2012.010.
  31. Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum Query Complexity of State Conversion. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011), pages 344-353, 2011. URL: https://doi.org/10.1109/FOCS.2011.75.
  32. 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. URL: https://doi.org/10.1137/090745854.
  33. Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. Google Scholar
  34. Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 560-569, 2011. URL: https://doi.org/10.1137/1.9781611973082.44.
  35. Ben W. Reichardt. Span programs are equivalent to quantum query algorithms. SIAM Journal on Computing, 43(3):1206-1219, 2014. URL: https://doi.org/10.1137/100792640.
  36. Seiichiro Tani. Claw finding algorithms using quantum walk. Theoretical Computer Science, 410:5285-5297, 2009. URL: https://doi.org/10.1016/j.tcs.2009.08.030.
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