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

Acta Physica Sinica

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

Published Jan 1, 2015• 0 citations
Publisher

Abstract

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

DOI
10.7498/aps.64.240301

Related papers

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.

International Journal of Quantum Information•Jul 24, 2026•0 citations

Scattering quantum walk search algorithm on star graph

Liu Yan-Mei, Hanwu Chen, Zhihao Liu +2 more

Quantum walk is a typical quantum computing model which is receiving significant attention in recent years from theory researchers. In this paper, we prove that the two major formulations for discrete quantum walks, coined and scattering, are unitarily equivalent on star graph. We then propose a new quantum search algorithm on star graph based on the scattering quantum walk. It is shown that the temporal complexity of the algorithm is the same as that in Grover algorithm, but success probability is greater than that in Grover algorithm when the objects are more than one third of total items.

Acta Physica Sinica•Jan 1, 2015•5 citations

A Quantum Walk Enhanced Grover Search Algorithm for Global Optimization

Yan Wang

One of the significant breakthroughs in quantum computation is Grover's algorithm for unsorted database search. Recently, the applications of Grover's algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed so that the search is accelerated with improved threshold values. By taking advantage of the quantum tunneling effect, better threshold values can be found at the early stage of the search process so that the sharpness of probability improves. The results between the new algorithm, existing Grover search, and classical heuristic algorithms are compared.

arXiv:1711.07825•Nov 18, 2017•7 citations

Efficient implementation of quantum walk-based algorithms into the quantum gate model of computation

Allan Wing Bocanegra

Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.

•Jan 1, 2023•0 citations

Global Optimization With Quantum Walk Enhanced Grover Search

Yan Wang

One of the significant breakthroughs in quantum computation is Grover’s algorithm for unsorted database search. Recently, the applications of Grover’s algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed. By taking advantage of quantum tunneling effect, local barriers are overcome and better threshold values can be found at the early stage of search process. The new algorithm based on the formalism is demonstrated with benchmark examples of global optimization. The results between the new algorithm and the Grover search method are also compared.

ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC/CIE)•Aug 17, 2014•8 citations

Data Search Algorithms based on Quantum Walk

Masataka Fujisaki, Hiromi Miyajima, Noritaka Shigei

For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.

Lecture notes in computer science•Jan 1, 2012•2 citations
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
Quantum walk is a typical quantum computing model which is receiving significant attention in recent years from theory researchers. In this paper, we prove that the two major formulations for discrete quantum walks, coined and scattering, are unitarily equivalent on star graph. We then propose a new quantum search algorithm on star graph based on the scattering quantum walk. It is shown that the temporal complexity of the algorithm is the same as that in Grover algorithm, but success probability is greater than that in Grover algorithm when the objects are more than one third of total items.
One of the significant breakthroughs in quantum computation is Grover's algorithm for unsorted database search. Recently, the applications of Grover's algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed so that the search is accelerated with improved threshold values. By taking advantage of the quantum tunneling effect, better threshold values can be found at the early stage of the search process so that the sharpness of probability improves. The results between the new algorithm, existing Grover search, and classical heuristic algorithms are compared.
Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.
One of the significant breakthroughs in quantum computation is Grover’s algorithm for unsorted database search. Recently, the applications of Grover’s algorithm to solve global optimization problems have been demonstrated, where unknown optimum solutions are found by iteratively improving the threshold value for the selective phase shift operator in Grover rotation. In this paper, a hybrid approach that combines continuous-time quantum walks with Grover search is proposed. By taking advantage of quantum tunneling effect, local barriers are overcome and better threshold values can be found at the early stage of search process. The new algorithm based on the formalism is demonstrated with benchmark examples of global optimization. The results between the new algorithm and the Grover search method are also compared.
For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.