Search Results

Documents authored by Pass, Galina

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.117
A Quantum Time-Space Tradeoff for Directed st-Connectivity

Authors: Stacey Jeffery and Galina Pass

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Directed st-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices s and t in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its NL-completeness. We show that for any S ≥ log²(n), there is a quantum algorithm for dstcon using space S and time T ≤ 2^{1/2 log(n) log(n/S) + o(log²(n))}, which is an (up to quadratic) improvement over the best classical algorithm for any S = o(√n). Of the S total space used by our algorithm, only O(log²(n)) is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.
Cite as

Stacey Jeffery and Galina Pass. A Quantum Time-Space Tradeoff for Directed st-Connectivity. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.ICALP.2026.117,
  author =	{Jeffery, Stacey and Pass, Galina},
  title =	{{A Quantum Time-Space Tradeoff for Directed st-Connectivity}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.117},
  URN =		{urn:nbn:de:0030-drops-265063},
  doi =		{10.4230/LIPIcs.ICALP.2026.117},
  annote =	{Keywords: Quantum algorithms, time-space tradeoffs, directed st-connectivity, switching networks, space-bounded computation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.54
Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer

Authors: Stacey Jeffery and Galina Pass

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We introduce an object called a subspace graph that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity.
Cite as

Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.STACS.2025.54,
  author =	{Jeffery, Stacey and Pass, Galina},
  title =	{{Multidimensional Quantum Walks, Recursion, and Quantum Divide \& Conquer}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.54},
  URN =		{urn:nbn:de:0030-drops-228791},
  doi =		{10.4230/LIPIcs.STACS.2025.54},
  annote =	{Keywords: Quantum Divide \& Conquer, Time-Efficient, Subspace Graphs, Quantum Walks, Switching Networks, Directed st-Connectivity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.10
(No) Quantum Space-Time Tradeoff for USTCON

Authors: Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
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.
Cite as

Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ESA.2023.10,
  author =	{Apers, Simon and Jeffery, Stacey and Pass, Galina and Walter, Michael},
  title =	{{(No) Quantum Space-Time Tradeoff for USTCON}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.10},
  URN =		{urn:nbn:de:0030-drops-186636},
  doi =		{10.4230/LIPIcs.ESA.2023.10},
  annote =	{Keywords: Undirected st-connectivity, quantum walks, time-space tradeoff}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact