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 $U_{uv}\in {\mathbb{C}}^{k\times 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 $|{\psi }_s⟩,|{\psi }_t⟩\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)|{\psi }_s⟩$ and $|{\psi }_t⟩$ to additive error $\epsilon$. 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 $\tilde{O}(n/\epsilon )$ and uses $O(\log n+\log k+\log (1/\epsilon ))$ space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an $\Omega (n)$ quantum query lower bound that holds even when $s$ and $t$ are promised to be connected, so for constant $\epsilon$ our algorithm is optimal up to polylogarithmic factors.

34 pages, 3 figures