Quantum algorithm for path-edge sampling
| Authors |
|
|---|---|
| Publication date | 07-2023 |
| Host editors |
|
| Book title | 18th Conference on the Theory of Quantum Computation, Communication and Cryptography |
| Book subtitle | TQC 2023, July 24-28, 2023, Aveiro, Portugal |
| ISBN (electronic) |
|
| Series | Leibniz International Proceedings in Informatics |
| Event | 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023 |
| Article number | 5 |
| Number of pages | 28 |
| Publisher | Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Organisations |
|
| 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. |
| Document type | Conference contribution |
| Language | English |
| Published at | https://doi.org/10.4230/LIPIcs.TQC.2023.5 |
| Other links | https://www.scopus.com/pages/publications/85168331776 |
| Downloads |
Quantum algorithm for path-edge sampling
(Final published version)
|
| Permalink to this page | |
