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:2510.14905 · Physical Review A

Quantum circuit model for continuous-time quantum walks on random graphs

Sabyasachi Chakraborty, Rohit Sarma Sarkar, Sonjoy Majumder, Rohit Kishan Ray

Published Feb 11, 2026• 1 citation
arXivHTMLPDF

Abstract

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 = 2^n$ for $n$ qubits) on a quantum circuit is based on Pauli decomposition of the graph Hamiltonian, which can yield $O(4^n)$ terms, and require $O(N^2\log N)$ time for coefficient computation. In contrast, our LPA uses $O(2^n)$ terms, in $O(N^2)$ 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.

DOI
10.1103/6zfy-8h5y

Related papers

Implementation of a continuous-time quantum walk on a sparse graph

Zhaoyang Chen, Guanzhong Li, Lvzhou Li

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 ${H}_{j}$, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.

arXiv:2408.10553•Physical Review A•Nov 15, 2024•6 citations

A matching decomposition algorithm for simulating quantum walk Hamiltonians

Mostafa Atallah, Alvin Gonzales, Daniel Dilley +3 more

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.

quant-pharXiv:2601.11418•Jan 19, 2026•0 citations

Predicting Resource Efficient Hamiltonian Decomposition for Continuous-Time Quantum Walk Simulations

Mostafa Atallah, Rebekah Herrman, Zain H. Saleem

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.

quant-pharXiv:2608.20660•Aug 24, 2026•0 citations

Quantum Walks in a Superconducting Quantum Computer

Jaime E. Santos, Bruno Chagas, Rodrigo Chaves

Quantum Walks are among the most widely used techniques with which we can construct new quantum algorithms. This paper aims to outline how to construct a circuit for the continuous-time quantum walk (CTQW) over circulant graphs using the Quantum Fourier Transform (QFT) due to the spectral properties of those graphs. Furthermore, we examine how the Approximate Quantum Fourier Transform (AQFT) allows us to shorten the size of the circuit by reducing the number of controlled rotation gates. The contributions of this paper consist of the development of a general circuit implementation of the CTQW for an important class of graphs that does not scale up with time, and the study of the cases where the AQFT decreases the error by controlling the approximation. Finally, we provide a statistical analysis for several circulant graphs, running experiments in a IBM's superconducting quantum computer, and we also explore the pretty good state transfer (PGST) for some graphs.

•Aug 16, 2021•2 citations

Extended Poster Abstract: Graph Matching Trotterization for CTQW Circuit Simulation

Mostafa Atallah, Daniel Dilley, Igor Gaidai +3 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs

Mostafa Atallah, Daniel Dilley, Jishnu Mahmud +2 more

Continuous-time quantum walks (CTQWs) on dynamic graphs realize quantum gates as sequences of time-evolving graph Hamiltonians, but naive constructions produce long sequences with redundancy. Simplification rules, which are graph rewrite rules that shorten a dynamic graph sequence while preserving the unitary it implements, are the CTQW analogue of circuit identities in the gate model. In this work, we give CTQW realizations of the standard single-qubit gates and introduce new graph rewrite rules. We demonstrate the simplification rules through worked circuit reductions and outline their use as transpilation primitives for converting between the circuit model and the dynamic graph framework.

quant-pharXiv:2609.18463•Sep 17, 2026•0 citations
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=2nN = 2^nN=2n for nnn qubits) on a quantum circuit is based on Pauli decomposition of the graph Hamiltonian, which can yield O(4n)O(4^n)O(4n) terms, and require O(N2log⁡N)O(N^2\log N)O(N2logN) time for coefficient computation. In contrast, our LPA uses O(2n)O(2^n)O(2n) terms, in O(N2)O(N^2)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.
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 AAA corresponds to the adjacency matrix of a graph). Our result is, for a ddd-sparse graph with NNN vertices and evolution time ttt, 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)d=O(1)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 HHH can be represented as the sum of some Hamiltonians Hj{H}_{j}Hj​, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.
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.
Quantum Walks are among the most widely used techniques with which we can construct new quantum algorithms. This paper aims to outline how to construct a circuit for the continuous-time quantum walk (CTQW) over circulant graphs using the Quantum Fourier Transform (QFT) due to the spectral properties of those graphs. Furthermore, we examine how the Approximate Quantum Fourier Transform (AQFT) allows us to shorten the size of the circuit by reducing the number of controlled rotation gates. The contributions of this paper consist of the development of a general circuit implementation of the CTQW for an important class of graphs that does not scale up with time, and the study of the cases where the AQFT decreases the error by controlling the approximation. Finally, we provide a statistical analysis for several circulant graphs, running experiments in a IBM's superconducting quantum computer, and we also explore the pretty good state transfer (PGST) for some graphs.
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.
Continuous-time quantum walks (CTQWs) on dynamic graphs realize quantum gates as sequences of time-evolving graph Hamiltonians, but naive constructions produce long sequences with redundancy. Simplification rules, which are graph rewrite rules that shorten a dynamic graph sequence while preserving the unitary it implements, are the CTQW analogue of circuit identities in the gate model. In this work, we give CTQW realizations of the standard single-qubit gates and introduce new graph rewrite rules. We demonstrate the simplification rules through worked circuit reductions and outline their use as transpilation primitives for converting between the circuit model and the dynamic graph framework.