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

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

Zhaoyang Chen, Guanzhong Li, Lvzhou Li

Published Nov 15, 2024• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.110.052215

Related papers

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

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

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

Efficient Circuit Implementations of Continuous-Time Quantum Walks for Quantum Search

Renato Portugal, Jalil Khatibi Moqadam

Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.

arXiv:2212.08889•Entropy•Apr 23, 2025•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

Isolated vertices in continuous-time quantum walks on dynamic graphs

Thomas G. Wong

It was recently shown that continuous-time quantum walks on dynamic graphs, i.e., sequences of static graphs whose edges change at specific times, can implement a universal set of quantum gates. This result treated all isolated vertices as having self-loops, so they all evolved by a phase under the quantum walk. In this paper, we permit isolated vertices to be loopless or looped, and loopless isolated vertices do not evolve at all under the quantum walk. Using this distinction, we construct simpler dynamic graphs that implement the Pauli gates and a set of universal quantum gates consisting of the Hadamard, $T$, and controlled-not gates, and these gates are easily extended to multiqubit systems. For example, the $T$ gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of 4. We also construct a generalized phase gate, of which $Z$, $S$, and $T$ are specific instances. Finally, we validate our implementations by numerically simulating a quantum circuit consisting of layers of one- and two-qubit gates, similar to those in recent quantum supremacy experiments, using a quantum walk.

arXiv:1908.00507•Physical Review A•Dec 18, 2019•11 citations
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{e}^{\ensuremath{-}iHt}e\ensuremath−iHt, where H=\ensuremathγAH=\ensuremath{\gamma}AH=\ensuremathγA (\ensuremathγ\ensuremath{\gamma}\ensuremathγ 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{e}^{\ensuremath{-}iHt}e\ensuremath−iHt by a quantum circuit with gate complexity (d3\ensuremath∥H\ensuremath∥tNlog2(N))1+o(1)({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}(d3\ensuremath∥H\ensuremath∥tNlog2​(N))1+o(1), compared to the general Pauli decomposition, which scales like (\ensuremath∥H\ensuremath∥tN4log2(N))1+o(1)(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}(\ensuremath∥H\ensuremath∥tN4log2​(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−iHjt{e}^{\ensuremath{-}i{H}_{j}t}e\ensuremath−iHj​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.
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.
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 a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.
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.
It was recently shown that continuous-time quantum walks on dynamic graphs, i.e., sequences of static graphs whose edges change at specific times, can implement a universal set of quantum gates. This result treated all isolated vertices as having self-loops, so they all evolved by a phase under the quantum walk. In this paper, we permit isolated vertices to be loopless or looped, and loopless isolated vertices do not evolve at all under the quantum walk. Using this distinction, we construct simpler dynamic graphs that implement the Pauli gates and a set of universal quantum gates consisting of the Hadamard, TTT, and controlled-not gates, and these gates are easily extended to multiqubit systems. For example, the TTT gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of 4. We also construct a generalized phase gate, of which ZZZ, SSS, and TTT are specific instances. Finally, we validate our implementations by numerically simulating a quantum circuit consisting of layers of one- and two-qubit gates, similar to those in recent quantum supremacy experiments, using a quantum walk.