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

Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs

Seoyoon Kang

quant-phSubmitted Aug 25, 2026• Announced Aug 27, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $\mathbb{Z}_{16} \times \mathbb{Z}_8$ 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 \leq 64$ for inverse-closed graphs and $k \leq 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.

Comments
40 pages

Related papers

Efficient circuit implementation of quantum walks on non-degree-regular graphs

T. Loke, Jingbo B. Wang

This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.

Physical Review A•Oct 31, 2012•21 citations

Efficient Implementation of Discrete-Time Quantum Walks on Quantum Computers

Luca Razzoli, Gabriele Cenedese, Maria Bondani +1 more

Quantum walks have proven to be a universal model for quantum computation and to provide speed-up in certain quantum algorithms. The discrete-time quantum walk (DTQW) model, among others, is one of the most suitable candidates for circuit implementation due to its discrete nature. Current implementations, however, are usually characterized by quantum circuits of large size and depth, which leads to a higher computational cost and severely limits the number of time steps that can be reliably implemented on current quantum computers. In this work, we propose an efficient and scalable quantum circuit implementing the DTQW on the 2n-cycle based on the diagonalization of the conditional shift operator. For t time steps of the DTQW, the proposed circuit requires only O(n2+nt) two-qubit gates compared to the O(n2t) of the current most efficient implementation based on quantum Fourier transforms. We test the proposed circuit on an IBM quantum device for a Hadamard DTQW on the 4-cycle and 8-cycle characterized by periodic dynamics and by recurrent generation of maximally entangled single-particle states. Experimental results are meaningful well beyond the regime of few time steps, paving the way for reliable implementation and use on quantum computers.

arXiv:2402.01854•Entropy•Apr 2, 2024•25 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

Discrete-time quantum walk on circular graph: Simulations and effect of gate depth and errors

Iyed Ben Slimen, Amor Gueddana, Vasudevan Lakshminarayanan

We investigate the counterparts of random walks in universal quantum computing and their implementation using standard quantum circuits. Quantum walks have been recently well investigated for traversing graphs with certain oracles. We focus our study on traversing a 1D graph, namely a circle, and show how to implement a discrete-time quantum walk in quantum circuits built with universal CNOT and single qubit gates. We review elementary quantum gates and circuit decomposition techniques and propose a generalized version of all CNOT-based circuits of the quantum walk. We simulated these circuits on five different qubits IBM-Q quantum devices. This quantum computer has nonperfect gates based on superconducting qubits, and, therefore, we analyzed the impact of the CNOT errors and CNOT-depth on the fidelity of the circuit.

arXiv:2005.02447•International Journal of Quantum Information•Mar 1, 2021•3 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•4 citations

Efficient implementation of quantum walk-based algorithms into the quantum gate model of computation

Allan Wing Bocanegra

Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.

•Jan 1, 2023•0 citations
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 ddd-dimensional torus graphs and provide explicit circuit implementations for an 8-Cayley graph and a Z16×Z8\mathbb{Z}_{16} \times \mathbb{Z}_8Z16​×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≤64k \leq 64k≤64 for inverse-closed graphs and k≤16k \leq 16k≤16 for non-inverse-closed graphs, where kkk denotes the degree of the generating set. Benchmarking further reveals that this efficiency gain is largely insensitive to the system size NNN, identifying kkk 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.
This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.
Quantum walks have proven to be a universal model for quantum computation and to provide speed-up in certain quantum algorithms. The discrete-time quantum walk (DTQW) model, among others, is one of the most suitable candidates for circuit implementation due to its discrete nature. Current implementations, however, are usually characterized by quantum circuits of large size and depth, which leads to a higher computational cost and severely limits the number of time steps that can be reliably implemented on current quantum computers. In this work, we propose an efficient and scalable quantum circuit implementing the DTQW on the 2n-cycle based on the diagonalization of the conditional shift operator. For t time steps of the DTQW, the proposed circuit requires only O(n2+nt) two-qubit gates compared to the O(n2t) of the current most efficient implementation based on quantum Fourier transforms. We test the proposed circuit on an IBM quantum device for a Hadamard DTQW on the 4-cycle and 8-cycle characterized by periodic dynamics and by recurrent generation of maximally entangled single-particle states. Experimental results are meaningful well beyond the regime of few time steps, paving the way for reliable implementation and use on quantum computers.
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 investigate the counterparts of random walks in universal quantum computing and their implementation using standard quantum circuits. Quantum walks have been recently well investigated for traversing graphs with certain oracles. We focus our study on traversing a 1D graph, namely a circle, and show how to implement a discrete-time quantum walk in quantum circuits built with universal CNOT and single qubit gates. We review elementary quantum gates and circuit decomposition techniques and propose a generalized version of all CNOT-based circuits of the quantum walk. We simulated these circuits on five different qubits IBM-Q quantum devices. This quantum computer has nonperfect gates based on superconducting qubits, and, therefore, we analyzed the impact of the CNOT errors and CNOT-depth on the fidelity of the circuit.
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.
Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.