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:1002.4227 · Physical Review A

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

David C. Collins

Published May 19, 2010• 5 citations
arXivHTMLPDF

Abstract

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

DOI
10.1103/physreva.81.052323

Related papers

Discrimination of Unitary Transformations and Quantum Algorithms

David C. Collins, Alexander I. Lvovsky

Quantum algorithms are typically understood in terms of the evolution of a multi-qubit quantum system under a prescribed sequence of unitary transformations. The input to the algorithm prescribes some of the unitary transformations in the sequence with others remaining fixed. For oracle query algorithms, the input determines the oracle unitary transformation. Such algorithms can be regarded as devices for discriminating amongst a set of unitary transformations. The question arises: "Given a set of known oracle unitary transformations, to what extent is it possible to discriminate amongst them?" We investigate this for the Deutsch-Jozsa problem. The task of discriminating amongst the admissible oracle unitary transformations results in an exhaustive collection of algorithms which can solve the problem with certainty.

arXiv:0811.1359•AIP conference proceedings•Jan 1, 2009•0 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

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

Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm

Arvind, David C. Collins

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.

arXiv:quant-ph/0307153•Physical Review A•Nov 3, 2003•12 citations

Phase-creation algorithm to solve and extended Deutsch problem with an implementation on an NMR quantum computer (Analytical Study of Quantum Information and Related Fields)

Hiroshi Ozawa

The Deutsch-Jozsa algorithm to implement an $f$ -controUed-NOT transformation on a quantum computer was generalized to create arbitrary phases.This phase-creation algorithm was applied to solve an extended Deutsch problem for afunction that maps $\{0, 1\}^{n}$ to $\{0, 1\}^{m}$ .Implementation of the algorithm on an NMR quantum computer is discussed.

数理解析研究所講究録•May 1, 2002•0 citations

The continuous-variable Deutsch–Jozsa algorithm using realistic quantum systems

Rob C. Wagner, Viv M. Kendon

This paper is a study of the continuous-variable Deutsch–Jozsa algorithm. First, we review an existing version of the algorithm for qunat states (Pati and Braunstein 2002 arXiv:0207108v1), and then, we present a realistic version of the Deutsch–Jozsa algorithm for continuous variables, which can be implemented in a physical quantum system given the appropriate oracle. Under these conditions, we have a probabilistic algorithm for deciding the function with a very high success rate with a single call to the oracle. Finally, we look at the effects of errors in both of these continuous-variable algorithms and how they affect the chances of success. We find that the algorithm is generally robust for errors in initialization and the oracle, but less so for errors in the measurement apparatus and the Fourier transform. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to 'Coherent states: mathematical and physical aspects'.

Journal of Physics A Mathematical and Theoretical•May 30, 2012•4 citations
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 algorithms are typically understood in terms of the evolution of a multi-qubit quantum system under a prescribed sequence of unitary transformations. The input to the algorithm prescribes some of the unitary transformations in the sequence with others remaining fixed. For oracle query algorithms, the input determines the oracle unitary transformation. Such algorithms can be regarded as devices for discriminating amongst a set of unitary transformations. The question arises: "Given a set of known oracle unitary transformations, to what extent is it possible to discriminate amongst them?" We investigate this for the Deutsch-Jozsa problem. The task of discriminating amongst the admissible oracle unitary transformations results in an exhaustive collection of algorithms which can solve the problem with certainty.
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.
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.
The Deutsch-Jozsa algorithm to implement an fff -controUed-NOT transformation on a quantum computer was generalized to create arbitrary phases.This phase-creation algorithm was applied to solve an extended Deutsch problem for afunction that maps {0,1}n\{0, 1\}^{n}{0,1}n to {0,1}m\{0, 1\}^{m}{0,1}m .Implementation of the algorithm on an NMR quantum computer is discussed.
This paper is a study of the continuous-variable Deutsch–Jozsa algorithm. First, we review an existing version of the algorithm for qunat states (Pati and Braunstein 2002 arXiv:0207108v1), and then, we present a realistic version of the Deutsch–Jozsa algorithm for continuous variables, which can be implemented in a physical quantum system given the appropriate oracle. Under these conditions, we have a probabilistic algorithm for deciding the function with a very high success rate with a single call to the oracle. Finally, we look at the effects of errors in both of these continuous-variable algorithms and how they affect the chances of success. We find that the algorithm is generally robust for errors in initialization and the oracle, but less so for errors in the measurement apparatus and the Fourier transform. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to 'Coherent states: mathematical and physical aspects'.