2026-07-22T18:58:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18663 2024-03-06T11:02:23Z ddc:004 open_access

(No) Quantum Space-Time Tradeoff for USTCON Apers, Simon Jeffery, Stacey Pass, Galina Walter, Michael Undirected st-connectivity quantum walks time-space tradeoff 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 = Õ(n²/S) for any S such that S = Ω(log(n)) and S = O(n²/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Õ(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Õ(n^{1.5}) time, or Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Stacey Jeffery and Galina Pass and Michael Walter 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.10 urn:nbn:de:0030-drops-186636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.10 eng https://creativecommons.org/licenses/by/4.0/legalcode