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

arXiv:0706.0304 · Physical Review A

Efficient quantum circuit implementation of quantum walks

B. L. Douglas, Jingbo B. Wang

Published May 27, 2009• 98 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.79.052335

Related papers

Can quantum walks provide practical exponential speedups

B. L. Douglas, Jingbo B. Wang

Quantum walks, being the quantum analogue 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.

•Jun 3, 2007•1 citation

Quantum random-walk search algorithm

Neil Shenvi, Julia Kempe, K. Birgitta Whaley

Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with $O(\sqrt{N})$ calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.

arXiv:quant-ph/0210064•Physical Review A•May 23, 2003•1,140 citations

Efficient circuit implementation of quantum walks on non-degree-regular graphs

T. Loke, Jingbo B. Wang

This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.

Physical Review A•Oct 31, 2012•18 citations

Complexity Analysis of Quantum Walk Based Search Algorithms

B. L. Douglas, Jingbo B. Wang

We present several families of graphs that allow both efficient quantum walk implementations and efficient quantum walk based search algorithms. For these graphs, we construct quantum circuits that explicitly implement the full quantum walk search algorithm, without reference to a `black box' oracle. These circuits provide a practically implementable method to explore quantum walk based search algorithms with the aim of eventual real-world applications. We also provide a numerical analysis of a quantum walk based search along a twisted toroid family of graphs, which requires O($\sqrt{n}$ log($n$)) elementary 2-qubit quantum gate operations to find a marked node.

arXiv:1408.1616•Journal of Computational and Theoretical Nanoscience•Jun 20, 2013•7 citations

Quantum Walk-Based Algorithms for Large-Scale Graph Search

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to large-scale graph search problems. Classical algorithms often struggle with the computational complexity of exploring vast graphs, particularly when searching for specific patterns or nodes. Quantum walks, inspired by the probabilistic nature of random walks, provide a promising alternative by utilizing quantum superposition and interference to accelerate the search process. We explore the theoretical framework and potential advantages of employing quantum walks for graph traversal, focusing on scenarios where exponential speedups are theoretically possible. This work aims to demonstrate the potential of quantum computing to tackle computationally demanding graph search tasks that are currently intractable for classical methods. The core concept leverages the ability to simultaneously explore multiple paths within a graph, drastically reducing the search time compared to sequential exploration. We present a foundational understanding of quantum walk implementation and analyze its suitability for various graph search algorithms.

•Aug 28, 2026•0 citations

Quantum Walk-Based Graph Search Algorithms

Jincheng Zhang

This paper explores the application of quantum walk algorithms for graph search problems. Classical graph search algorithms, such as Dijkstra's algorithm, frequently encounter limitations when dealing with large graphs, often exhibiting performance bottlenecks due to exhaustive exploration of the graph's nodes. We propose a novel approach utilizing quantum walks to address these challenges. Quantum walks exploit quantum superposition and interference to facilitate a more efficient exploration of the graph space compared to their classical counterparts. The theoretical framework presented investigates the potential for exponential speedups in graph search operations. We formally define the quantum walk model and its implementation for graph traversal, outlining the key steps involved in constructing a quantum algorithm. This work focuses on the theoretical aspects of the algorithm, providing a foundation for future experimental investigations and optimization.

•Sep 5, 2026•0 citations
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.
Quantum walks, being the quantum analogue 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.
Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with O(N)O(\sqrt{N})O(N​) calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.
This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.
We present several families of graphs that allow both efficient quantum walk implementations and efficient quantum walk based search algorithms. For these graphs, we construct quantum circuits that explicitly implement the full quantum walk search algorithm, without reference to a `black box' oracle. These circuits provide a practically implementable method to explore quantum walk based search algorithms with the aim of eventual real-world applications. We also provide a numerical analysis of a quantum walk based search along a twisted toroid family of graphs, which requires O(n\sqrt{n}n​ log(nnn)) elementary 2-qubit quantum gate operations to find a marked node.
This paper investigates the application of quantum walk algorithms to large-scale graph search problems. Classical algorithms often struggle with the computational complexity of exploring vast graphs, particularly when searching for specific patterns or nodes. Quantum walks, inspired by the probabilistic nature of random walks, provide a promising alternative by utilizing quantum superposition and interference to accelerate the search process. We explore the theoretical framework and potential advantages of employing quantum walks for graph traversal, focusing on scenarios where exponential speedups are theoretically possible. This work aims to demonstrate the potential of quantum computing to tackle computationally demanding graph search tasks that are currently intractable for classical methods. The core concept leverages the ability to simultaneously explore multiple paths within a graph, drastically reducing the search time compared to sequential exploration. We present a foundational understanding of quantum walk implementation and analyze its suitability for various graph search algorithms.
This paper explores the application of quantum walk algorithms for graph search problems. Classical graph search algorithms, such as Dijkstra's algorithm, frequently encounter limitations when dealing with large graphs, often exhibiting performance bottlenecks due to exhaustive exploration of the graph's nodes. We propose a novel approach utilizing quantum walks to address these challenges. Quantum walks exploit quantum superposition and interference to facilitate a more efficient exploration of the graph space compared to their classical counterparts. The theoretical framework presented investigates the potential for exponential speedups in graph search operations. We formally define the quantum walk model and its implementation for graph traversal, outlining the key steps involved in constructing a quantum algorithm. This work focuses on the theoretical aspects of the algorithm, providing a foundation for future experimental investigations and optimization.