2023-07-18
Quantum algorithm for path-edge sampling
Publication
Publication
Presented at the
18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023 (July 2023), Aveiro, Portugal
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.
| Additional Metadata | |
|---|---|
| , , , , , | |
| doi.org/10.4230/LIPIcs.TQC.2023.5 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Quantum time-space tradeoff lower bounds , Robustness of Quantum Algorithms , ASC-Q | |
| 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023 | |
| , , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Jeffery, S., Kimmel, S., & Piedrafita Postigo, Á. (2023). Quantum algorithm for path-edge sampling. In Conference on the Theory of Quantum Computation, Communication and Cryptography (pp. 5.1–5.28). doi:10.4230/LIPIcs.TQC.2023.5 |
|
