(No) Quantum space-time tradeoff for USTCON
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909153200439296 |
|---|---|
| author | Apers, Simon Jeffery, Stacey Pass, Galina Walter, Michael |
| author_facet | Apers, Simon Jeffery, Stacey Pass, Galina Walter, Michael |
| contents | Undirected $st$-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of $T=\tilde{O}(n^2/S)$ for any $S$ such that $S=Ω(\log (n))$ and $S=O(n^2/m)$. Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time $\tilde{O}(n)$ and space $O(\log (n))$ simultaneously. This improves on previous results, which required either $O(\log (n))$ space and $\tilde{O}(n^{1.5})$ time, or $\tilde{O}(n)$ space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_00094 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | (No) Quantum space-time tradeoff for USTCON Apers, Simon Jeffery, Stacey Pass, Galina Walter, Michael Quantum Physics Data Structures and Algorithms Undirected $st$-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of $T=\tilde{O}(n^2/S)$ for any $S$ such that $S=Ω(\log (n))$ and $S=O(n^2/m)$. Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time $\tilde{O}(n)$ and space $O(\log (n))$ simultaneously. This improves on previous results, which required either $O(\log (n))$ space and $\tilde{O}(n^{1.5})$ time, or $\tilde{O}(n)$ space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk. |
| title | (No) Quantum space-time tradeoff for USTCON |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2212.00094 |