Directed st-connectivity with few paths is in quantum logspace
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910978731409408 |
|---|---|
| author | Apers, Simon Edenhofer, Roman |
| author_facet | Apers, Simon Edenhofer, Roman |
| contents | We present a $\mathsf{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 $\mathsf{DSPACE}(O(\log^2 n/ \log \log n))$. The result establishes a new relationship between~$\mathsf{BQL}$ and unambiguity and fewness subclasses of $\mathsf{NL}$. Further, we also show how to \emph{recognize} directed graphs with at most polynomially many paths between any two nodes in $\mathsf{BQSPACE}(O(\log n))$. This yields the first natural candidate for a language separating $\mathsf{BQL}$ from $\mathsf{L}$ and~$\mathsf{BPL}$. Until now, all candidates potentially separating these classes were inherently promise problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12473 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Directed st-connectivity with few paths is in quantum logspace Apers, Simon Edenhofer, Roman Quantum Physics Computational Complexity Data Structures and Algorithms We present a $\mathsf{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 $\mathsf{DSPACE}(O(\log^2 n/ \log \log n))$. The result establishes a new relationship between~$\mathsf{BQL}$ and unambiguity and fewness subclasses of $\mathsf{NL}$. Further, we also show how to \emph{recognize} directed graphs with at most polynomially many paths between any two nodes in $\mathsf{BQSPACE}(O(\log n))$. This yields the first natural candidate for a language separating $\mathsf{BQL}$ from $\mathsf{L}$ and~$\mathsf{BPL}$. Until now, all candidates potentially separating these classes were inherently promise problems. |
| title | Directed st-connectivity with few paths is in quantum logspace |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.12473 |