arXiv preprint ·
A Quantum Algorithm for $st$-Transport on Flat Connection Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.