Abstract The objective of Grover’s quantum algorithm is to efficiently identify a single solution within a search space. However, there are search problems that require finding all possible solutions. A direct, repeated application of Grover’s algorithm is unsuitable for these problems, as it lacks an internal mechanism to avoid rediscovering previous solutions. Here we introduce a quantum algorithm that efficiently and deterministically discovers all solutions by preparing special initial states of the index register, a step accomplished by leveraging knowledge from solutions obtained during execution. We experimentally demonstrate our algorithm on a superconducting quantum processor. This work provides quantum examples for search scenarios with some knowledge about solutions.
Abstract The objective of Grover’s quantum algorithm is to efficiently identify a single solution within a search space. However, there are search problems that require finding all possible solutions. A direct, repeated application of Grover’s algorithm is unsuitable for these problems, as it lacks an internal mechanism to avoid rediscovering previous solutions. Here we introduce a quantum algorithm that efficiently and deterministically discovers all solutions by preparing special initial states of the index register, a step accomplished by leveraging knowledge from solutions obtained during execution. We experimentally demonstrate our algorithm on a superconducting quantum processor. This work provides quantum examples for search scenarios with some knowledge about solutions.
Grover’s algorithm leverages quantum computing to efficiently locate solutions in unstructured search spaces, outperforming classical approaches. Since Grover’s algorithm requires prior knowledge of the number of solutions (M) within a search space of size N, previous studies assume M is estimated beforehand and focus on identifying all solutions. Here, we propose a two-step process that integrates both the estimation of M and the discovery of the solutions, optimizing the interactions between the two steps. To enhance efficiency, the estimation step captures as many solutions as possible, leaving the discovery step to focus on the remaining ones. To ensure accuracy, the discovery step continues searching until the probability of finding additional solutions becomes sufficiently low. We implemented and evaluated our methods, showing that over 80% of solutions were found during the estimation phase, allowing the discovery phase to conclude earlier, while identifying over 99% of solutions on average. In theory, the process requires NM × log(M) Grover’s iterations in the worst case, but in practice, it typically terminates after iterations proportional to N. We expect that our methods will be applicable to various search problems and inspire further research on efficiently finding all solutions.
Searching for index corresponding to a given data in an unsorted database represents a nontrivial unstructured search problem with wide-ranging applications in fields like data mining, cryptography, and bio-informatics. Unlike the reverse query, where the data can be trivially obtained from a known index, retrieving the index from data lacks order preservation, making efficient classical search infeasible without linear traversal. To address this problem, we propose a deterministic quantum search algorithm, which provides a solution for the database having any arbitrary number of entries while always guaranteeing success in a single execution. The algorithm is formulated within the quantum circuit model, employing amplitude manipulation techniques that eliminate probabilistic outcomes and ensure exact retrieval of the location of data. We present a scalable circuit construction adaptable to databases of varying sizes, without constraints such as number of entries equal to power-of-two. Because of its adaptability, the proposed algorithm is directly applicable to real-world datasets without the need for costly pre-processing or ineffective data padding. The proposed work presents a resilient and exact technique for the quantum index retrieval problem by providing a solution offering wide applicability and dependable outputs. Our findings shows a clear way towards quantum primitives that can be easily included into deterministic computing workflows, bridging the gap between theoretical speedup and the real-world requirement for dependable outputs.
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.
Abstract—Quantum mechanical computers unlike classical computers can be in a superposition of states and carry out multiple operations at the same time. Grover has shown that a quantum computer can do a random database search in O ( √ N) steps. He has further proved that using the superposition of the states in quantum computing, a quantum computer should be able to do a search in a single step. He has stated that the query generated to do this search will require Ω(NlogN) steps. In this paper we aim at optimizing the Grover’s search algorithm. In our algorithm, we have repeated the inversion step a number of times instead of stopping after a single step. Measurement after a single step required a larger number of subsystems which impaired the effectiveness of the algorithm leading to Ω(NlogN) steps in the preparation and processing of the query. Repetition of the inversion step brought the the number of subsystems down drastically by increasing the amplitude of the desired state.We have proved that by doing so the overall effectiveness of Grover’s algorithm can be brought down to Ω ( 3 √ N). Keywords: Quantum mechanical computers, Grover’s search algorithm, inversion step, probability and amplitude.
We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.