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:2011.04051

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

Published Nov 8, 2020• 4 citations
arXivHTMLPDF

Abstract

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

DOI
10.48550/arxiv.2011.04051

Related papers

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard, Peter Høyer +1 more

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.

arXiv:quant-ph/9605034•Fortschritte der Physik•Jun 1, 1998•1,338 citations

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

arXiv:quant-ph/0507234•Physical Review A•Feb 3, 2006•3 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•9 citations

Optimization of a probabilistic quantum search algorithm with a priori information

Yutong Huang, Shengshi Pang

A quantum computer encodes information in quantum states and runs quantum algorithms to surpass the classical counterparts by exploiting quantum superposition and quantum correlation. Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. It has a quadratic reduction in the query complexity of a database search and is known to be optimal when no a priori information about the elements of the database is provided. In this work we consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements and minimize the number of oracle calls by optimizing the initial state of the quantum system and the reflection axis of the diffusion operator. The initial state and the reflection axis are allowed to not coincide and thus the quantum search algorithm rotates the quantum system in a three-dimensional subspace spanned by the initial state, the reflection axis, and the search target state in general. The number of oracle calls is minimized by a variational method, and formal results are obtained with the assumption of low failure probability. The results show that for a nonuniform a priori distribution of the database elements, the number of oracle calls can be significantly reduced given a small decrease in the success probability of the quantum search algorithm, leading to a lower average query complexity to find the solution of the search problem. The results are applied to a simple but nontrivial database model with two-value a priori probabilities to show the power of the optimized quantum search algorithm. The paper concludes with a discussion about the generalization to higher-order results that allows for a larger failure probability for the quantum search algorithm.

arXiv:2304.02856•Physical Review A•Aug 18, 2023•6 citations

Implementing a deterministic search algorithm with a single qubit

Chen-Hui Peng, Liang Bin, Xin He +3 more

Abstract Quantum search algorithms have important applications in quantum information, which have been experimentally demonstrated in several quantum systems with database sizes up to 16. We first propose an efficient quantum search scheme based on an optimized Grover’s algorithm and a novel encoding method. With this scheme, a target element can be deterministically searched in a large database using only a single qubit. Then we implement this search scheme in linear optics with database sizes up to 40. Experimental results fit well with the theoretical results, with all fidelities greater than 99.7%. The limitation of the number of elements encoded in a single qubit is also investigated in the experiment. The experimental results indicate that a target state can be successfully searched from a database of size 36 using a single qubit in our laboratory. Since only one qubit and one-qubit gates are required, this search scheme is quite efficient and general, and can be adopted to implement the same task in most quantum systems.

Progress of Theoretical and Experimental Physics•Mar 1, 2023•1 citation

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•1 citation
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size NNN by using only O(N)O(\sqrt{N})O(N​) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either MMM or KKK, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let mmm be the required number of iterations; we prove that under certain restrictions on the sizes of MMM and KKK the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.
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.
A quantum computer encodes information in quantum states and runs quantum algorithms to surpass the classical counterparts by exploiting quantum superposition and quantum correlation. Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. It has a quadratic reduction in the query complexity of a database search and is known to be optimal when no a priori information about the elements of the database is provided. In this work we consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements and minimize the number of oracle calls by optimizing the initial state of the quantum system and the reflection axis of the diffusion operator. The initial state and the reflection axis are allowed to not coincide and thus the quantum search algorithm rotates the quantum system in a three-dimensional subspace spanned by the initial state, the reflection axis, and the search target state in general. The number of oracle calls is minimized by a variational method, and formal results are obtained with the assumption of low failure probability. The results show that for a nonuniform a priori distribution of the database elements, the number of oracle calls can be significantly reduced given a small decrease in the success probability of the quantum search algorithm, leading to a lower average query complexity to find the solution of the search problem. The results are applied to a simple but nontrivial database model with two-value a priori probabilities to show the power of the optimized quantum search algorithm. The paper concludes with a discussion about the generalization to higher-order results that allows for a larger failure probability for the quantum search algorithm.
Abstract Quantum search algorithms have important applications in quantum information, which have been experimentally demonstrated in several quantum systems with database sizes up to 16. We first propose an efficient quantum search scheme based on an optimized Grover’s algorithm and a novel encoding method. With this scheme, a target element can be deterministically searched in a large database using only a single qubit. Then we implement this search scheme in linear optics with database sizes up to 40. Experimental results fit well with the theoretical results, with all fidelities greater than 99.7%. The limitation of the number of elements encoded in a single qubit is also investigated in the experiment. The experimental results indicate that a target state can be successfully searched from a database of size 36 using a single qubit in our laboratory. Since only one qubit and one-qubit gates are required, this search scheme is quite efficient and general, and can be adopted to implement the same task in most quantum systems.
We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.