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:1102.2332 · International Conference on Quantum Information

A Fast Measurement based fixed-point Quantum Search Algorithm

Ashish Mani, C. Patvardhan

Published Jan 1, 2011• 3 citations
arXivHTMLPDF

Abstract

Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover’s quantum rotation transform to reach near the vicinity of the target entity represented by a basis state in the Hilbert space associated with the qubits. Thus, when qubits are measured, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in the unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is at least greater than half for all the ratios of the number of target entities to the total number of entities in a database, which are less than half. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires an additional ancilla qubit.

DOI
10.1364/icqi.2011.qmi28

Related papers

A Fast fixed-point Quantum Search Algorithm by using Disentanglement and Measurement

Ashish Mani, C. Patvardhan

Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover's quantum rotation transform to reach near the vicinity of the target entity. Thus, upon measurement, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in an unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed-point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by disentanglement, measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is greater than half for all practically significant ratios of the number of target entities to the total number of entities in a database. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires two additional ancilla qubits.

arXiv:1203.3178•Mar 14, 2012•2 citations

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

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

Robust Quantum Search with Uncertain Number of Target States

Yuanyue Zhu, Zeguo Wang, Bao Yan +1 more

The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.

Entropy•Dec 8, 2021•5 citations

Ancilla-mediated fixed-point quantum search using Grover iterations

Yash Prabhat, Snigdha Thakur, Ankur Raina

Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\sqrt{N})$. However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, $M$, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least $92.6\%$ with a query complexity of approximately $\mathcal{O}(\sqrt{N/M})$, effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.

quant-pharXiv:2608.29839•Sep 1, 2026•0 citations

Measurement-enhanced quantum search

Neris I. Sombillo, Ronald S. Banzon, Cristine Dlr. Villagonzalo

The oscillatory nature of the unitary Grover operator makes quantum searching difficult if one has no prior knowledge of the number of target states in the database. In this work, we coupled the database to an external qubit to transfer the target state in a space where the quantum search operation is not applied. This is followed by a measurement of the external and the ancilla qubit which result to a mixed state with a higher probability of finding the target state. The algorithm is simulated in a spin chain having first and second order neighbor interactions. The result shows that the oscillation is suppressed and the probability of success generally increased with iteration number.

AIP conference proceedings•Jan 1, 2017•1 citation
Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover’s quantum rotation transform to reach near the vicinity of the target entity represented by a basis state in the Hilbert space associated with the qubits. Thus, when qubits are measured, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in the unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is at least greater than half for all the ratios of the number of target entities to the total number of entities in a database, which are less than half. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires an additional ancilla qubit.
Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover's quantum rotation transform to reach near the vicinity of the target entity. Thus, upon measurement, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in an unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed-point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by disentanglement, measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is greater than half for all practically significant ratios of the number of target entities to the total number of entities in a database. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires two additional ancilla qubits.
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.
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.
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.
Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from O(N)\mathcal{O}(N)O(N) to O(N)\mathcal{O}(\sqrt{N})O(N​). However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, MMM, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least 92.6%92.6\%92.6% with a query complexity of approximately O(N/M)\mathcal{O}(\sqrt{N/M})O(N/M​), effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.
The oscillatory nature of the unitary Grover operator makes quantum searching difficult if one has no prior knowledge of the number of target states in the database. In this work, we coupled the database to an external qubit to transfer the target state in a space where the quantum search operation is not applied. This is followed by a measurement of the external and the ancilla qubit which result to a mixed state with a higher probability of finding the target state. The algorithm is simulated in a spin chain having first and second order neighbor interactions. The result shows that the oscillation is suppressed and the probability of success generally increased with iteration number.