2026-07-23T16:09:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10398 2024-03-06T10:46:45Z ddc:004 open_access

Applications of the Quantum Algorithm for st-Connectivity DeLorenzo, Kai Kimmel, Shelby Witter, R. Teal graphs algorithms query complexity quantum algorithms span programs We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kai DeLorenzo and Shelby Kimmel and R. Teal Witter 2019 Is Part Of LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2019.6 urn:nbn:de:0030-drops-103984 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.6 eng https://creativecommons.org/licenses/by/3.0/legalcode