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

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^{-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\gtrsim {10}^{22}$.

Figure 1

Critical polarization for (a) $N={10}^{10}$ and (b) $N={10}^{14}$. Open squares indicate sufficient polarization and solid dots indicate necessary polarization. Note the distinct horizontal and vertical scales. The rightmost point in each plot corresponds to $M=M_{\text{max}}$ for the relevant value of $N$. The critical polarization ${\epsilon }_c$, lies between the two curves.

Figure 2

Critical polarization for success probability of 0.90. Open squares indicate sufficient critical polarization and solid dots indicate necessary critical polarization. The straight lines are obtained by least-squares fits. Similar plots are obtained for other values of $p$, the primary difference being that the lines are shifted vertically.