Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm

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.

Minor changes, reference added, replaced with publised version

References in corpus (1)

• Algorithmic Cooling and Scalable NMR Quantum Computers

Cited by in corpus (8)

• Parallel Quantum Computing in a Single Ensemble Quantum Computer
• Determining the parity of a permutation using an experimental NMR qutrit
• Strategy for quantum algorithm design assisted by machine learning
• Thermal Equilibrium as an Initial State for Quantum Computation by NMR
• Partitioned trace distances
• Programmable quantum state discriminator by Nuclear Magnetic Resonance
• Polarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output
• Statistical comparison of ensemble implementations of Grover's search algorithm to classical sequential searches