Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Machine Learning Quantum State Preparation Representation

A Quantum Time-Space Tradeoff for Directed st-Connectivity

arXiv
Authors: Stacey Jeffery, Galina Pass

Year

2025

Paper ID

51485

Status

Preprint

Abstract Read

~2 min

Abstract Words

135

Citations

N/A

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 {sf NL}-completeness. We show that for any Sgeq log2(n), there is a quantum algorithm for DSTCON using space S and time Tleq 2^{frac{1}{2}log(n)log(n/S)+o\(log2(n\))}, which is an (up to quadratic) improvement over the best classical algorithm for any S=o\(sqrt{n}\). Of the S total space used by our algorithm, only O\(log2(n\)) is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.

Why This Paper Matters

  • This paper contributes to the Quantum Machine Learning research area in the Quantum Articles archive.
  • It adds a 2025 reference point for readers tracking recent quantum research.
  • 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.

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:2510.08403 [2] arXiv https://arxiv.org/abs/2510.08403 [3] Publisher https://arxiv.org/abs/2510.08403

Local Citation Graph (Related-Paper Links)

Current Paper #51485 #69034 Hardware-aware Low-latency Quan... #69025 Machine-Learning Optimization a... #69003 QBugLM: An Agentic Benchmarking... #68993 Tomography of quantum states wi...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.