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

AIP conference proceedings

Measurement-enhanced quantum search

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

Published Jan 1, 2017• 1 citation
Publisher

Abstract

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.

DOI
10.1063/1.4996512

Related papers

A Fast Measurement based fixed-point Quantum Search Algorithm

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 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.

arXiv:1102.2332•International Conference on Quantum Information•Jan 1, 2011•3 citations

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

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 quantum search algorithm

Saptarshi Roy Chowdhury, Sudarshan Baruah, Biswaranjan Dikshit

Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.

Europhysics Letters (EPL)•Feb 8, 2023•2 citations

Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits

Sihyung Lee, Seung Yeob Nam

Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.

IEEE Access•Jan 1, 2024•7 citations

Simulation of Grover's algorithm with position-variation of the ancilla qubit

Neris Ilano, Ronald S. Banzon, Cristine Dlr. Villagonzalo

We simulate Grover’s quantum search algorithm in an Ising spin chain quantum computer with nearest and second-nearest neighbour interactions. We determine the optimum Rabi frequency that satisfies the 2πk method by selecting a high fidelity value in the frequency scan for each database size. Also, we vary the position of the ancilla qubit and investigate the effect on the fidelity for different sizes of the database. The behavior of the fidelity as a function of the number of Grover iterations during the algorithm is considered. For a fixed location of the ancilla qubit, the overall fidelity decreases as we increase the size of the database.

Proceedings of the Samahang Pisika ng Pilipinas•Jun 3, 2015•0 citations
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.
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 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.
Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.
Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.
We simulate Grover’s quantum search algorithm in an Ising spin chain quantum computer with nearest and second-nearest neighbour interactions. We determine the optimum Rabi frequency that satisfies the 2πk method by selecting a high fidelity value in the frequency scan for each database size. Also, we vary the position of the ancilla qubit and investigate the effect on the fidelity for different sizes of the database. The behavior of the fidelity as a function of the number of Grover iterations during the algorithm is considered. For a fixed location of the ancilla qubit, the overall fidelity decreases as we increase the size of the database.