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

Geometric Analysis of Grover's Search Algorithm in the Presence of Perturbation

Wenliang Jin

Published Jul 1, 2013• 0 citations
OpenAlex

Abstract

"For an initial uniform superposition over all pos- sible computational basis states, we explore the perfor- mance of Grover’s search algorithm geometrically when imposing a perturbation on the Walsh-Hadamard trans- formation contained in the Grover iteration. We give the geometric picture to visualize the quantum search process in the three-dimensional space and show that Grover’s search algorithm can work well with an appropriately chosen per- turbation. Thereby we corroborate Grover’s conclusion that if the perturbation is small, then it will have little impact on the implementation of this algorithm. We also prove that Grover’s path cannot achieve a geodesic under a perturba- tion of the Fubini-Study metric."

Related papers

An improved formalism for the Grover search algorithm

James M. Chappell, Max A. Lohe, Lorenz von Smekal +2 more

The Grover search algorithm is one of the two key algorithms in the field of quantum computing, and hence it is of significant interest to describe it in the most efficient mathematical formalism. We show firstly, that Clifford's formalism of geometric algebra, provides a significantly more efficient representation than the conventional Bra-ket notation, and secondly, that the basis defined by the states of maximum and minimum weight in the Grover search space, allows a simple visualization of the Grover search as the precession of a spin-1/2 particle. Using this formalism we efficiently solve the exact search problem, as well as easily representing more general search situations.

arXiv:1201.1707•Jan 9, 2012•2 citations

Geometric Analysis of Grover’s Search Algorithmin the Presence of Perturbation

Wenliang Jin

Brazilian Journal of Physics•Jan 27, 2014•1 citation

Family of Grover’s quantum-searching algorithms

Alberto Galindo, Miguel Angel Martin-Delgado

We introduce the concepts of Grover operators and Grover kernels to systematically analyze Grover's searching algorithms. Then we investigate a one-parameter family of quantum searching algorithms of Grover type and we show that the standard Grover algorithm is a distinguished member of this family. We show that all the algorithms of this class solve the searching problem with an efficiency of order $O(\sqrt{N}),$ with a coefficient which is class-dependent. The analysis of this dependence is a test of the stability and robustness of the algorithms. We show the stability of this constructions under perturbations of the initial conditions and extend them to a very general class of Grover operators.

arXiv:quant-ph/0009086•Physical Review A•Nov 8, 2000•50 citations

An extention of Grover's quantum search algorithm (Foundations of Computer Science)

Keisuke Tanaka

Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time $O(\sqrt{N})$ with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where $N=2^{n}$ , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is $\Omega(N)$ .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in $O(\sqrt{N})$ time.

数理解析研究所講究録•Apr 1, 2000•0 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•0 citations

Algebraic analysis of quantum search with pure and mixed states

Daniel Shapira, Yishai Shimoni, Ofer Biham

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.

arXiv:quant-ph/0504149•Physical Review A•Apr 12, 2005•11 citations
"For an initial uniform superposition over all pos- sible computational basis states, we explore the perfor- mance of Grover’s search algorithm geometrically when imposing a perturbation on the Walsh-Hadamard trans- formation contained in the Grover iteration. We give the geometric picture to visualize the quantum search process in the three-dimensional space and show that Grover’s search algorithm can work well with an appropriately chosen per- turbation. Thereby we corroborate Grover’s conclusion that if the perturbation is small, then it will have little impact on the implementation of this algorithm. We also prove that Grover’s path cannot achieve a geodesic under a perturba- tion of the Fubini-Study metric."
The Grover search algorithm is one of the two key algorithms in the field of quantum computing, and hence it is of significant interest to describe it in the most efficient mathematical formalism. We show firstly, that Clifford's formalism of geometric algebra, provides a significantly more efficient representation than the conventional Bra-ket notation, and secondly, that the basis defined by the states of maximum and minimum weight in the Grover search space, allows a simple visualization of the Grover search as the precession of a spin-1/2 particle. Using this formalism we efficiently solve the exact search problem, as well as easily representing more general search situations.
We introduce the concepts of Grover operators and Grover kernels to systematically analyze Grover's searching algorithms. Then we investigate a one-parameter family of quantum searching algorithms of Grover type and we show that the standard Grover algorithm is a distinguished member of this family. We show that all the algorithms of this class solve the searching problem with an efficiency of order O(N),O(\sqrt{N}),O(N​), with a coefficient which is class-dependent. The analysis of this dependence is a test of the stability and robustness of the algorithms. We show the stability of this constructions under perturbations of the initial conditions and extend them to a very general class of Grover operators.
Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time O(N)O(\sqrt{N})O(N​) with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where N=2nN=2^{n}N=2n , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is Ω(N)\Omega(N)Ω(N) .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in O(N)O(\sqrt{N})O(N​) time.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
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 nnn 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.