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:2402.01854 · Entropy

Efficient Implementation of Discrete-Time Quantum Walks on Quantum Computers

Luca Razzoli, Gabriele Cenedese, Maria Bondani, Giuliano Benenti

Published Apr 2, 2024• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.3390/e26040313

Related papers

Robust implementation of discrete-time quantum walks in any finite-dimensional quantum system

Biswayan Nandi, Sandipan Singha, Ankan Datta +2 more

Research has shown that quantum walks can accelerate certain quantum algorithms and act as a universal paradigm for quantum processing. The discrete-time quantum walk (DTQW) model, owing to its discrete nature, stands out as one of the most suitable choices for circuit implementation. Nevertheless, most current implementations are characterized by extensive, multi-layered quantum circuits, leading to higher computational expenses and a notable decrease in the number of confidently executable time steps on current quantum computers. Since quantum computers are not scalable enough in this NISQ era, we also must confine ourselves to the ancilla-free frontier zone. Therefore, in this paper, we have successfully cut down the circuit cost concerning gate count and circuit depth by half through our proposed methodology in qubit systems as compared to the state-of-the-art increment–decrement approach. Furthermore, for the engineering excellence of our proposed approach, we implement DTQW in any finite-dimensional quantum system with akin efficiency. To ensure an efficient implementation of quantum walks without requiring ancilla, we have incorporated an intermediate qudit technique for decomposing multi-qubit gates. Experimental outcomes hold significance far beyond the realm of just a few time steps, laying the groundwork for dependable implementation and utilization on quantum computers.

arXiv:2408.00530•Modern Physics Letters A•Mar 29, 2025•2 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

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

Seoyoon Kang

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.

quant-pharXiv:2608.25136•Aug 27, 2026•0 citations

Implementing arbitrary quantum operations via quantum walks on a cycle graph

Jia-Yi Lin, Xinyu Li, Yu-Hao Shao +2 more

The quantum circuit model is the most commonly used model for implementing quantum computers and quantum neural networks whose essential tasks are to realize certain unitary operations. The circuit model usually implements a desired unitary operation $U(N)$ by a sequence of single-qubit and two-qubit unitary gates from a universal set. Although this certainly facilitates the experimentalists as they only need to prepare several different kinds of universal gates, the number of gates required to implement an arbitrary desired unitary operation is usually large. Hence, the efficiency in terms of the circuit depth or running time is not guaranteed. Here we propose an alternative approach; we use a simple discrete-time quantum walk (DTQW) on a cycle graph to model an arbitrary unitary operation $U(N)$ without the need to decompose it into a sequence of gates of smaller sizes. Our model is essentially a quantum neural network based on DTQW. Firstly, it is universal as we show that any unitary operation $U(N)$ can be realized via an appropriate choice of coin operators. Secondly, our DTQW-based neural network can be updated efficiently via a learning algorithm, i.e., a modified stochastic gradient descent algorithm adapted to our network. By training this network, one can promisingly find approximations to arbitrary desired unitary operations. With an additional measurement on the output, the DTQW-based neural network can also implement general positive-operator-valued measure (POVM) measurements. We show its capacity in implementing arbitrary two-outcome POVMs via numeric simulation. We further demonstrate that the network can be simplified and can overcome device noises during the training so that it becomes more friendly for laboratory implementations. Our work shows the capability of the DTQW-based neural network in quantum computation and its potential in laboratory implementations.

arXiv:2210.14450•Physical Review A•Apr 5, 2023•5 citations

Implementing quantum walks with a single qubit

Qi-Ping Su, Shi-Chao Wang, Yan Chi +5 more

Quantum walks have wide applications in quantum information, such as universal quantum computation, so it is important to explore properties of quantum walks thoroughly. We propose a novel method to implement discrete-time quantum walks (DTQWs) using only a single qubit, in which both coin and walker are encoded in the two-dimensional state space of a single qubit, operations are realized using single-qubit gates only, and high-dimensional final states of DTQWs can be obtained naturally. With this "one-qubit" approach, DTQW experiments can be realized much more easily, compared with previous methods, in most quantum systems and all properties based on quantum states of DTQWs (such as quantum correlation and coherence) can be investigated. By this approach, we experimentally implement one-particle and two-particle DTQWs with seven steps using single photons. Furthermore, we systematically investigate quantum correlations and coherence (based on the full state of the coin and walker) of the DTQW systems with different initial states of the coin, which have not been obtained and studied in DTQW experiments. As an application, we also study the assisted distillation of quantum coherence using the full state of the two-particle DTQW from the experiment. The maximal increase in distillable coherence for high-dimensional mixed states is investigated for the first time by obtaining its upper and lower bounds. Our work opens a new door to implement DTQW experiments and to better explore properties of quantum walks.

arXiv:2206.03642•Jun 8, 2022•1 citation

Testing the Efficiency of Digital Simulation of Quantum Walks on IBM’s Q platform - towards quantum experimental algorithms

Luis Ángel Sedas

This thesis presents several quantum circuit implementations of discrete and continuous quantum walks in cycle graphs. Quantum walks have become an important tool for developing quantum algorithms, that is why this work is a contribution to the area of quantum computation, specially for scientist who want to test their developed algorithms, in a real quantum device as the IBM-Q Experience platform. We give a complete suite of quantum gates that are needed to simulate quantum walks and quantum walk-based algorithms. Since some of these quantum gates are not elementary, we show how to decompose them into fundamental quantum gates available at Qiskit, an open-source quantum computing software development framework created by IBM. This is an important contribution towards the development of a professional platform for simulating and testing quantum algorithms. We found that the decomposition of unitary gates, related to quantum walks, into elementary gates is not very well documented in the literature. We studied the efficiency of both, the number of qubits and logic gates needed for each circuit, and the correctness of the results of each experiment by comparing the theoretical expected output state with the output generated by quantum simulators. Implementations of both discrete and continuous quantum walks in quantum circuits rely heavily on controlled gates, that when decomposed into fundamental gates add a high number of quantum gates and depth. Experiments were performed on a real quantum device, but results showed that the quantum computer is not good enough when executing these quantum circuits, due to the depth of the circuits and the high amount of CNOT gates required. We tested different implementations and optimization methods for the simplification of the quantum circuits, were we find that resources grow linearly w.r.t the number of qubits, and the minimum amount of gates required for the discrete case in C8 was 144 quantum gates with a depth of 111, which is the reason of the error between the simulations and the implementations in the quantum device.

•Mar 14, 2020•0 citations
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.
Research has shown that quantum walks can accelerate certain quantum algorithms and act as a universal paradigm for quantum processing. The discrete-time quantum walk (DTQW) model, owing to its discrete nature, stands out as one of the most suitable choices for circuit implementation. Nevertheless, most current implementations are characterized by extensive, multi-layered quantum circuits, leading to higher computational expenses and a notable decrease in the number of confidently executable time steps on current quantum computers. Since quantum computers are not scalable enough in this NISQ era, we also must confine ourselves to the ancilla-free frontier zone. Therefore, in this paper, we have successfully cut down the circuit cost concerning gate count and circuit depth by half through our proposed methodology in qubit systems as compared to the state-of-the-art increment–decrement approach. Furthermore, for the engineering excellence of our proposed approach, we implement DTQW in any finite-dimensional quantum system with akin efficiency. To ensure an efficient implementation of quantum walks without requiring ancilla, we have incorporated an intermediate qudit technique for decomposing multi-qubit gates. Experimental outcomes hold significance far beyond the realm of just a few time steps, laying the groundwork for dependable implementation and utilization on quantum computers.
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.
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.
The quantum circuit model is the most commonly used model for implementing quantum computers and quantum neural networks whose essential tasks are to realize certain unitary operations. The circuit model usually implements a desired unitary operation U(N)U(N)U(N) by a sequence of single-qubit and two-qubit unitary gates from a universal set. Although this certainly facilitates the experimentalists as they only need to prepare several different kinds of universal gates, the number of gates required to implement an arbitrary desired unitary operation is usually large. Hence, the efficiency in terms of the circuit depth or running time is not guaranteed. Here we propose an alternative approach; we use a simple discrete-time quantum walk (DTQW) on a cycle graph to model an arbitrary unitary operation U(N)U(N)U(N) without the need to decompose it into a sequence of gates of smaller sizes. Our model is essentially a quantum neural network based on DTQW. Firstly, it is universal as we show that any unitary operation U(N)U(N)U(N) can be realized via an appropriate choice of coin operators. Secondly, our DTQW-based neural network can be updated efficiently via a learning algorithm, i.e., a modified stochastic gradient descent algorithm adapted to our network. By training this network, one can promisingly find approximations to arbitrary desired unitary operations. With an additional measurement on the output, the DTQW-based neural network can also implement general positive-operator-valued measure (POVM) measurements. We show its capacity in implementing arbitrary two-outcome POVMs via numeric simulation. We further demonstrate that the network can be simplified and can overcome device noises during the training so that it becomes more friendly for laboratory implementations. Our work shows the capability of the DTQW-based neural network in quantum computation and its potential in laboratory implementations.
Quantum walks have wide applications in quantum information, such as universal quantum computation, so it is important to explore properties of quantum walks thoroughly. We propose a novel method to implement discrete-time quantum walks (DTQWs) using only a single qubit, in which both coin and walker are encoded in the two-dimensional state space of a single qubit, operations are realized using single-qubit gates only, and high-dimensional final states of DTQWs can be obtained naturally. With this "one-qubit" approach, DTQW experiments can be realized much more easily, compared with previous methods, in most quantum systems and all properties based on quantum states of DTQWs (such as quantum correlation and coherence) can be investigated. By this approach, we experimentally implement one-particle and two-particle DTQWs with seven steps using single photons. Furthermore, we systematically investigate quantum correlations and coherence (based on the full state of the coin and walker) of the DTQW systems with different initial states of the coin, which have not been obtained and studied in DTQW experiments. As an application, we also study the assisted distillation of quantum coherence using the full state of the two-particle DTQW from the experiment. The maximal increase in distillable coherence for high-dimensional mixed states is investigated for the first time by obtaining its upper and lower bounds. Our work opens a new door to implement DTQW experiments and to better explore properties of quantum walks.
This thesis presents several quantum circuit implementations of discrete and continuous quantum walks in cycle graphs. Quantum walks have become an important tool for developing quantum algorithms, that is why this work is a contribution to the area of quantum computation, specially for scientist who want to test their developed algorithms, in a real quantum device as the IBM-Q Experience platform. We give a complete suite of quantum gates that are needed to simulate quantum walks and quantum walk-based algorithms. Since some of these quantum gates are not elementary, we show how to decompose them into fundamental quantum gates available at Qiskit, an open-source quantum computing software development framework created by IBM. This is an important contribution towards the development of a professional platform for simulating and testing quantum algorithms. We found that the decomposition of unitary gates, related to quantum walks, into elementary gates is not very well documented in the literature. We studied the efficiency of both, the number of qubits and logic gates needed for each circuit, and the correctness of the results of each experiment by comparing the theoretical expected output state with the output generated by quantum simulators. Implementations of both discrete and continuous quantum walks in quantum circuits rely heavily on controlled gates, that when decomposed into fundamental gates add a high number of quantum gates and depth. Experiments were performed on a real quantum device, but results showed that the quantum computer is not good enough when executing these quantum circuits, due to the depth of the circuits and the high amount of CNOT gates required. We tested different implementations and optimization methods for the simplification of the quantum circuits, were we find that resources grow linearly w.r.t the number of qubits, and the minimum amount of gates required for the discrete case in C8 was 144 quantum gates with a depth of 111, which is the reason of the error between the simulations and the implementations in the quantum device.