Scaling Issues in Ensemble Quantum Algorithms

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 subsyste