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

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

Luis Ángel Sedas

Published Mar 14, 2020• 0 citations
OpenAlex

Abstract

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.

Related papers

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

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

Cycle discrete-time quantum walks on a noisy quantum computer

Vivek Wadhia, Nicholas Chancellor, Viv M. Kendon

Abstract The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quantum walk. Implementing an 8-node, 8-step walk and a simpler 4-node, 4-step discrete-time quantum walk on an IBM quantum device known as , the results for each step of the respective walks are presented. A custom noise model is developed in order to estimate that noise levels in the quantum device would need to be reduced by at least 94% in order to execute a 16-node, 16-step cycle discrete-time quantum walk to a reasonable level of fidelity. Graphic abstract

arXiv:2307.11027•The European Physical Journal D•Mar 1, 2024•9 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

Implementation of quantum random walk on a real quantum computer

Warat Puengtambol, Prapong Prechaprapranwong, Unchalisa Taetragool

Abstract A random walk is one of the widely adopted random processes for simulation and approximation in multiple areas of science and engineering. Quantum random walk is an analog version of the classical random walk. It was first introduced in 1993 by Y. Aharonov et al. They presented that, with the nature of quantum characteristic, the average length of the walking path on a line is possible to larger than a classical random walk can produce. Therefore, the quantum random walk can be used as a tool to construct many other quantum algorithms. Moreover, it can solve graph problems that many real-world problems can be formulated. However, quantum algorithms are only useful in practice if we can implement them efficiently on a quantum computer. In this study, we are then interested in designing and implementing a quantum circuit that can be run on a real quantum computing device. We firstly focus on the most straightforward, which is a one-dimension, quantum random walk algorithm. Then, the quantum circuits are developed and implemented on a real quantum computer and a quantum computing simulator using software development kits provided by IBM. Lastly, the performance and results of the quantum circuits tested on both computing platforms are presented.

Journal of Physics Conference Series•Jan 1, 2021•11 citations

Optimal Quantum Circuit Decomposition of Reversible Gates on IBM quantum computer

Hilal Ahmad Bhat, Farooq Ahmad Khanday, Khurshed Ahmad Shah

Currently, computing paradigm is ruled by the laws of classical physics and will continue till the dimensions of transistors reaches the size of atomic particles. Quantum computing (QC) is a new technology that employs laws of quantum mechanics to address issues such as irreversibility and power dissipation that are outside the scope of conventional computing models. QC offers a powerful stage for solving complex and compound problems like searching and number factoring. A critical task in utilizing quantum physics in many application fields is circuit design using reversible quantum gates. Unitary decomposition is a popular scheme for mapping quantum algorithms to any set of elementary quantum operations. Using decomposition techniques enables transformation of unitary matrices into fundamental quantum gates, which is critical for running algorithms on prevailing quantum computers. Any 3x3 reversible quantum gate can be decomposed into single-qubit rotation gates and two qubit CNOT gates. This paper is the first to present quantum implementations of FRSG1 and JTF1 gates into CNOT gates and single qubit U3 gates with different optimization levels on a platform provided by IBM. These gates are important in a variety of practical applications like Stochastic computing and parity generation circuits. In FRSG1 the implementation count of single qubit gates decreases by 56% and the count of two qubit gates by 15% after optimization, whereas in JTF1 gate the single qubit gate count reduces by 71% and the number of two qubit gates reduces by 41%.

International Conference on Multimedia, Signal Processing and Communication Technologies (IMPACT)•Nov 26, 2022•3 citations
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.
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.
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.
Abstract The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quantum walk. Implementing an 8-node, 8-step walk and a simpler 4-node, 4-step discrete-time quantum walk on an IBM quantum device known as , the results for each step of the respective walks are presented. A custom noise model is developed in order to estimate that noise levels in the quantum device would need to be reduced by at least 94% in order to execute a 16-node, 16-step cycle discrete-time quantum walk to a reasonable level of fidelity. Graphic 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.
Abstract A random walk is one of the widely adopted random processes for simulation and approximation in multiple areas of science and engineering. Quantum random walk is an analog version of the classical random walk. It was first introduced in 1993 by Y. Aharonov et al. They presented that, with the nature of quantum characteristic, the average length of the walking path on a line is possible to larger than a classical random walk can produce. Therefore, the quantum random walk can be used as a tool to construct many other quantum algorithms. Moreover, it can solve graph problems that many real-world problems can be formulated. However, quantum algorithms are only useful in practice if we can implement them efficiently on a quantum computer. In this study, we are then interested in designing and implementing a quantum circuit that can be run on a real quantum computing device. We firstly focus on the most straightforward, which is a one-dimension, quantum random walk algorithm. Then, the quantum circuits are developed and implemented on a real quantum computer and a quantum computing simulator using software development kits provided by IBM. Lastly, the performance and results of the quantum circuits tested on both computing platforms are presented.
Currently, computing paradigm is ruled by the laws of classical physics and will continue till the dimensions of transistors reaches the size of atomic particles. Quantum computing (QC) is a new technology that employs laws of quantum mechanics to address issues such as irreversibility and power dissipation that are outside the scope of conventional computing models. QC offers a powerful stage for solving complex and compound problems like searching and number factoring. A critical task in utilizing quantum physics in many application fields is circuit design using reversible quantum gates. Unitary decomposition is a popular scheme for mapping quantum algorithms to any set of elementary quantum operations. Using decomposition techniques enables transformation of unitary matrices into fundamental quantum gates, which is critical for running algorithms on prevailing quantum computers. Any 3x3 reversible quantum gate can be decomposed into single-qubit rotation gates and two qubit CNOT gates. This paper is the first to present quantum implementations of FRSG1 and JTF1 gates into CNOT gates and single qubit U3 gates with different optimization levels on a platform provided by IBM. These gates are important in a variety of practical applications like Stochastic computing and parity generation circuits. In FRSG1 the implementation count of single qubit gates decreases by 56% and the count of two qubit gates by 15% after optimization, whereas in JTF1 gate the single qubit gate count reduces by 71% and the number of two qubit gates reduces by 41%.