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}$.
Ensembles of quantum systems, such as liquid state NMR, have been proposed as possibilities for implementing quantum algorithms. For such implementations, projective measurement outcomes are replaced by expectation values. Although these are apparently deterministic, we point out that real implementations involve ensembles of nite size, giving probabilistic approximations to expectation values. The performance of such algorithms must be compared to their classical probabilistic counterparts. We discuss proposed scalable ensemble versions of the Deutsch-Jozsa algorithm in this context and show that their performance is worse than the classical probabilistic algorithm. Appears in Phys. Rev. A 68, 052301 (2003) \\Standard " Quantum Computing Implementations on a single quantum system amenable to projective measurements. L-qubit quantum system Pure state preparation Apply algorithm unitary Projective measurement on L0 qubit subsystem Classical computation j ii f : = Ûalg j ii x 2 f0; : : : ; 2L 0 1g with probability xj f 2 Possible solution I For useful algorithms the probability of returning x corresponding to trivial or incorrect solutions is small. I Typically a decomposition Ûalg = Ûm: : : Û1 into simple unitary operations facilitates algorithm implementation. 1 Expectation Value Quantum Computing Implementations using an ensemble of identical, non-interacting quantum systems. Ensemble of L-qubit quantum systems Mixed state preparation Apply algorithm unitary Expectation value (EV) measurements on L0 qubit subsystem
We analytically investigate the robustness of the Bernstein-Vazirani and Deutsch-Jozsa algorithms against single-qubit Pauli noise, of which bit-flip, phase-flip, and depolarizing noise are special cases, using the density-matrix formalism. For a general Pauli channel acting on each qubit after every gate, we derive exact closed-form expressions for the success probability of a single run as a function of the error probabilities and the number of qubits
n, and validate them against Qiskit simulations. The noise enters only through the probability
ε with which each output bit is flipped. Under bit-flip noise with error probability
p>1/2 the most probable outcome of the Bernstein-Vazirani algorithm is the complement of the correct one, which classical post-processing corrects, whereas depolarizing and phase-flip noise never bias the output toward a wrong outcome. For the Deutsch-Jozsa algorithm, the success probability is the average over constant and balanced oracles, and the results are given for the single-variable balanced oracle, which is shown to be the least robust of all balanced oracles for
ε<1/2. For a single run, the tolerable error probability of both algorithms decreases as
1/n. We then determine the minimum number of repetitions required for a given confidence and compare it with the number of queries of the classical algorithms. The threshold error probability below which the noisy Bernstein-Vazirani algorithm retains its query advantage increases with
n, whereas that of the Deutsch-Jozsa algorithm with its standard readout decreases as
1/n. This contrast indicates that algorithms whose answer is encoded in many independently decodable output bits are considerably more robust to noise than algorithms whose verdict depends on a single global outcome.
We discuss the ensemble version of the Deutsch-Jozsa (DJ) algorithm which attempts to provide a ``scalable'' implementation on an expectation-value NMR quantum computer. We show that this ensemble implementation of the DJ algorithm is at best as efficient as the classical random algorithm. As soon as any attempt is made to classify all possible functions with certainty, the implementation requires an exponentially large number of molecules. The discrepancies arise out of the interpretation of mixed state density matrices.
A general framework for regarding oracle-assisted quantum algorithms as tools for discriminating among unitary transformations is described. This framework is applied to the Deutsch-Jozsa problem and all possible quantum algorithms which solve the problem with certainty using oracle unitaries in a particular form are derived. It is also used to show that any quantum algorithm that solves the Deutsch-Jozsa problem starting with a quantum system in a particular class of initial, thermal equilibrium-based states of the type encountered in solution-state NMR can only succeed with greater probability than a classical algorithm when the problem size
n exceeds
105.That superpositions of states can be useful for performing tasks in quantum systems has been known since the early days of quantum information, but only recently has a quantitative theory of quantum coherence been proposed. Here we apply that theory to an analysis of the Deutsch-Jozsa algorithm, which depends on quantum coherence for its operation. The Deutsch-Jozsa algorithm solves a decision problem, and we focus on a probabilistic version of that problem, comparing probability of being correct for both classical and quantum procedures. In addition, we study a related decision problem in which the quantum procedure has one-sided error while the classical procedure has two-sided error. The role of coherence on the quantum success probabilities in both of these problems is examined.