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

Quantum Searching amidst large uncertainties

D. Li, Xiao-Ming Li, Hongtao Huang, Xinxin Li

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

The quantum search algorithm is a way for finding an item with desired properties in an unsorted database of size N in only$\\sqrt{N}$ steps by means of a sequence of selective inversion and quantum diffusion operations. However, like most quantum algorithms, this requires the algorithm to execute the precise sequence of operations, any further probing into the database only worsens the result. Grover recently showed that by replacing the selective inversion by selective phase shifts of $\\pi /3$, the algorithm converges to the desired item monotonically. This paper builds on that result and considers the problem of retrieving a marked item from a database containing an unknown fraction of marked items, say $\\epsilon $. We derive optimal algorithms for different ranges of $\\epsilon .$ These are similar to Grover's recent algorithm but the phase shift turns out to vary with $\\epsilon $ - this is generally quite different from $\\pi /3$.

Related papers

Fixed-Point Quantum Search

Lov K. Grover

The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size N in only sqrt[N] queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of pi/3, the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.

arXiv:quant-ph/0503205•Physical Review Letters•Oct 3, 2005•209 citations

Research on Quantum Searching Algorithms Based on Phase Shifts

Zhong Pu-Cha, Wan‐Su Bao

One iterative in Grover's original quantum search algorithm consists of two Hadamard–Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary ϕ = ϕ(0 ⩽ ϕ, ϕ ⩽ 2π). Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.5π/ iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%.

Chinese Physics Letters•Jul 29, 2008•7 citations

Quantum Algorithms with Fixed Points: The Case of Database Search

Lov K. Grover, Apoorva D. Patel, Tathagat Tulsi

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\fracπ{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $ε$ to $ε^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

arXiv:quant-ph/0603132•Mar 15, 2006•3 citations

PHASE MATCHING IN FIXED-POINT QUANTUM SEARCH ALGORITHM

Hong‐Fu Wang, Shou Zhang, Yongfang Zhao

We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.

International Journal of Quantum Information•Sep 1, 2009•2 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

Faster quantum searching with almost any diffusion operator

Avatar Tulsi

Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of ${I}_{s}$, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator ${D}_{s}$ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of $O(B)$, where $B$ is a characteristic of the eigenspectrum of ${D}_{s}$ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still $O(B)$ times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.

arXiv:1503.05712•Physical Review A•May 7, 2015•10 citations
The quantum search algorithm is a way for finding an item with desired properties in an unsorted database of size N in onlysqrtN\\sqrt{N}sqrtN steps by means of a sequence of selective inversion and quantum diffusion operations. However, like most quantum algorithms, this requires the algorithm to execute the precise sequence of operations, any further probing into the database only worsens the result. Grover recently showed that by replacing the selective inversion by selective phase shifts of pi/3\\pi /3pi/3, the algorithm converges to the desired item monotonically. This paper builds on that result and considers the problem of retrieving a marked item from a database containing an unknown fraction of marked items, say epsilon\\epsilon epsilon. We derive optimal algorithms for different ranges of epsilon.\\epsilon .epsilon. These are similar to Grover's recent algorithm but the phase shift turns out to vary with epsilon\\epsilon epsilon - this is generally quite different from pi/3\\pi /3pi/3.
The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size N in only sqrt[N] queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of pi/3, the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.
One iterative in Grover's original quantum search algorithm consists of two Hadamard–Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary ϕ = ϕ(0 ⩽ ϕ, ϕ ⩽ 2π). Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.5π/ iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%.
The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of π3\fracπ{3}3π​. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using qqq oracle queries, these variations reduce the probability of finding a non-target state from εεε to ε2q+1ε^{2q+1}ε2q+1, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.
We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.
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.
Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of Is{I}_{s}Is​, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator Ds{D}_{s}Ds​ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of O(B)O(B)O(B), where BBB is a characteristic of the eigenspectrum of Ds{D}_{s}Ds​ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still O(B)O(B)O(B) times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.