2026-08-15T13:15:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23712 2025-10-27T10:42:43Z ddc:004 open_access

Directed st-Connectivity with Few Paths Is in Quantum Logspace Apers, Simon Edenhofer, Roman Quantum computation Space-bounded complexity classes Graph connectivity Unambiguous computation Random walks We present a BQSPACE(O(log n))-procedure to count st-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in s and polynomially many paths ending in t. For comparison, the best known classical upper bound in this case just to decide st-connectivity is DSPACE(O(log² n/ log log n)). The result establishes a new relationship between BQL and unambiguity and fewness subclasses of NL. Further, we also show how to recognize directed graphs with at most polynomially many paths between any two nodes in BQSPACE(O(log n)). This yields the first natural candidate for a language separating BQL from 𝖫 and BPL. Until now, all candidates potentially separating these classes were inherently promise problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Roman Edenhofer 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.18 urn:nbn:de:0030-drops-237128 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode