arXiv:2609.40231
A Quantum Algorithm for $st$-Transport on Flat Connection Graphs
Stacey Jeffery, Tobias J. Osborne, Galina Pass
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 $U_{uv}\in\mathbb{C}^{k\times k}$, with $U_{vu}=U_{uv}^\dagger$. 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\rangle,|ψ_t\rangle\in\mathbb{C}^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\rangle$ and $|ψ_t\rangle$ to additive error $\varepsilon$. 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 $\widetilde{O}(n/\varepsilon)$ and uses $O(\log n+\log k+\log(1/\varepsilon))$ 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 $\varepsilon$ our algorithm is optimal up to polylogarithmic factors.
AI Summary
The paper studies $st$-transport on undirected graphs with $k$-dimensional unitary edge labels satisfying $U_{vu}=U_{uv}^\dagger$. A flatness promise makes the ordered product along a path depend only on its endpoints, defining a unique transport unitary $U_s(t)$. Given boundary-state preparation oracles and coherent access that simultaneously traverses an edge and applies its label, the task is to detect disconnectedness or estimate $|\langle\psi_t|U_s(t)|\psi_s\rangle|^2$ to additive error $\varepsilon$. For unweighted input graphs with $n$ vertices, the algorithm has bounded error, runs in $\widetilde O(n/\varepsilon)$ time, and uses $O(\log n+\log k+\log(1/\varepsilon))$ qubits. A weighted-graph version costs $\widetilde O(\sqrt{\mathbf W\mathbf R}/\varepsilon)$, given upper bounds on total weight and terminal effective resistance. The construction extends a quantum-walk transducer to implement endpoint transport, composes it with amplitude estimation before conversion into an approximate circuit, and uses Metropolis–Hastings reweighting to obtain $\mathbf W\mathbf R=O(n^2)$ while preserving transport. It also provides approximate transport-state generation. Encoding parity in Pauli-$X$ labels along a path establishes an $\Omega(n)$ quantum query lower bound, even for connected instances with $k=2$, giving near-optimal dependence on $n$ at constant precision. The setting requires exact flatness and black-box coherent unitary access; it does not address inconsistent or noisy connections. The motivation is large internal dimension and small space: with explicit label matrices, transport can instead be computed classically by finding a path and multiplying its labels. The lower bound does not establish optimal dependence on $\varepsilon$.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 34 pages, 3 figures