Abstract
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.
Introduction
Graph connectivity—determining if every node in a graph can reach every other node—is a foundational problem in computer science with applications ranging from social network analysis to routing and reliability. Classically, this is solved in linear time ($O(m)$ for $m$ edges) using Breadth-First Search (BFS). Previous quantum attempts typically used Grover’s search to accelerate parts of classical algorithms, resulting in sub-linear but still size-dependent runtimes. The authors of this paper sought to break the dependency on graph size for the measurement phase, aiming for a "constant time" decision process for the connectivity property itself.
Methods
The core innovation lies in the mapping of graph structures to ZX-calculus, a graphical language for quantum mechanics. Each node in a graph $\mathcal{G}$ is mapped to a qubit, and each edge is represented by a two-qubit non-unitary "Z-spider" gate.
The Fusion Rule
In ZX-calculus, adjacent spiders of the same color can "fuse" into a single larger spider. This is the fundamental mechanism that allows local edge operations to represent global connectivity.
Mathematically, if a set of nodes is connected by edges, the corresponding gates contract into a single multi-qubit projector. The algorithm starts with qubits in the ground state, applies Hadamard gates to create a superposition, and then applies the edge-based Z-spiders. If nodes are connected, the fusion of these spiders creates a Greenberger-Horne-Zeilinger (GHZ) state (e.g., $\frac{1}{\sqrt{2}}(|00...0\rangle + |11...1\rangle)$) for that component.
Algorithm Pipeline
The complete process maps an edge list to a graph, translates that graph into a sequence of two-qubit operations, and results in a quantum state where connected components are represented by equivalent spiders.
Key Results
The algorithm determines if a graph is connected in exactly two measurements, providing a success probability of 3/4. By extending the measurement count to $O(|G_k|)$ (where $|G_k|$ is the number of components), the algorithm can identify exactly which nodes belong to which connected component.
Numerical simulations using the Julia programming language and the Yao.jl package validated the approach on Erdős-Rényi graphs with up to 1000 nodes. Key performance metrics include:
- Abelian Gates: The gates used are abelian (they commute), meaning the algorithm is independent of edge list order.
- Circuit Depth: The depth is $O(m/n)$ in the best case (highly parallelizable) and $O(m)$ in the worst case. For pre-sorted graphs, depth is bounded by $O(2n)$.
- State Decay Mitigation: To counter exponential state decay from non-unitary operations, the authors propose using $m$ ancilla qubits for Bell measurements.
Limitations and Future Work
Current quantum hardware is primarily designed for unitary operations. Implementing non-unitary Z-spiders directly requires post-selection or a significant number of ancilla qubits and mid-circuit measurements. However, this "requirement-driven" gate design could be extended to other complex problems, such as bipartiteness or strong connectivity in directed graphs.
Summary updated