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.
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.
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.
Shenvi, Kempe, and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require O(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.
An algebraic analysis of Grover's quantum search algorithm is presented for the case in which the initial state is an arbitrary pure quantum state $\ensuremath{\mid}\ensuremath{\psi}⟩$ of n qubits. This approach reveals the geometrical structure of the quantum search process, which turns out to be confined to a four-dimensional subspace of the Hilbert space. It unifies and generalizes earlier results on the time evolution of the amplitudes during the search, the optimal number of iterations, and the success probability. Furthermore, it enables a direct generalization to the case in which the initial state is a mixed state, providing an exact formula for the success probability.
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.
The application of quantum principles in computing has garnered interest since the 1980s. Today, this concept is not only theoretical, but we have the means to design and execute techniques that leverage the quantum principles to perform calculations. The emergence of the quantum walk search technique exemplifies the practical application of quantum concepts and their potential to revolutionize information technologies. It promises to be versatile and may be applied to various problems. For example, the coined quantum walk search allows for identifying a marked item in a combinatorial search space, such as the quantum hypercube. The quantum hypercube organizes the qubits such that the qubit states represent the vertices and the edges represent the transitions to the states differing by one qubit state. It offers a novel framework to represent k-mer graphs in the quantum realm. Thus, the quantum hypercube facilitates the exploitation of parallelism, which is made possible through superposition and entanglement to search for a marked k-mer. However, as found in the analysis of the results, the search is only sometimes successful in hitting the target. Thus, through a meticulous examination of the quantum walk search circuit outcomes, evaluating what input-target combinations are useful, and a visionary exploration of DNA k-mer search, this paper opens the door to innovative possibilities, laying down the groundwork for further research to bridge the gap between theoretical conjecture in quantum computing and a tangible impact in bioinformatics.
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.