We present a novel algorithm that converts CTQWs on arbitrary graphs into efficient quantum circuits through graph matching decomposition. Our approach decomposes the target graph into a set of matchings, where a matching is a collection of disjoint edges that can be implemented exactly using multi-controlled rotation gates. The overall CTQW evolution is then approximated via Trotterization over these matchings. We validate our approach through comprehensive comparison with Pauli decomposition methods across all connected isomorphic 8-vertex graphs, demonstrating comparable accuracy across all test cases. Our matching decomposition achieves reduced gate counts compared to Pauli decomposition for approximately 33% of all connected 8-vertex graphs, with particular advantages for graphs that decompose into small numbers of matchings or contain many disjoint edges. Our matching decomposition provides a valuable alternative pathway for implementing CTQW-based algorithms on near-term gate-based quantum devices while maintaining the fundamental quantum advantages of walk-based computation.
We present a novel algorithm that converts CTQWs on arbitrary graphs into efficient quantum circuits through graph matching decomposition. Our approach decomposes the target graph into a set of matchings, where a matching is a collection of disjoint edges that can be implemented exactly using multi-controlled rotation gates. The overall CTQW evolution is then approximated via Trotterization over these matchings. We validate our approach through comprehensive comparison with Pauli decomposition methods across all connected isomorphic 8-vertex graphs, demonstrating comparable accuracy across all test cases. Our matching decomposition achieves reduced gate counts compared to Pauli decomposition for approximately 33% of all connected 8-vertex graphs, with particular advantages for graphs that decompose into small numbers of matchings or contain many disjoint edges. Our matching decomposition provides a valuable alternative pathway for implementing CTQW-based algorithms on near-term gate-based quantum devices while maintaining the fundamental quantum advantages of walk-based computation.
In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. We develop a greedy matching heuristic and a compression-aware matching heuristic, both of which can be used in the quantum circuit algorithm. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare greedy (compression-aware) matching decomposition to a standard Pauli-based simulation pipeline and find that greedy (compression-aware) matching decomposition consistently yields substantial resource reductions, requiring up to 43% (70\%) fewer controlled gates and up to 54% (75\%) shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.
Simulating a continuous-time quantum walk (CTQW) on a graph in the circuit model of quantum computing requires decomposing its Hamiltonian into terms that can be Trotterized into hardware-native gates. We consider two such decompositions: the standard Pauli decomposition and the recently introduced matching decomposition. Prior work suggests that the matching decomposition uses fewer CX gates on sparse graphs, while the Pauli decomposition uses fewer on denser graphs. Since CX gates dominate error and runtime on current hardware, we train machine learning models to predict, for a given graph, which of the two decompositions produces the smaller CX gate count. We train and evaluate on the complete population of all 11,117 connected eight-vertex graphs from Brendan McKay's database, so the class balance and overlap are measured directly rather than estimated. We use twelve features: ten topological properties of the graph and two that count the terms the Pauli and matching decompositions produce (n_Pauli and n_match), both computable without transpiling the simulation circuit. Standard topological properties alone provide little predictive power. Instead, the dominant signal comes from n_Pauli, a property of the Hamiltonian decomposition rather than an intrinsic property of the graph; degree variance is the only other feature that carries signal. Across a range of models the Matthews correlation coefficient (MCC) falls in a narrow band, from 0.569 untuned to 0.593 after tuning, so no single architecture stands out. We adopt a single-hidden-layer neural network at MCC 0.593. Applied frozen to a held-out, class-balanced test set of larger graphs (up to 256 vertices) from structured and Erdos-Renyi families, the model transfers, with MCC rising from 0.785 at N=8 to 1 at N>=64.
We present a generalized and efficient quantum circuit framework for implementing discrete-time quantum walks (DTQWs) on Cayley graphs of arbitrary dimension. Building on the Boundary QFT scheme of Razzoli et al., we introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs across three classes of generating sets: inverse-closed without involutions, inverse-closed with an involution, and non-inverse-closed. The decomposition hierarchically factorizes the QFT-diagonalized shift operator into structured block components, progressively reducing the control degree of the required rotation gates and replacing high-degree multi-qubit controlled operations with collections of lower-degree equivalents. We extend this construction to d-dimensional torus graphs and provide explicit circuit implementations for an 8-Cayley graph and a Z16×Z8 torus graph as concrete illustrations. Gate complexity analysis using the linear CNOT scaling of Rosa et al. demonstrates that the decomposed implementation achieves a substantial reduction in upper-bound CNOT cost relative to the naive implementation within the regime k≤64 for inverse-closed graphs and k≤16 for non-inverse-closed graphs, where k denotes the degree of the generating set. Benchmarking further reveals that this efficiency gain is largely insensitive to the system size N, identifying k as the dominant resource parameter for the shift operator. These results provide a scalable and hardware-conscious pathway toward practical DTQW implementations on near-term quantum devices.
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and A corresponds to the adjacency matrix of a graph). Our result is, for a d-sparse graph with N vertices and evolution time t, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance, d=O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian H can be represented as the sum of some Hamiltonians Hj, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.
Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work we develop a mapping from dynamic CTQWs to the gate model of computation in the form of an algorithm to convert arbitrary single edge walks and single self loop walks, which are the fundamental building blocks of dynamic CTQWs, to their circuit model counterparts. We use this mapping to introduce an arbitrary quantum state preparation framework based on dynamic CTQWs. Our approach utilizes global information about the target state, relates state preparation to finding the optimal path in a graph, and leads to optimizations in the reduction of controls that are not as obvious in other approaches. Interestingly, classical optimization problems such as the minimal hitting set, minimum spanning tree, and shortest Hamiltonian path problems arise in our framework. We test our methods against uniformly controlled rotations methods, used by Qiskit, and find ours requires fewer CX gates when the target state has a polynomial number of non-zero amplitudes.
Quantum-circuit implementations of continuous-time quantum walks (CTQWs) can provide an efficient route to model graph-based algorithms. However, constructing circuits that faithfully reproduce CTQW dynamics across arbitrary graphs remains a major challenge. In this work, we introduce a Laplacian partitioning algorithm (LPA) that enables an efficient and scalable quantum-circuit realization of CTQWs on random graphs. A common algorithm to simulate a general graph (of size N=2n for n qubits) on a quantum circuit is based on Pauli decomposition of the graph Hamiltonian, which can yield O(4n) terms, and require O(N2logN) time for coefficient computation. In contrast, our LPA uses O(2n) terms, in O(N2) time. Our circuit provides a graph-agnostic framework for CTQWs, implemented via a Trotter-Suzuki product formula and confirming error scaling consistent with theoretical Trotter error bounds. To further test the circuit performance, we study the localization behavior of the CTQW. In our case, localization originates from Laplacian spectral degeneracies rather than disorder (Anderson-type), and our circuit faithfully reproduces these localization phenomena and spectral structure for a random graphs with high accuracy.