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

Entropy

Robust Quantum Search with Uncertain Number of Target States

Yuanyue Zhu, Zeguo Wang, Bao Yan, Shijie Wei

Published Dec 8, 2021• 5 citations
Publisher

Abstract

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

DOI
10.3390/e23121649

Related papers

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

Shang Bin

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.

arXiv:quant-ph/0604059•Communications in Theoretical Physics•Aug 1, 2007•3 citations

Improved quantum multi-object search algorithm

Wei-Yun Ma

Grover’s quantum mechanical search algorithm solves the unsorted database search with quadratic speed-up over the classical algorithms.But Grover’s algorithm will be inefficient when the number of matching is close to 2n/2.This paper presents a quantum algorithm which can get a target item with certainty by a single query when the number of the target items is more than a quarter.

Computer Engineering and Applications Journal•Jan 1, 2009•0 citations

Analysis of Grover’S Quantum Search Algorithm on a Classical Computer

Necati Çelik, Özkan Bingöl

In this paper, Grover's quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states.The calculations show that the marked state can be found in 𝒪(√𝑁) iterations, where 𝑁 = 2 ( is the number of items.The possibility of improving Grover's search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states.The calculations showed that the marked state could be found with sufficiently high probability in 𝒪(ln (𝑁)) iterations.This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.

Sigma Journal of Engineering and Natural Sciences – Sigma Mühendislik ve Fen Bilimleri Dergisi•Jan 1, 2022•6 citations

Grover algorithm with zero theoretical failure rate

Gui‐Lu Long

In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the $(J+1)\mathrm{th}$ iteration, the marked state is obtained with certainty.

arXiv:quant-ph/0106071•Physical Review A•Jul 11, 2001•481 citations

Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method*

Tan Li, Shuo Zhang, Xiang-Qun Fu +4 more

For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.

arXiv:1912.01773•Chinese Physics B•Nov 1, 2019•8 citations

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•4 citations
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%.
An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.
In this paper, Grover's quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states.The calculations show that the marked state can be found in 𝒪(√𝑁) iterations, where 𝑁 = 2 ( is the number of items.The possibility of improving Grover's search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states.The calculations showed that the marked state could be found with sufficiently high probability in 𝒪(ln (𝑁)) iterations.This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.
In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the (J+1)th(J+1)\mathrm{th}(J+1)th iteration, the marked state is obtained with certainty.
For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.
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.