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

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^(-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 > 10^22

References in corpus (25)

• Quantum Mechanics helps in searching for a needle in a haystack
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum Computing
• NMR Techniques for Quantum Control and Computation
• On the Power of One Bit of Quantum Information
• Grover's quantum searching algorithm is optimal
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing
• An all silicon quantum computer
• Effective Pure States for Bulk Quantum Computation
• Benchmarking quantum control methods on a 12-qubit system
• Algorithmic Cooling and Scalable NMR Quantum Computers
• Sympathetic cooling of ${}^{9}B{e}^{+}$ and ${}^{24}M{g}^{+}$ for quantum logic
• Experimental implementation of heat-bath algorithmic cooling using solid-state nuclear magnetic resonance
• Implementation of a three-quantum-bit search algorithm
• Preparing high purity initial states for nuclear magnetic resonance quantum computing
• NMR Quantum Computation: a Critical Evaluation
• Liquid state NMR simulations of quantum many-body problems
• A solid-state NMR three-qubit homonuclear system for quantum information processing: control and characterization
• Ensemble Quantum Computation with atoms in periodic potentials
• Implementing Grover's Quantum Search on a Para-Hydrogen based Pure State NMR Quantum Computer
• Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm
• Modified Grover's algorithm for an expectation value quantum computer
• Polarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output
• Creation of entanglement in a scalable spin quantum computer with long-range dipole-dipole interaction between qubits