A Quantum Algorithm for st-Transport on Flat Connection Graphs
Abstract
We study a generalization of undirected st-connectivity to graphs whose edges carry quantum operations. Let G=(V,E) be an undirected graph on n vertices in which each edge {u,v} is labeled by a unitary Uuv∈ℂk× k, with Uvu=Uuv†. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices u and v is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever s and t are connected, transporting a state from s to t defines a unique unitary Us(t). Given states |ψs⟩,|ψt⟩∈ℂk and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{st-transport problem} is to decide whether s and t are connected and, if so, to estimate the squared overlap between Us(t)|ψs⟩ and |ψt⟩ to additive error ε. When k=1 and all labels are trivial, this is exactly undirected st-connectivity. We give a bounded-error quantum algorithm for st-transport that runs in time Õ(n/ε) and uses O(log n+log k+log(1/ε)) space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an Ω(n) quantum query lower bound that holds even when s and t are promised to be connected, so for constant ε our algorithm is optimal up to polylogarithmic factors.
Related
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
- Flat connections on moduli spaces I: Local (1,0)-extension of the DHS connection
- Some remarks on the connection between generative diffusion and optimal transport
- Topological Transverse Transport without a Gap in Critical Topological Flat Bands
BibTeX
@misc{jeffery2026quantum,
title = {{A Quantum Algorithm for $st$-Transport on Flat Connection Graphs}},
author = {Stacey Jeffery and Tobias J. Osborne and Galina Pass},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40231},
eprint = {2609.40231},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40231},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Quantum Algorithm for st-Transport on Flat Connection Graphs
AU - Stacey Jeffery
AU - Tobias J. Osborne
AU - Galina Pass
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40231
UR - https://arxiv.org/abs/2609.40231
AB - We study a generalization of undirected st-connectivity to graphs whose edges carry quantum operations. Let G=(V,E) be an undirected graph on n vertices in which each edge {u,v} is labeled by a unitary U_uv∈ℂ^k× k, with U_vu=U_uv^†. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices u and v is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever s and t are connected, transporting a state from s to t defines a unique unitary U_s(t). Given states |ψ_s⟩,|ψ_t⟩∈ℂ^k and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{st-transport problem} is to decide whether s and t are connected and, if so, to estimate the squared overlap between U_s(t)|ψ_s⟩ and |ψ_t⟩ to additive error ε. When k=1 and all labels are trivial, this is exactly undirected st-connectivity. We give a bounded-error quantum algorithm for st-transport that runs in time Õ(n/ε) and uses O(log n+log k+log(1/ε)) space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an Ω(n) quantum query lower bound that holds even when s and t are promised to be connected, so for constant ε our algorithm is optimal up to polylogarithmic factors.
ER -