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:0708.0808 · Physical Review A

Statistical comparison of ensemble implementations of Grover’s search algorithm to classical sequential searches

Tomasz M. Kott, David C. Collins

Published May 13, 2008• 1 citation
arXivHTMLPDF

Abstract

We compare pseudopure state ensemble implementations, quantified by their initial polarization and ensemble size, of Grover's search algorithm to probabilistic classical sequential search algorithms in terms of their success and failure probabilities. We propose a criterion for quantifying the resources used by the ensemble implementation via the aggregate number of oracle invocations across the entire ensemble and use this as a basis for comparison with classical search algorithms. We determine bounds for a critical polarization such that the ensemble algorithm succeeds with a greater probability than the probabilistic classical sequential search. Our results indicate that the critical polarization scales as ${N}^{\ensuremath{-}1/4}$, where $N$ is the database size and that for typical room temperature solution state NMR, the polarization is such that the ensemble implementation of Grover's algorithm would be advantageous for $N\ensuremath{\gtrsim}{10}^{22}$.

DOI
10.1103/physreva.77.052314

Related papers

Polarization requirements for ensemble implementations of quantum algorithms with a single-bit output

Brandon Anderson, David C. Collins

We compare the failure probabilities of ensemble implementations of quantum algorithms which use pseudopure initial states, quantified by their polarization, to those of competing classical probabilistic algorithms. Specifically we consider a class algorithms which require only one bit to output the solution to problems. For large ensemble sizes, we present a general scheme to determine a critical polarization beneath which the quantum algorithm fails with greater probability than its classical competitor. We apply this to the Deutsch-Jozsa algorithm and show that the critical polarization is 86.6%.

arXiv:quant-ph/0508061•Physical Review A•Oct 28, 2005•5 citations

Novel Strategy for Database Searching in Spin Liouville Space by NMR Ensemble Computing

Rafael Brüschweiler

Quantum computing by nuclear magnetic resonance using pseudopure spin states is bound by the maximal speed of quantum computing algorithms operating on pure states. In contrast to these quantum computing algorithms, a novel algorithm for searching an unsorted database is presented here that operates on truly mixed states in spin Liouville space. It provides an exponential speedup over Grover's quantum search algorithm with the sensitivity scaling exponentially with the number of spins, as for pseudopure state implementations. The minimal decoherence time required is exponentially shorter than that for Grover's algorithm.

Physical Review Letters•Nov 27, 2000•35 citations

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

Simanraj Sadana

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.

arXiv:2011.04051•Nov 8, 2020•1 citation

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

Coherence Fraction in Grover Search Algorithm

Si-Qi Zhou, Hai Jin, Jin-Min Liang +3 more

The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.

quant-pharXiv:2511.06835•Physical Review A•Nov 11, 2025•6 citations

Effects of a random noisy oracle on search algorithm complexity

Neil Shenvi, Kenneth R. Brown, K. Birgitta Whaley

Grover's algorithm provides a quadratic speed-up over classical algorithms for unstructured database or library searches. This paper examines the robustness of Grover's search algorithm to a random phase error in the oracle and analyzes the complexity of the search process as a function of the scaling of the oracle error with database or library size. Both the discrete- and continuous-time implementations of the search algorithm are investigated. It is shown that unless the oracle phase error scales as ${O(N}^{\ensuremath{-}1/4}),$ neither the discrete- nor the continuous-time implementation of Grover's algorithm is scalably robust to this error in the absence of error correction.

arXiv:quant-ph/0304138•Physical Review A•Nov 20, 2003•76 citations
We compare pseudopure state ensemble implementations, quantified by their initial polarization and ensemble size, of Grover's search algorithm to probabilistic classical sequential search algorithms in terms of their success and failure probabilities. We propose a criterion for quantifying the resources used by the ensemble implementation via the aggregate number of oracle invocations across the entire ensemble and use this as a basis for comparison with classical search algorithms. We determine bounds for a critical polarization such that the ensemble algorithm succeeds with a greater probability than the probabilistic classical sequential search. Our results indicate that the critical polarization scales as N\ensuremath−1/4{N}^{\ensuremath{-}1/4}N\ensuremath−1/4, where NNN is the database size and that for typical room temperature solution state NMR, the polarization is such that the ensemble implementation of Grover's algorithm would be advantageous for N\ensuremath≳1022N\ensuremath{\gtrsim}{10}^{22}N\ensuremath≳1022.
We compare the failure probabilities of ensemble implementations of quantum algorithms which use pseudopure initial states, quantified by their polarization, to those of competing classical probabilistic algorithms. Specifically we consider a class algorithms which require only one bit to output the solution to problems. For large ensemble sizes, we present a general scheme to determine a critical polarization beneath which the quantum algorithm fails with greater probability than its classical competitor. We apply this to the Deutsch-Jozsa algorithm and show that the critical polarization is 86.6%.
Quantum computing by nuclear magnetic resonance using pseudopure spin states is bound by the maximal speed of quantum computing algorithms operating on pure states. In contrast to these quantum computing algorithms, a novel algorithm for searching an unsorted database is presented here that operates on truly mixed states in spin Liouville space. It provides an exponential speedup over Grover's quantum search algorithm with the sensitivity scaling exponentially with the number of spins, as for pseudopure state implementations. The minimal decoherence time required is exponentially shorter than that for Grover's algorithm.
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.
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.
The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.
Grover's algorithm provides a quadratic speed-up over classical algorithms for unstructured database or library searches. This paper examines the robustness of Grover's search algorithm to a random phase error in the oracle and analyzes the complexity of the search process as a function of the scaling of the oracle error with database or library size. Both the discrete- and continuous-time implementations of the search algorithm are investigated. It is shown that unless the oracle phase error scales as ${O(N}^{\ensuremath{-}1/4}),$ neither the discrete- nor the continuous-time implementation of Grover's algorithm is scalably robust to this error in the absence of error correction.