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• 13 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

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•24 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•6 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•9 citations

The Deutsch-Jozsa algorithm and the bulk ensemble NMR quantum computer

Ryuichi Sawae, Y. Mori, Minaru Kawamura +2 more

In a bulk quantum computing it is shown by Collins that the iteration number of the Grover's algorithm will be decreased as compared with that number in case of a single quantum computer system. We discuss some of the implications on the Deutsch-Jozsa algorithm in a bulk quantum computing, and have a plan to prove them experimentally.

International Conference Physics and Control•Oct 4, 2006•1 citation

Scheme for implementing the Deutsch-Jozsa algorithm via atomic ensembles

Ping Dong, Zheng‐Yuan Xue, Ming Yang +1 more

We propose a physical scheme for implementing the Deutsch-Jozsa algorithm using atomic ensembles and optical devices. The scheme has inherent fault tolerance to the realistic noise and efficient scaling with the number of ensembles for some entangled states within the reach of current technology. It would be an important step toward more complex quantum computation via atomic ensembles.

arXiv:quant-ph/0510139•Oct 18, 2005•1 citation

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.
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 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.
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.