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

Journal of Physics Conference Series

Implementation of quantum random walk on a real quantum computer

Warat Puengtambol, Prapong Prechaprapranwong, Unchalisa Taetragool

Published Jan 1, 2021• 11 citations
Publisher

Abstract

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.

DOI
10.1088/1742-6596/1719/1/012103

Related papers

Design of Quantum Circuits for Random Walk Algorithms

Amlan Chakrabarti, Chia-Chun Lin, Niraj Kumar Jha

A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. Quantum random walks on a graph, which are analogous to classical stochastic walk, form the basis for some of the recent quantum algorithms that promise to significantly outperform existing classical random walk algorithms. Though research has been done on the application of quantum random walk to important computational problems, very little work has been done on its quantum circuit design. There are two types of quantum random walk algorithms: discrete-time and continuous-time. In this paper, we propose quantum circuit designs for both types of random walk algorithms that operate on various graphs. We consider in detail two important problems to which random walk algorithms are applicable: the triangle finding problem and binary welded tree problem. Though there exist a few research works related to quantum circuit design for random walk on graphs, to the best of our knowledge, the circuit designs we present here are first of their kind. We also provide an estimate of the quantum cost of these circuits for several physical machine descriptions (PMDs)of quantum systems, based on the number of quantum operations and execution cycles.

IEEE Computer Society Annual Symposium on VLSI•Aug 1, 2012•9 citations

Quantum Walk Computing: Theory, Implementation, and Application

Xiaogang Qiang, Shixin Ma, Haijing Song

The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.

arXiv:2404.04178•Intelligent Computing•Jan 1, 2024•55 citations

Efficient quantum circuit implementation of quantum walks

B. L. Douglas, Jingbo B. Wang

Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the ``glued trees'' algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.

arXiv:0706.0304•Physical Review A•May 27, 2009•98 citations

Quantum walk processes in quantum devices

Anandu Kalleri Madhu, Alexey A. Melnikov, Leonid Evgenevich Fedichkin +2 more

Simulation and programming of current quantum computers as Noisy Intermediate-Scale Quantum (NISQ) devices represent a hot topic at the border of current physical and information sciences. The quantum walk process represents a basic subroutine in many quantum algorithms and plays an important role in studying physical phenomena. Simulating quantum walk processes is computationally challenging for classical processors. With an increasing improvement in qubits fidelity and qubits number in a single register, there is a potential to improve quantum walks simulations substantially. However, efficient ways to simulate quantum walks in qubit registers still have to be explored. Here, we explore the relationship between quantum walk on graphs and quantum circuits. Firstly, we discuss ways to obtain graphs provided quantum circuit. We then explore techniques to represent quantum walk on a graph as a quantum circuit. Specifically, we study hypercube graphs and arbitrary graphs. Our approach to studying the relationship between graphs and quantum circuits paves way for the efficient implementation of quantum walks algorithms on quantum computers.

arXiv:2012.14386•Heliyon•Feb 7, 2023•4 citations

One-dimensional Hadamard Quantum Walk on a Cycle with Rotational Implementation

Κωνσταντίνος Γεωργόπουλος, Paolo Zuliani

Quantum walks have been extensively studied recently, mainly due to their vast difference in behavior to classical random walks. This paper is concerned with discrete time and space quantum walks of particles that propagate through a one-dimensional line. This line can be either a lattice or a graph or any other form of mathematical structure that can be viewed as a one-dimensional line. First is defined a concrete way to describe the unitary evolution of a quantum walk through a balanced coin operator and a shift operator. Then follows the implementation of the quantum walk on an $8$-cycle, i.e a cycle graph with $8$ nodes, which is then run locally as a simulation and on IBM's quantum computer. The paper explores two implementations of the quantum walk as a quantum circuit: the first one consists of generalised controlled inversions, as introduced in \cite{EffWalk}, whereas the second one tries to replace them with rotation operators around the basis states. The main aim is to find a way around the caveat resulting from the large amount of ancilla qubits required to carry out the computation in the case where only generalised inverters are used. Next, another three experiments are computed, involving cycles with a larger state space, more specifically $16$, $32$ and $64$ possible positions. In order to measure the magnitude of the error of the circuit we use the cross entropy benchmarking method, calculated through the Hellinger distance. Finally, a derivation of the variance of the quantum walk is provided along with a calculation of the variance for our experiment.

•Nov 1, 2019•2 citations

Efficient quantum walk on a quantum processor

Xiaogang Qiang, T. Loke, Ashley Montanaro +5 more

The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.

arXiv:1510.08657•Nature Communications•May 5, 2016•108 citations
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.
A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. Quantum random walks on a graph, which are analogous to classical stochastic walk, form the basis for some of the recent quantum algorithms that promise to significantly outperform existing classical random walk algorithms. Though research has been done on the application of quantum random walk to important computational problems, very little work has been done on its quantum circuit design. There are two types of quantum random walk algorithms: discrete-time and continuous-time. In this paper, we propose quantum circuit designs for both types of random walk algorithms that operate on various graphs. We consider in detail two important problems to which random walk algorithms are applicable: the triangle finding problem and binary welded tree problem. Though there exist a few research works related to quantum circuit design for random walk on graphs, to the best of our knowledge, the circuit designs we present here are first of their kind. We also provide an estimate of the quantum cost of these circuits for several physical machine descriptions (PMDs)of quantum systems, based on the number of quantum operations and execution cycles.
The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.
Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the ``glued trees'' algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.
Simulation and programming of current quantum computers as Noisy Intermediate-Scale Quantum (NISQ) devices represent a hot topic at the border of current physical and information sciences. The quantum walk process represents a basic subroutine in many quantum algorithms and plays an important role in studying physical phenomena. Simulating quantum walk processes is computationally challenging for classical processors. With an increasing improvement in qubits fidelity and qubits number in a single register, there is a potential to improve quantum walks simulations substantially. However, efficient ways to simulate quantum walks in qubit registers still have to be explored. Here, we explore the relationship between quantum walk on graphs and quantum circuits. Firstly, we discuss ways to obtain graphs provided quantum circuit. We then explore techniques to represent quantum walk on a graph as a quantum circuit. Specifically, we study hypercube graphs and arbitrary graphs. Our approach to studying the relationship between graphs and quantum circuits paves way for the efficient implementation of quantum walks algorithms on quantum computers.
Quantum walks have been extensively studied recently, mainly due to their vast difference in behavior to classical random walks. This paper is concerned with discrete time and space quantum walks of particles that propagate through a one-dimensional line. This line can be either a lattice or a graph or any other form of mathematical structure that can be viewed as a one-dimensional line. First is defined a concrete way to describe the unitary evolution of a quantum walk through a balanced coin operator and a shift operator. Then follows the implementation of the quantum walk on an 888-cycle, i.e a cycle graph with 888 nodes, which is then run locally as a simulation and on IBM's quantum computer. The paper explores two implementations of the quantum walk as a quantum circuit: the first one consists of generalised controlled inversions, as introduced in \cite{EffWalk}, whereas the second one tries to replace them with rotation operators around the basis states. The main aim is to find a way around the caveat resulting from the large amount of ancilla qubits required to carry out the computation in the case where only generalised inverters are used. Next, another three experiments are computed, involving cycles with a larger state space, more specifically 161616, 323232 and 646464 possible positions. In order to measure the magnitude of the error of the circuit we use the cross entropy benchmarking method, calculated through the Hellinger distance. Finally, a derivation of the variance of the quantum walk is provided along with a calculation of the variance for our experiment.
The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.