Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40231

A Quantum Algorithm for $st$-Transport on Flat Connection Graphs

Stacey Jeffery, Tobias J. Osborne, Galina Pass

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 1 citation
arXivHTMLPDF

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$.

Little sign of AI-generated textStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
34 pages, 3 figures

Related papers

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

Simon Apers, Arinta Auza, Troy Lee

An $s{\operatorname{-}}t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from $s$ to $t$. In this work we describe a quantum algorithm for the minimum $s{\operatorname{-}}t$ cut problem on undirected graphs. For an undirected graph with $n$ vertices, $m$ edges, and integral edge weights bounded by $W$, the algorithm computes with high probability the weight of a minimum $s{\operatorname{-}}t$ cut after $\widetilde O(\sqrt{m} n^{5/6} W^{1/3})$ queries to the adjacency list of $G$. For simple graphs this bound is always $\widetilde O(n^{11/6})$, even in the dense case when $m = Ω(n^2)$. In contrast, a randomized algorithm must make $Ω(m)$ queries to the adjacency list of a simple graph $G$ even to decide whether $s$ and $t$ are connected.

arXiv:2110.15587•Oct 29, 2021•4 citations

Quantum algorithms for path and cycle containment problems

Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro

The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph $H$ is present in an input graph $G$, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length $k$. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly $k$, or at most $k$. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity $\widetilde{O}(n^{3/2-α_k})$, where $α_k \in Θ(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$, beating the previous best upper bound $O(n^{3/2})$ on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an $O(\sqrt{n})$ query algorithm.

quant-pharXiv:2605.09017•Leibniz international proceedings in informatics•May 12, 2026•5 citations

A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs

Simon Apers, Arinta Auza, Troy Lee

An $s{\operatorname{-}}t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from $s$ to $t$. In this work we describe a quantum algorithm for the minimum $s{\operatorname{-}}t$ cut problem on undirected graphs. For an undirected graph with $n$ vertices, $m$ edges, and integral edge weights bounded by $W$, the algorithm computes with high probability the weight of a minimum $s{\operatorname{-}}t$ cut in time $\widetilde O(\sqrt{m} n^{5/6} W^{1/3} + n^{5/3} W^{2/3})$, given adjacency list access to $G$. For simple graphs this bound is always $\widetilde O(n^{11/6})$, even in the dense case when $m = \Omega(n^2)$. In contrast, a randomized algorithm must make $\Omega(m)$ queries to the adjacency list of a simple graph $G$ even to decide whether $s$ and $t$ are connected.

•Oct 29, 2021•0 citations

Advances in quantum algorithms for the shortest path problem

Adam Wesołowski, Stephen Piddock

Given an undirected, weighted graph, with $n$ vertices and $m$ edges, and two special vertices $s$ and $t$, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ space on graphs where the shortest $s$-$t$ path is also a minimum resistance $s$-$t$ subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability $q>0.537$ of finding the shortest $s$-$t$ path. In such cases the quantum algorithm outputs the shortest $s$-$t$ path with high probability in $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ space, where $l$ is the length (or total weight, in case of weighted graphs) of the shortest $s$-$t$ path. This algorithm can be parallelised to $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.

arXiv:2408.10427•Aug 19, 2024•13 citations

A Constant Measurement Quantum Algorithm for Graph Connectivity

Maximilian Balthasar Mansky, Chon‐Fai Kam, Claudia Linnhoff–Popien

We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.

arXiv:2411.15015•Nov 22, 2024•1 citation

Quantum complexity of minimum cut

Simon Apers, Troy Lee

The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $τ$, we give a quantum algorithm to solve the minimum cut problem using $\tilde O(n^{3/2}\sqrtτ)$ queries and time. Moreover, for every integer $1 \le τ\le n$ we give an example of a graph $G$ with edge weights $1$ and $τ$ such that solving the minimum cut problem on $G$ requires $Ω(n^{3/2}\sqrtτ)$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Ω(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $\tilde Θ(m)$. We show that the quantum query and time complexity are $\tilde O(\sqrt{mnτ})$ and $\tilde O(\sqrt{mnτ} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $τ$. For dense graphs we give lower bounds on the quantum query complexity of $Ω(n^{3/2})$ for $τ> 1$ and $Ω(τn)$ for any $1 \leq τ\leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).

arXiv:2011.09823•Nov 19, 2020•4 citations
A Quantum Algorithm for ststst-Transport on Flat Connection Graphs
We study a generalization of undirected ststst-connectivity to graphs whose edges carry quantum operations. Let G=(V,E)G=(V,E)G=(V,E) be an undirected graph on nnn vertices in which each edge {u,v}\{u,v\}{u,v} is labeled by a unitary Uuv∈Ck×kU_{uv}\in\mathbb{C}^{k\times k}Uuv​∈Ck×k, with Uvu=Uuv†U_{vu}=U_{uv}^\daggerUvu​=Uuv†​. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices uuu and vvv 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 sss and ttt are connected, transporting a state from sss to ttt defines a unique unitary Us(t)U_s(t)Us​(t). Given states ∣ψs⟩,∣ψt⟩∈Ck|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k∣ψs​⟩,∣ψt​⟩∈Ck and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{ststst-transport problem} is to decide whether sss and ttt are connected and, if so, to estimate the squared overlap between Us(t)∣ψs⟩U_s(t)|ψ_s\rangleUs​(t)∣ψs​⟩ and ∣ψt⟩|ψ_t\rangle∣ψt​⟩ to additive error ε\varepsilonε. When k=1k=1k=1 and all labels are trivial, this is exactly undirected ststst-connectivity. We give a bounded-error quantum algorithm for ststst-transport that runs in time O~(n/ε)\widetilde{O}(n/\varepsilon)O(n/ε) and uses O(log⁡n+log⁡k+log⁡(1/ε))O(\log n+\log k+\log(1/\varepsilon))O(logn+logk+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)Ω(n)Ω(n) quantum query lower bound that holds even when sss and ttt are promised to be connected, so for constant ε\varepsilonε our algorithm is optimal up to polylogarithmic factors.
The paper studies ststst-transport on undirected graphs with kkk-dimensional unitary edge labels satisfying Uvu=Uuv†U_{vu}=U_{uv}^\daggerUvu​=Uuv†​. A flatness promise makes the ordered product along a path depend only on its endpoints, defining a unique transport unitary Us(t)U_s(t)Us​(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 ∣⟨ψt∣Us(t)∣ψs⟩∣2|\langle\psi_t|U_s(t)|\psi_s\rangle|^2∣⟨ψt​∣Us​(t)∣ψs​⟩∣2 to additive error ε\varepsilonε.
For unweighted input graphs with nnn vertices, the algorithm has bounded error, runs in O~(n/ε)\widetilde O(n/\varepsilon)O(n/ε) time, and uses O(log⁡n+log⁡k+log⁡(1/ε))O(\log n+\log k+\log(1/\varepsilon))O(logn+logk+log(1/ε)) qubits. A weighted-graph version costs O~(WR/ε)\widetilde O(\sqrt{\mathbf W\mathbf R}/\varepsilon)O(WR​/ε), 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 WR=O(n2)\mathbf W\mathbf R=O(n^2)WR=O(n2) while preserving transport. It also provides approximate transport-state generation. Encoding parity in Pauli-XXX labels along a path establishes an Ω(n)\Omega(n)Ω(n) quantum query lower bound, even for connected instances with k=2k=2k=2, giving near-optimal dependence on nnn 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ε.
An s-⁡ts{\operatorname{-}}ts-t minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices sss and ttt. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from sss to ttt. In this work we describe a quantum algorithm for the minimum s-⁡ts{\operatorname{-}}ts-t cut problem on undirected graphs. For an undirected graph with nnn vertices, mmm edges, and integral edge weights bounded by WWW, the algorithm computes with high probability the weight of a minimum s-⁡ts{\operatorname{-}}ts-t cut after O~(mn5/6W1/3)\widetilde O(\sqrt{m} n^{5/6} W^{1/3})O(m​n5/6W1/3) queries to the adjacency list of GGG. For simple graphs this bound is always O~(n11/6)\widetilde O(n^{11/6})O(n11/6), even in the dense case when m=Ω(n2)m = Ω(n^2)m=Ω(n2). In contrast, a randomized algorithm must make Ω(m)Ω(m)Ω(m) queries to the adjacency list of a simple graph GGG even to decide whether sss and ttt are connected.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph HHH is present in an input graph GGG, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length kkk. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly kkk, or at most kkk. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O~(n3/2−αk)\widetilde{O}(n^{3/2-α_k})O(n3/2−αk​), where αk∈Θ(c−k)α_k \in Θ(c^{-k})αk​∈Θ(c−k) and c=3+17/2≈1.33c = \sqrt{3+\sqrt{17}}/2 \approx 1.33c=3+17​​/2≈1.33, beating the previous best upper bound O(n3/2)O(n^{3/2})O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n)O(\sqrt{n})O(n​) query algorithm.
An s-⁡ts{\operatorname{-}}ts-t minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices sss and ttt. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from sss to ttt. In this work we describe a quantum algorithm for the minimum s-⁡ts{\operatorname{-}}ts-t cut problem on undirected graphs. For an undirected graph with nnn vertices, mmm edges, and integral edge weights bounded by WWW, the algorithm computes with high probability the weight of a minimum s-⁡ts{\operatorname{-}}ts-t cut in time O~(mn5/6W1/3+n5/3W2/3)\widetilde O(\sqrt{m} n^{5/6} W^{1/3} + n^{5/3} W^{2/3})O(m​n5/6W1/3+n5/3W2/3), given adjacency list access to GGG. For simple graphs this bound is always O~(n11/6)\widetilde O(n^{11/6})O(n11/6), even in the dense case when m=Ω(n2)m = \Omega(n^2)m=Ω(n2). In contrast, a randomized algorithm must make Ω(m)\Omega(m)Ω(m) queries to the adjacency list of a simple graph GGG even to decide whether sss and ttt are connected.
Given an undirected, weighted graph, with nnn vertices and mmm edges, and two special vertices sss and ttt, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m)\tilde{O}(l^2\sqrt{m})O~(l2m​) expected time and uses O(log⁡n)O(\log{n})O(logn) space on graphs where the shortest sss-ttt path is also a minimum resistance sss-ttt subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537q>0.537q>0.537 of finding the shortest sss-ttt path. In such cases the quantum algorithm outputs the shortest sss-ttt path with high probability in O~(ℓm)\widetilde{O}(\ell\sqrt{m})O(ℓm​) expected time and O(log⁡n)O(\log{n})O(logn) space, where lll is the length (or total weight, in case of weighted graphs) of the shortest sss-ttt path. This algorithm can be parallelised to O~(lm)\tilde{O}(\sqrt{lm})O~(lm​) circuit depth when using O(llog⁡n)O(l\log{n})O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.
The minimum cut problem in an undirected and weighted graph GGG is to find the minimum total weight of a set of edges whose removal disconnects GGG. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If GGG has nnn vertices and edge weights at least 111 and at most τττ, we give a quantum algorithm to solve the minimum cut problem using O~(n3/2τ)\tilde O(n^{3/2}\sqrtτ)O~(n3/2τ​) queries and time. Moreover, for every integer 1≤τ≤n1 \le τ\le n1≤τ≤n we give an example of a graph GGG with edge weights 111 and τττ such that solving the minimum cut problem on GGG requires Ω(n3/2τ)Ω(n^{3/2}\sqrtτ)Ω(n3/2τ​) many queries to the adjacency matrix of GGG. These results contrast with the classical randomized case where Ω(n2)Ω(n^2)Ω(n2) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when GGG has mmm edges the classical randomized complexity of the minimum cut problem is Θ~(m)\tilde Θ(m)Θ~(m). We show that the quantum query and time complexity are O~(mnτ)\tilde O(\sqrt{mnτ})O~(mnτ​) and O~(mnτ+n3/2)\tilde O(\sqrt{mnτ} + n^{3/2})O~(mnτ​+n3/2), respectively, where again the edge weights are between 111 and τττ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2)Ω(n^{3/2})Ω(n3/2) for τ>1τ> 1τ>1 and Ω(τn)Ω(τn)Ω(τn) for any 1≤τ≤n1 \leq τ\leq n1≤τ≤n. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).