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

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

Figure 1

General structure for oracle-based quantum algorithm where the oracle output is a single bit. The oracle is invoked $M$ times. The initial and final unitaries ${\mathrm{V̂}}_0$ and ${\mathrm{V̂}}_M$ are not generally necessary but will enable initialization and measurement in the computational basis.