Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0307153 · Physical Review A

Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm

Arvind, David C. Collins

Published Nov 3, 2003• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.68.052301

Related papers

Scaling Issues in Ensemble Quantum Algorithms

David C. Collins

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

•Feb 9, 2015•0 citations

Discrimination of unitary transformations in the Deutsch-Jozsa algorithm: Implications for thermal-equilibrium-ensemble implementations

David C. Collins

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 $~{10}^{5}.$

arXiv:1002.4227•Physical Review A•May 19, 2010•5 citations

Thermal equilibrium as an initial state for quantum computation by NMR

Amr F. Fahmy, Raimund Marx, Wolfgang Bermel +1 more

An experimental implementation of an ensemble quantum algorithm is presented in which the thermal state is used as an initial state of the algorithm. More specifically, we use four active qubits to demonstrate the solution of the Deutsch-Jozsa problem using a nuclear magnetic resonance quantum computer. For the implemented algorithm the number of molecules in the NMR sample is irrelevant to the number of qubits available to an NMR quantum computer, and the initial state is chosen to be the state of thermal equilibrium, thereby avoiding the preparation of pseudopure states and the resulting exponential loss of signal as the number of qubits increases. As expected, measured spectra demonstrate a clear distinction between constant and balanced functions.

arXiv:0705.1676•Physical Review A•Aug 12, 2008•23 citations

Quantum entanglement in the NMR implementation of the Deutsch-Jozsa algorithm

Arvind, *, Kavita Dorai, Anil Kumar

A scheme to execute an \\eta-bit Deutsch-Jozsa (DJ) algorithm using \\eta qubits has been implemented for up to three qubits on an NMR quantum computer. For the one- and the two-bit Deutsch problem, the qubits do not get entangled, and the NMR implementation is achieved without using spin-spin interactions. It is for the three-bit case, that the manipulation of entangled states becomes essential. The interactions through scalar J-couplings in NMR spin systems have been exploited to implement entangling transformations required for the three bit DJ algorithm.

•May 1, 2001•13 citations

Solution of the Deutsch-Josza Problem by NMR Ensemble Computing without Sensitivity Scaling

Frank Matthew Woodward, Rafael Brüschweiler

Experimental NMR implementations of the Deutsch-Josza quantum algorithm based on pesudo-pure spin states exhibit an exponential sensitivity scaling with the number of qubits. By employing truly mixed spin states in spin Liouville space, where molecules with different nuclear spin configurations represent different input states, the Deutsch-Josza problem can be solved by single function evaluation without sensitivity loss concomitant with increase of the number of bits.

arXiv:quant-ph/0006024•Jun 6, 2000•6 citations

Implementing the Deutsch-Jozsa algorithm with macroscopic ensembles

Henry Semenenko, Tim Byrnes

Quantum computing implementations under consideration today typically deal with systems with microscopic degrees of freedom such as photons, ions, cold atoms, and superconducting circuits. The quantum information is stored typically in low-dimensional Hilbert spaces such as qubits, as quantum effects are strongest in such systems. It has, however, been demonstrated that quantum effects can be observed in mesoscopic and macroscopic systems, such as nanomechanical systems and gas ensembles. While few-qubit quantum information demonstrations have been performed with such macroscopic systems, a quantum algorithm showing exponential speedup over classical algorithms is yet to be shown. Here, we show that the Deutsch-Jozsa algorithm can be implemented with macroscopic ensembles. The encoding that we use avoids the detrimental effects of decoherence that normally plagues macroscopic implementations. We discuss two mapping procedures which can be chosen depending upon the constraints of the oracle and the experiment. Both methods have an exponential speedup over the classical case, and only require control of the ensembles at the level of the total spin of the ensembles. It is shown that both approaches reproduce the qubit Deutsch-Jozsa algorithm, and are robust under decoherence.

arXiv:1604.08688•Physical Review A•May 2, 2016•8 citations
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.
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
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 nnn exceeds  105.~{10}^{5}. 105.
An experimental implementation of an ensemble quantum algorithm is presented in which the thermal state is used as an initial state of the algorithm. More specifically, we use four active qubits to demonstrate the solution of the Deutsch-Jozsa problem using a nuclear magnetic resonance quantum computer. For the implemented algorithm the number of molecules in the NMR sample is irrelevant to the number of qubits available to an NMR quantum computer, and the initial state is chosen to be the state of thermal equilibrium, thereby avoiding the preparation of pseudopure states and the resulting exponential loss of signal as the number of qubits increases. As expected, measured spectra demonstrate a clear distinction between constant and balanced functions.
A scheme to execute an \\eta-bit Deutsch-Jozsa (DJ) algorithm using \\eta qubits has been implemented for up to three qubits on an NMR quantum computer. For the one- and the two-bit Deutsch problem, the qubits do not get entangled, and the NMR implementation is achieved without using spin-spin interactions. It is for the three-bit case, that the manipulation of entangled states becomes essential. The interactions through scalar J-couplings in NMR spin systems have been exploited to implement entangling transformations required for the three bit DJ algorithm.
Quantum computing implementations under consideration today typically deal with systems with microscopic degrees of freedom such as photons, ions, cold atoms, and superconducting circuits. The quantum information is stored typically in low-dimensional Hilbert spaces such as qubits, as quantum effects are strongest in such systems. It has, however, been demonstrated that quantum effects can be observed in mesoscopic and macroscopic systems, such as nanomechanical systems and gas ensembles. While few-qubit quantum information demonstrations have been performed with such macroscopic systems, a quantum algorithm showing exponential speedup over classical algorithms is yet to be shown. Here, we show that the Deutsch-Jozsa algorithm can be implemented with macroscopic ensembles. The encoding that we use avoids the detrimental effects of decoherence that normally plagues macroscopic implementations. We discuss two mapping procedures which can be chosen depending upon the constraints of the oracle and the experiment. Both methods have an exponential speedup over the classical case, and only require control of the ensembles at the level of the total spin of the ensembles. It is shown that both approaches reproduce the qubit Deutsch-Jozsa algorithm, and are robust under decoherence.