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

Cambridge University Press eBooks

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Published Dec 23, 2022• 15 citations
Publisher

Abstract

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.

DOI
10.1017/9781009261692

Related papers

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

A classical approach to the graph isomorphism problem using quantum walks

B. L. Douglas, J. B. Wang

Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.

arXiv:0705.2531•Journal of Physics A Mathematical and Theoretical•Feb 5, 2008•124 citations

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

Anna Maria Houk

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.

•Jan 1, 2020•0 citations

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

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Quantum algorithms have the potential to demonstrate that for some problems quantum computation is more efficient than classical computation. A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. In our survey we present recent quantum algorithms for basic problems from graph and algebra theory. The quantum algorithms for these problems use a combination of Grovers search algorithms, quantum amplitude amplification and quantum random walks. These quantum algorithms are faster than the best known classical algorithms for the corresponding problems. Keywords: Quantum computing, quantum algorithms, graph theory, algebra, quantum query complexity

Recent Advances in Computer Science and Communications•Jun 1, 2009•0 citations

Discrete quantum walks and quantum image processing

Salvador Elías Venegas-Andraca

In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.

•Jan 1, 2005•19 citations
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.
Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.
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.
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.
Quantum algorithms have the potential to demonstrate that for some problems quantum computation is more efficient than classical computation. A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. In our survey we present recent quantum algorithms for basic problems from graph and algebra theory. The quantum algorithms for these problems use a combination of Grovers search algorithms, quantum amplitude amplification and quantum random walks. These quantum algorithms are faster than the best known classical algorithms for the corresponding problems. Keywords: Quantum computing, quantum algorithms, graph theory, algebra, quantum query complexity
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.