2023-08-30
(No) Quantum space-time tradeoff for USTCON
Publication
Publication
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 = Oe(n2/S) for any S such that S = Ω(log(n)) and S = O(n2/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Oe(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Oe(n1.5) time, or Oe(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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4230/LIPIcs.ESA.2023.10 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Quantum time-space tradeoff lower bounds , Robustness of Quantum Algorithms , ASC-Q , Startimpuls Nationale Quantumtechnologie (KAT-1) | |
| 31st Annual European Symposium on Algorithms, ESA 2023 | |
| , , , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Apers, S., Jeffery, S., Pass, G., & Walter, M. (2023). (No) Quantum space-time tradeoff for USTCON. In Annual European Symposium on Algorithms (pp. 10:1–10:17). doi:10.4230/LIPIcs.ESA.2023.10 |
|
