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

Implementing arbitrary quantum operations via quantum walks on a cycle graph

Jia-Yi Lin, Xinyu Li, Yu-Hao Shao, Wei Wang, Shengjun Wu

Published Apr 5, 2023• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.107.042405

Related papers

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

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

Quantum circuit design using neural networks assisted by entanglement

Carolina Allende, Efrain Buksman, André Fonseca de Oliveira

This work introduces a novel structure based on universal quantum circuits which uses classical machine learning techniques in order to solve a quantum problem: the decomposition of a generic quantum operator into a sequence of elementary unitary matrices (universal basic quantum gates). Even though the postulates of quantum mechanics guarantee any unitary operation as a feasible operation over a quantum system, there is no simple method to implement an arbitrary algorithm. By means of a multilayer hybrid neural network in which the basic cell is made up of CNOTs and universal one-qubit unitary gates, this work offers a solution to the given problem. These specific gates were chosen since they are the gates available in real quantum computers such as IBMQ's quantum processors. The network learns the unitary gates classically using the method of the steepest descent and is aided in learning the entangling gates by the use of two types of quantum correlations: Mutual Information (MI) and Cumulative Correlation Measure (CCM). The algorithm implemented in this case is a type of supervised learning. The results show that the model fits the data gracefully and correctly predicts a wide range of algorithms.

IEEE URUCON•Nov 24, 2021•0 citations

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

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
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 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.
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.
This work introduces a novel structure based on universal quantum circuits which uses classical machine learning techniques in order to solve a quantum problem: the decomposition of a generic quantum operator into a sequence of elementary unitary matrices (universal basic quantum gates). Even though the postulates of quantum mechanics guarantee any unitary operation as a feasible operation over a quantum system, there is no simple method to implement an arbitrary algorithm. By means of a multilayer hybrid neural network in which the basic cell is made up of CNOTs and universal one-qubit unitary gates, this work offers a solution to the given problem. These specific gates were chosen since they are the gates available in real quantum computers such as IBMQ's quantum processors. The network learns the unitary gates classically using the method of the steepest descent and is aided in learning the entangling gates by the use of two types of quantum correlations: Mutual Information (MI) and Cumulative Correlation Measure (CCM). The algorithm implemented in this case is a type of supervised learning. The results show that the model fits the data gracefully and correctly predicts a wide range of algorithms.
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.
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.