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

Quantum Random Walk Search and Grover's Algorithm - An Introduction and Neutral-Atom Approach

Anna Maria Houk

Published Jan 1, 2020• 0 citations
OpenAlex

Abstract

In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using neutral-atom (also known as cold-atom) quantum computing to physically implement two types of quantum random walks and Grover’s algorithm.

Related papers

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.

Cambridge University Press eBooks•Dec 23, 2022•11 citations

Grover Search

Chris Godsil, Hanmeng Zhan

1. Grover Search: We introduce the basics of discrete quantum walks, describing some of the underlying physics. One of the most important algorithms in quantum computing is Grover’s search algorithm, we show how one can implement this algorithm using a discrete walk on the arcs of a graph.

Cambridge University Press eBooks•Dec 23, 2022•0 citations

Quantum random walk search on satisfiability problems

Stephan Hoyer

Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.

•Jan 1, 2008•6 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

A random walk approach to quantum algorithms

Viv M. Kendon

The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.

arXiv:quant-ph/0609035•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 18, 2006•116 citations

Evolution of Quantum Computing Based on Grover's Search Algorithm

Prakhar Shrivastava, Kapil Kumar Soni, Akhtar Rasool

Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•18 citations
In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using neutral-atom (also known as cold-atom) quantum computing to physically implement two types of quantum random walks and Grover’s algorithm.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.
Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.
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 development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.