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• 0 citations
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.

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•0 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•0 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

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.

quant-pharXiv:2610.00527•Oct 2, 2026•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•1 citation

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•0 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.
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.
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on nnn labelled vertices in O~(n6.38)\widetilde O(n^{6.38})O(n6.38) bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost O~(n5)\widetilde O(n^5)O(n5) bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
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.