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
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 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.
Quantum algorithms are conventionally formulated for implementation on a single system of qubits amenable to projective measurements. However, in expectation value quantum computation, such as nuclear magnetic resonance realizations, the computer consists of an ensemble of identical qubit-systems amenable only to expectation value measurements. The prevalent strategy in such expectation value implementations of quantum algorithms has been to retain the conventional formulation's unitary operations but modify its initialization and measurement steps appropriately. This naive approach is not optimal for Grover's algorithm and a shortened version for expectation value quantum computers is presented.
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.
In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor's factorization algorithm, Grover's search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and σ(z)(¼) as these operations cannot be implemented "bitwise", and their standard fault-tolerant implementations require measurement.
Experimental characterizations of a quantum system involve the measurement of expectation values of observables for a preparable state $\ensuremath{\mid}\ensuremath{\psi}⟩$ of the quantum system. Such expectation values can be measured by repeatedly preparing $\ensuremath{\mid}\ensuremath{\psi}⟩$ and coupling the system to an apparatus. For this method, the precision of the measured value scales as N1 for N repetitions of the experiment. For the problem of estimating the parameter $\ensuremath{\phi}$ in an evolution ${e}^{\ensuremath{-}i\ensuremath{\phi}H}$, it is possible to achieve precision N1 [the quantum metrology limit; see Giovannetti et al., Phys. Rev. Lett. 96, 010401 (2006)] provided that sufficient information about H and its spectrum is available. We consider the more general problem of estimating expectations of operators A with minimal prior knowledge of A. We give explicit algorithms that approach precision N1 given a bound on the eigenvalues of A or on their tail distribution. These algorithms are particularly useful for simulating quantum systems on quantum computers because they enable efficient measurement of observables and correlation functions. Our algorithms are based on a method for efficiently measuring the complex overlap of $\ensuremath{\mid}\ensuremath{\psi}⟩$ and $U\ensuremath{\mid}\ensuremath{\psi}⟩$, where U is an implementable unitary operator. We explicitly consider the issue of confidence levels in measuring observables and overlaps and show that, as expected, confidence levels can be improved exponentially with linear overhead. We further show that the algorithms given here can typically be parallelized with minimal increase in resource usage.
The translation of Grover's search algorithm from its standard version, designed for implementation on a single quantum system amenable to projective measurements, into one suitable for an ensemble of quantum computers, whose outputs are expectation values of observables on individual qubits, is described in detail. A filtering scheme, which effectively determines expectation values on a limited portion of the quantum state, is presented and used to locate a single item for searches involving more than one marked item. A truncated version of Grover's algorithm, requiring fewer steps than the translated standard version but locating marked items just as successfully, is proposed. For quantum computational devices that only return expectation values, the truncated version is superior to its standard counterpart. This indicates that it is possible to modify quantum algorithms so as to reduce the required temporal resources by using the ensemble's spatial resources.