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

Optics and Spectroscopy

Scattering quantum random walk

J. Košk

Published Aug 1, 2005• 1 citation
Publisher

Abstract

Random processes are of interest not only from the theoretical point of view but also for practical use in algorithms for investigating large combinatorial structures. The theory of quantum computing requires implementation of classical algorithms using quantum-mechanical devices, and random walk is an obvious candidate. We present a model for quantum random walk that is based on an interferometric analogy, can be easily implemented, and is a generalization of a former model of quantum random walk proposed by Aharonov and colleagues.

DOI
10.1134/1.2034608

Related papers

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

Advances in Random and Quantum Walks: Bridging Classical and Quantum Computational Paradigms

Anurag Soni, Akhtar Rasool, Dhirendra Pratap Singh

In the world of computational probing, random walks and quantum walks are two separate but tightly linked paradigms. Classical stochastic processes like random walks are based on the random movement of particles in mathematical space and have been extensively used in data mining, network analysis, computer vision, etc. Quantum walks, by contrast generalize random walks into the quantum realm, taking the benefit of the quantum superposition and interference in order to investigate multiple paths at the same time. Quantum walks provide significant potential for algorithmic development: in quantum computing and communication, and in Scientific modelling and simulation. This paper provides an in-depth survey of random walks and quantum walks, outlining historical context, fundamental principles, applications, challenges, and future prospects. In this paper, motivated by the abstractness of both random walks and quantum walks, we survey the field of computational exploration at large scales, coalescing the myriad notions and difficult challenges addressed by existing research efforts on random and quantum walks, inferring a nuanced and multifaceted view on how both random walks and quantum walks are involved in paving the way to future development in many fields.

Procedia Computer Science•Jan 1, 2025•1 citation

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•77 citations

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

•Dec 8, 2003•0 citations

Where to quantum walk

Viv M. Kendon

Quantum versions of random walks have diverse applications that are motivating experimental implementations as well as theoretical studies. However, the main impetus behind this interest is their use in quantum algorithms, which have always employed the quantum walk in the form of a program running on a quantum computer. Recent results showing that quantum walks are "universal for quantum computation" relate entirely to algorithms, and do not imply that a physical quantum walk could provide a new architecture for quantum computers. Nonetheless, quantum walks used to model transport phenomena in spin chains and biomolecules broaden their scope well beyond algorithms, and reopen the question of when a physical implementation might provide useful computational outputs. In this article we determine the conditions under which a physical quantum walk experiment could provide useful results beyond the reach of classical computation.

arXiv:1107.3795•Jul 19, 2011•13 citations

Random Walks: A Review of Algorithms and Applications

Feng Xia, Jiaying Liu, Hansong Nie +3 more

A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.

arXiv:2008.03639•IEEE Transactions on Emerging Topics in Computational Intelligence•Nov 25, 2019•329 citations
Random processes are of interest not only from the theoretical point of view but also for practical use in algorithms for investigating large combinatorial structures. The theory of quantum computing requires implementation of classical algorithms using quantum-mechanical devices, and random walk is an obvious candidate. We present a model for quantum random walk that is based on an interferometric analogy, can be easily implemented, and is a generalization of a former model of quantum random walk proposed by Aharonov and colleagues.
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.
In the world of computational probing, random walks and quantum walks are two separate but tightly linked paradigms. Classical stochastic processes like random walks are based on the random movement of particles in mathematical space and have been extensively used in data mining, network analysis, computer vision, etc. Quantum walks, by contrast generalize random walks into the quantum realm, taking the benefit of the quantum superposition and interference in order to investigate multiple paths at the same time. Quantum walks provide significant potential for algorithmic development: in quantum computing and communication, and in Scientific modelling and simulation. This paper provides an in-depth survey of random walks and quantum walks, outlining historical context, fundamental principles, applications, challenges, and future prospects. In this paper, motivated by the abstractness of both random walks and quantum walks, we survey the field of computational exploration at large scales, coalescing the myriad notions and difficult challenges addressed by existing research efforts on random and quantum walks, inferring a nuanced and multifaceted view on how both random walks and quantum walks are involved in paving the way to future development in many fields.
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.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem
Quantum versions of random walks have diverse applications that are motivating experimental implementations as well as theoretical studies. However, the main impetus behind this interest is their use in quantum algorithms, which have always employed the quantum walk in the form of a program running on a quantum computer. Recent results showing that quantum walks are "universal for quantum computation" relate entirely to algorithms, and do not imply that a physical quantum walk could provide a new architecture for quantum computers. Nonetheless, quantum walks used to model transport phenomena in spin chains and biomolecules broaden their scope well beyond algorithms, and reopen the question of when a physical implementation might provide useful computational outputs. In this article we determine the conditions under which a physical quantum walk experiment could provide useful results beyond the reach of classical computation.
A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.