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

Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial

Hugo Pillin

Published Apr 5, 2024• 0 citations
Publisher

Abstract

Discrete time quantum walk algorithms are the direct analogs of classical random walk algorithms, an important family in theoretical informatics. They can solve a variety of problems, in particular the NPcomplete SAT problem, in a relatively short time. Thus, the study of quantum walks could lead to the conception of new quantum algorithms. Among the quantum algorithms, one of the most extensively studied is Grover’s searchalgorithm, an iterative process that can find one element among N that meet a certain criterion, with a quadratic time gain over any classical algorithm. In this thesis, we study the variant of Grover’s search algorithm proposed by Shenvi, Kempe and Whaley, based on walks on hypercube graphs.As search algorithms are iterative processes, one has to compute the correct number of steps R before running the search, as the probability of success decreases past a certain point. The value of R depends on the number of elements N, but also the number of solutions M. For Grover's algorithm, the optimal number of iterations is well known, but this is not the case for the search on the hypercube as soon as there are multiple solutions. In this thesis, we propose an extensive eigenanalysis of the hypercube search algorithm, which leads to a procedure that allows us to compute the probability of success of the search algorithm on the hypercube without running it, in polynomial time.

DOI
10.70675/45a8a01fz7b20z40b8z813czab274c7b9a64

Related papers

Quantum walk search algorithm on hypercube : eigenanalysis and calculation of the probability of success in polynomial time

Hugo Pillin

Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial Les algorithmes de marche quantique à temps discret sont les analogues directs des algorithmes de marche aléatoire classiques, une famille importante en informatique. Ils peuvent résoudre une variété de problèmes, dont le problème NP-complet SAT, en un temps relativement court. Ainsi, l'étude des marches quantiques pourrait amener à la conception de nouveaux algorithmes quantiques. Parmi les algorithmes quantiques, l'un des plus étudiés est l'algorithme de recherche de Grover, un processus itératif qui peut trouver un élément parmi N qui répond à un certain critère, avec un gain de temps quadratique par rapport à n'importe quel algorithme classique. Dans cette thèse, on étudie la variante de l'algorithme de recherche de Grover proposée par Shenvi, Kempe et Whaley, basée sur les marches sur les graphes hypercubes. Comme les algorithmes de recherche sont des processus itératifs, il faut calculer le nombre correct d'étapes R avant de lancer la recherche, car la probabilité de succès diminue au-delà d'un certain point. La valeur de R dépend du nombre d'éléments N, mais aussi du nombre de solutions M. Pour l'algorithme de Grover, le nombre optimal d'itérations est bien connu, mais ce n'est pas le cas pour la recherche sur l'hypercube dès qu'il y a plusieurs solutions. Dans cette thèse, on propose une analyse propre exhaustive de l'algorithme de recherche sur l'hypercube, qui conduit à une procédure permettant de calculer la probabilité de succès de l'algorithme de recherche sur l'hypercube sans l'exécuter, en temps polynomial.

•Apr 5, 2024•0 citations

Optimized quantum random-walk search algorithms on the hypercube

Václav Potoček, A. Gábris, T. Kiss +1 more

Shenvi, Kempe, and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require $O(\sqrt{N})$ number of oracle queries to find the marked element, where $N$ is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield a significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.

arXiv:0805.4347•Physical Review A•Jan 28, 2009•115 citations

Hypercube quantum search: exact computation of the probability of success in polynomial time

Hugo Pillin, Gilles Burel, Paul Baird +2 more

Abstract In the emerging domain of quantum algorithms, Grover’s quantum search is certainly one of the most significant. It is relatively simple, performs a useful task and more importantly, does it in an optimal way. However, due to the success of quantum walks in the field, it is logical to study quantum search variants over several kinds of walks. In this paper, we propose an in-depth study of the quantum search over a hypercube layout. First, through the analysis of elementary walk operators restricted to suitable eigenspaces, we show that the acting component of the search algorithm takes place in a small subspace of the Hilbert workspace that grows linearly with the problem size. Subsequently, we exploit this property to predict the exact evolution of the probability of success of the quantum search in polynomial time.

arXiv:2202.12973•Quantum Information Processing•Mar 15, 2023•2 citations

Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube

Yao-Yao Jiang, Peng-Cheng Chu, Wenbin Zhang +1 more

Shenvi et al. have proposed a quantum algorithm based on quantum walking called Shenvi–Kempe–Whaley (SKW) algorithm, but this search algorithm can only search one target state and use a specific search target state vector. Therefore, when there are more than two target nodes in the search space, the algorithm has certain limitations. Even though a multi-objective SKW search algorithm was proposed later, when the number of target nodes is more than two, the SKW search algorithm cannot be mapped to the same quotient graph. In addition, the calculation of the optimal target state depends on the number of target states m. In previous studies, quantum computing and testing algorithms were used to solve this problem. But these solutions require more Oracle calls and cannot get a high accuracy rate. Therefore, to solve the above problems, we improve the multi-target quantum walk search algorithm, and construct a controllable quantum walk search algorithm under the condition of unknown number of target states. By dividing the Hilbert space into multiple subspaces, the accuracy of the search algorithm is improved from p c = (1/2) – O(1/n) to p c = 1 – O(1/n). And by adding detection gate phase, the algorithm can stop when the amplitude of the target state becomes the maximum for the first time, and the algorithm can always maintain the optimal number of iterations, so as to reduce the number of unnecessary iterations in the algorithm process and make the number of iterations reach <?CDATA ${t}_{{\rm{f}}}=(\pi /2)\sqrt{{2}^{n-2}}$?> t f = ( π / 2 ) 2 n − 2 .

Chinese Physics B•Sep 18, 2021•1 citation

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

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.

Acta Physica Sinica•Jan 1, 2015•0 citations

Optimized quantum random-walk search algorithm for multi-solution search

Yuchao Zhang, Wan‐Su Bao, Xiang Wang +1 more

This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q . For a given q , we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.

Chinese Physics B•Nov 1, 2015•7 citations
Discrete time quantum walk algorithms are the direct analogs of classical random walk algorithms, an important family in theoretical informatics. They can solve a variety of problems, in particular the NPcomplete SAT problem, in a relatively short time. Thus, the study of quantum walks could lead to the conception of new quantum algorithms. Among the quantum algorithms, one of the most extensively studied is Grover’s searchalgorithm, an iterative process that can find one element among N that meet a certain criterion, with a quadratic time gain over any classical algorithm. In this thesis, we study the variant of Grover’s search algorithm proposed by Shenvi, Kempe and Whaley, based on walks on hypercube graphs.As search algorithms are iterative processes, one has to compute the correct number of steps R before running the search, as the probability of success decreases past a certain point. The value of R depends on the number of elements N, but also the number of solutions M. For Grover's algorithm, the optimal number of iterations is well known, but this is not the case for the search on the hypercube as soon as there are multiple solutions. In this thesis, we propose an extensive eigenanalysis of the hypercube search algorithm, which leads to a procedure that allows us to compute the probability of success of the search algorithm on the hypercube without running it, in polynomial time.
Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial Les algorithmes de marche quantique à temps discret sont les analogues directs des algorithmes de marche aléatoire classiques, une famille importante en informatique. Ils peuvent résoudre une variété de problèmes, dont le problème NP-complet SAT, en un temps relativement court. Ainsi, l'étude des marches quantiques pourrait amener à la conception de nouveaux algorithmes quantiques. Parmi les algorithmes quantiques, l'un des plus étudiés est l'algorithme de recherche de Grover, un processus itératif qui peut trouver un élément parmi N qui répond à un certain critère, avec un gain de temps quadratique par rapport à n'importe quel algorithme classique. Dans cette thèse, on étudie la variante de l'algorithme de recherche de Grover proposée par Shenvi, Kempe et Whaley, basée sur les marches sur les graphes hypercubes. Comme les algorithmes de recherche sont des processus itératifs, il faut calculer le nombre correct d'étapes R avant de lancer la recherche, car la probabilité de succès diminue au-delà d'un certain point. La valeur de R dépend du nombre d'éléments N, mais aussi du nombre de solutions M. Pour l'algorithme de Grover, le nombre optimal d'itérations est bien connu, mais ce n'est pas le cas pour la recherche sur l'hypercube dès qu'il y a plusieurs solutions. Dans cette thèse, on propose une analyse propre exhaustive de l'algorithme de recherche sur l'hypercube, qui conduit à une procédure permettant de calculer la probabilité de succès de l'algorithme de recherche sur l'hypercube sans l'exécuter, en temps polynomial.
Shenvi, Kempe, and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require O(N)O(\sqrt{N})O(N​) number of oracle queries to find the marked element, where NNN is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield a significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.
Abstract In the emerging domain of quantum algorithms, Grover’s quantum search is certainly one of the most significant. It is relatively simple, performs a useful task and more importantly, does it in an optimal way. However, due to the success of quantum walks in the field, it is logical to study quantum search variants over several kinds of walks. In this paper, we propose an in-depth study of the quantum search over a hypercube layout. First, through the analysis of elementary walk operators restricted to suitable eigenspaces, we show that the acting component of the search algorithm takes place in a small subspace of the Hilbert workspace that grows linearly with the problem size. Subsequently, we exploit this property to predict the exact evolution of the probability of success of the quantum search in polynomial time.
Shenvi et al. have proposed a quantum algorithm based on quantum walking called Shenvi–Kempe–Whaley (SKW) algorithm, but this search algorithm can only search one target state and use a specific search target state vector. Therefore, when there are more than two target nodes in the search space, the algorithm has certain limitations. Even though a multi-objective SKW search algorithm was proposed later, when the number of target nodes is more than two, the SKW search algorithm cannot be mapped to the same quotient graph. In addition, the calculation of the optimal target state depends on the number of target states m. In previous studies, quantum computing and testing algorithms were used to solve this problem. But these solutions require more Oracle calls and cannot get a high accuracy rate. Therefore, to solve the above problems, we improve the multi-target quantum walk search algorithm, and construct a controllable quantum walk search algorithm under the condition of unknown number of target states. By dividing the Hilbert space into multiple subspaces, the accuracy of the search algorithm is improved from p c = (1/2) – O(1/n) to p c = 1 – O(1/n). And by adding detection gate phase, the algorithm can stop when the amplitude of the target state becomes the maximum for the first time, and the algorithm can always maintain the optimal number of iterations, so as to reduce the number of unnecessary iterations in the algorithm process and make the number of iterations reach <?CDATA tf=(π/2)2n−2{t}_{{\rm{f}}}=(\pi /2)\sqrt{{2}^{n-2}}tf​=(π/2)2n−2​?> t f = ( π / 2 ) 2 n − 2 .
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.
This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q . For a given q , we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.