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.
We propose a scalable method on the basis of nth-order coupling operators to construct f-dependent phase transformations in the n-qubit modified Deutsch-Jozsa (D-J) quantum algorithm. The novel n-qubit entangling transformations are easily implemented via J-couplings between neighboring spins. The seven-qubit modified D-J quantum algorithm and seventh-order coupling transformations are then experimentally demonstrated with liquid state nuclear magnetic resonance (NMR) techniques. The method may offer the possibility of creating generally entangled states of n qubits and simulating n-body interactions on n-qubit NMR quantum computers.
A detailed description of the development of a three qubit NMR realization of the Deutsch-Jozsa algorithm [Collins et.al., Phys. Rev. A 62, 022304 (2000)] is provided. The theoretical and experimental techniques used for the reduction of the algorithm's evolution steps into a sequence of NMR pulses are discussed at length. This includes the description of general pulse sequence compilation techniques, various schemes for indirectly coupled gate realizations, experimental pulse parameterization techniques and bookkeeping methods for pulse phases.
The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as
DJn0(x)=1 for
∣x∣=n/2,DJn0(x)=0 for
∣x∣=0,n, and it is undefined for the rest of the cases, where
n is even, and
∣x∣ is the Hamming weight of
x. The optimal quantum algorithm needs only one query to compute
DJn0 but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as
DJnk(x)=1 for
∣x∣=n/2,DJnk(x)=0 for
∣x∣ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity
k+1 for computing the generalized Deutsch-Jozsa problem
DJnk. It is clear that the case of
k=0 is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.