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:2601.11418

Simulating Quantum Walk Hamiltonians without Pauli Decomposition

Mostafa Atallah, Alvin Gonzales, Daniel Dilley, Igor Gaidai, Zain H. Saleem, Rebekah Herrman

quant-phSubmitted Jan 16, 2026• Announced Jan 19, 2026• 0 citations• Revised Jun 8, 2026 (v2)
v1 · Jan 16, 2026v2 · Jun 8, 2026v3 · Jun 16, 2026
arXivHTMLPDF

Abstract

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.

Related papers

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

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

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

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

Sabyasachi Chakraborty, Rohit Sarma Sarkar, Sonjoy Majumder +1 more

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.

arXiv:2510.14905•Physical Review A•Feb 11, 2026•1 citation

Efficient sparse state preparation via quantum walks

Alvin Gonzales, Rebekah Herrman, Colin Campbell +4 more

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 an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.

arXiv:2405.20273•npj Quantum Information•Aug 21, 2025•2 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
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 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) 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.
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) 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 an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.
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.