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:0906.3094 · Journal of Physics A Mathematical and Theoretical

Quantum search algorithms on the hypercube

Birgit Hein, Gregor Tanner

Published Jan 30, 2009• 26 citations
arXivHTMLPDF

Abstract

We investigate a set of discrete-time quantum search algorithms on the n -dimensional hypercube following a proposal by Shenvi et al (2003 Phys. Rev. A 67 052307). We show that there exists a whole class of quantum search algorithms in the symmetry-reduced space which perform a search of a marked vertex in time of order where N = 2 n , the number of vertices. In analogy to Grover's algorithm, the spatial search is effectively facilitated through a rotation in a two-level subspace of the full Hilbert space. In the hypercube, these two-level systems are introduced through avoided crossings. We give estimates on the quantum states forming the two-level subspaces at the avoided crossings and derive improved estimates on the search times.

DOI
10.1088/1751-8113/42/8/085303

Related papers

Quantum search algorithms on a regular lattice

Birgit Hein, Gregor Tanner

Quantum algorithms for searching for one or more marked items on a $d$-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For $d=2$ and $d=3$, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.

arXiv:1005.3676•Physical Review A•Jul 23, 2010•40 citations

Quantum search algorithms

Birgit Hein

In this thesis two quantum search algorithms on two different graphs, a hypercube and a d-dimensional square lattice, are analysed and some applications of the lattice search are discussed.\nThe approach in this thesis generalises a picture drawn by Shenvi, Kempe and Whaley, which was later adapted by Ambainis, Kempe and Rivosh. It defines a one parameter family of unitary operators U_λ with parameter λ. It will be shown that two eigenvalues of U_λ form an avoided crossing at the λ-value where U_λ is equal to the old search operator.\nThis generalised picture opens the way for a construction of two approximate eigen- vectors at the crossing and gives rise to a 2×2 model Hamiltonian that is used to approximate the operator U_λ near the crossing. The thus defined Hamiltonian can be used to calculate the leading order of search time and success probability for the search. To the best of my knowledge only the scaling of these quantities has been known.\nFor the algorithm searching the regular lattice, a generalisation of the model Hamiltonian for m target vertices is constructed. This algorithm can be used to send a signal from one vertex of the graph to a set of vertices. The signal is transmitted between these vertices exclusively and is localised only on the sender and the receiving vertices while the probability to measure the signal at one of the remaining vertices is significantly smaller.\nHowever, this effect can be used to introduce an additional sender to search settings and send a continuous signal to all target vertices where the signal will localise. This effect is an improvement compared to the original search algorithm as it does not need to know the number of target vertices.

•Oct 15, 2010•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

Spatial search on Johnson graphs by discrete-time quantum walk

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744•Journal of Physics A Mathematical and Theoretical•May 12, 2022•9 citations

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

Hugo Pillin

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.

•Apr 5, 2024•0 citations

Decoherence in Search Algorithms

Gonzalo Abal, R. Donangelo, Franklin de Lima Marquezino +2 more

Recently several quantum search algorithms based on quantum walks were proposed. Those algorithms differ from Grover's algorithm in many aspects. The goal is to find a marked vertex in a graph faster than classical algorithms. Since the implementation of those new algorithms in quantum computers or in other quantum devices is error-prone, it is important to analyze their robustness under decoherence. In this work we analyze the impact of decoherence on quantum search algorithms implemented on two-dimensional grids and on hypercubes.

arXiv:0912.1523•Dec 8, 2009•9 citations
We investigate a set of discrete-time quantum search algorithms on the n -dimensional hypercube following a proposal by Shenvi et al (2003 Phys. Rev. A 67 052307). We show that there exists a whole class of quantum search algorithms in the symmetry-reduced space which perform a search of a marked vertex in time of order where N = 2 n , the number of vertices. In analogy to Grover's algorithm, the spatial search is effectively facilitated through a rotation in a two-level subspace of the full Hilbert space. In the hypercube, these two-level systems are introduced through avoided crossings. We give estimates on the quantum states forming the two-level subspaces at the avoided crossings and derive improved estimates on the search times.
Quantum algorithms for searching for one or more marked items on a ddd-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For d=2d=2d=2 and d=3d=3d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.
In this thesis two quantum search algorithms on two different graphs, a hypercube and a d-dimensional square lattice, are analysed and some applications of the lattice search are discussed.\nThe approach in this thesis generalises a picture drawn by Shenvi, Kempe and Whaley, which was later adapted by Ambainis, Kempe and Rivosh. It defines a one parameter family of unitary operators U_λ with parameter λ. It will be shown that two eigenvalues of U_λ form an avoided crossing at the λ-value where U_λ is equal to the old search operator.\nThis generalised picture opens the way for a construction of two approximate eigen- vectors at the crossing and gives rise to a 2×2 model Hamiltonian that is used to approximate the operator U_λ near the crossing. The thus defined Hamiltonian can be used to calculate the leading order of search time and success probability for the search. To the best of my knowledge only the scaling of these quantities has been known.\nFor the algorithm searching the regular lattice, a generalisation of the model Hamiltonian for m target vertices is constructed. This algorithm can be used to send a signal from one vertex of the graph to a set of vertices. The signal is transmitted between these vertices exclusively and is localised only on the sender and the receiving vertices while the probability to measure the signal at one of the remaining vertices is significantly smaller.\nHowever, this effect can be used to introduce an additional sender to search settings and send a continuous signal to all target vertices where the signal will localise. This effect is an improvement compared to the original search algorithm as it does not need to know the number of target vertices.
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 The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.
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.
Recently several quantum search algorithms based on quantum walks were proposed. Those algorithms differ from Grover's algorithm in many aspects. The goal is to find a marked vertex in a graph faster than classical algorithms. Since the implementation of those new algorithms in quantum computers or in other quantum devices is error-prone, it is important to analyze their robustness under decoherence. In this work we analyze the impact of decoherence on quantum search algorithms implemented on two-dimensional grids and on hypercubes.