Discrimination of unitary transformations in the Deutsch-Jozsa algorithm

Abstract

We describe a general framework for regarding oracle-assisted quantum algorithms as tools for discriminating between unitary transformations. We apply this to the Deutsch-Jozsa problem and derive all possible quantum algorithms which solve the problem with certainty using oracle unitaries in a particular form. We also use this 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 exceeds $n\sim 10^5.$

arXiv comment7 pages, 1 figure

References in corpus (24)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Mechanics helps in searching for a needle in a haystack
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum Algorithms Revisited
• NMR Techniques for Quantum Control and Computation
• Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing
• Statistical distinguishability between unitary operations
• Using entanglement improves precision of quantum measurements
• An all silicon quantum computer
• Benchmarking quantum control methods on a 12-qubit system
• Algorithmic Cooling and Scalable NMR Quantum Computers
• Optimal discrimination of quantum operations
• Sympathetic cooling of ${}^{9}B{e}^{+}$ and ${}^{24}M{g}^{+}$ for quantum logic
• Quantum information and precision measurement
• Deutsch-Jozsa algorithm as a test of quantum computation
• Implementation of a three-quantum-bit search algorithm
• Liquid state NMR simulations of quantum many-body problems
• Minimum-error discrimination between mixed quantum states
• Ensemble Quantum Computation with atoms in periodic potentials
• Unambiguous discrimination among oracle operators
• Thermal Equilibrium as an Initial State for Quantum Computation by NMR
• Quantum-state filtering applied to the discrimination of Boolean functions
• Polarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output
• Creation of entanglement in a scalable spin quantum computer with long-range dipole-dipole interaction between qubits

Cited by in corpus (4)

• Determining the parity of a permutation using an experimental NMR qutrit
• Highly Efficient Processing Multi-photon States
• Tradeoff between energy and error in the discrimination of quantum-optical devices
• Multiple multi-control unitary operations: implementation and applications