The Deutsch-Jozca Algorithm

The Deutsch problem concerned itself with a function \(f:\{0,1\}\rightarrow \{0,1\}\) defined on a single bit. Instead, consider the function \(f:\{0,1\}^n\rightarrow \{0,1\}\) defined on bitstrings of length \(n\). Moreover, suppose this function is either constant if \(f(\mathbf{x})=c\) for all \(\mathbf{x}\in\{0,1\}^n\) and a fixed \(c\in\{0,1\}\), or balanced if \(f(\mathbf{x})=0\) for precisely half of the bitstrings \(\mathbf{x}\in\{0,1\}^n\) and \(f(\mathbf{x})=1\) for the remaining half of the bitstrings \(\mathbf{x}\in\{0,1\}^n\). This time, the problem of determining whether or not \(f\) is constant or balanced is tricker. In the classical context, suppose \(2^{n-1}\) queries are made to \(f\) for half of the possible bitstrings, and each of these queries returned the value \(0\). Then without making at least one more query to \(f\) it is impossible to determine with certainty whether or not \(f\) is constant or balanced since this next query could return a value of either \(0\) or \(1\). Thus, in the worst case \(2^{n-1}+1\) queries would be necessary to determine if \(f\) is constant or balanced. In the quantum case, the Deutsch-Jozsa algorithm, originally presented in \cite{jozsa}, is able to determine with certainty whether or not \(f\) is constant or balanced by making only a single query.

The Deutsch-Jozsa Problem

Input: A black-box that computes an unknown function \(f:\{0,1\}^n\rightarrow \{0,1\}\) which is guaranteed to be either constant or balanced.

Problem:  Determine wether or not the function is constant or balanced by making queries to the black-box.


Define a black-box encoding a function \(f:\{0,1\}^n\rightarrow \{0,1\}\) as the following controlled gate that acts on a \(n\) qubit control register and single qubit target register
\[\begin{array}{r l}
c-U_f: &\mathcal{H}^{2^n}\otimes\mathcal{H}^2\rightarrow \mathcal{H}^{2^n}\otimes \mathcal{H}^2, \\
& \left|\mathbf{x}\right>\left|y\right>\mapsto \left|\mathbf{x}\right>\left|y\oplus f(\mathbf{x})\right>.
\end{array}\]
Consider the circuit displayed in the figure below which takes as input the state \(\left|\psi_0\right>=\left|\mathbf{0}\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}} \big)\), where the first register represents the \(n\) qubit control and the second register represents the single qubit target. Notice that the overall action of this circuit is a generalization of the circuit for the Deutsch algorithm, where now the control register consists of \(n\) qubits instead of just one.

 
(A circuit solving the Deutsch-Jozsa problem by making a single query to the black-box \(c-U_f\). Applying Hadamard gates to the first \(n\) qubitis in the control register of the state 
\[\left|\psi_0\right>=\left|\mathbf{0}\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\] yields the state \(\left|\psi_2\right>\) which is in some superposition of  eigenstates of the \(c-U_f\) gate. Applying the second set of Hadamard gates ensures that state \[\left|\psi_4\right>=\left|\mathbf{0}\right>\] will only be observed upon measurement of the control register of \(\left|\psi_3\right>\) if the function \(f\) is constant. Otherwise some basis state \(\left|\psi_4\right>
\neq\left|\mathbf{0}\right>\) will be observed after measurement if the function \(f\) is balanced.)



After the Hadamard gate is applied to each qubit in the control the state becomes
\[\left|\psi_1\right>=(H^{\otimes n}\otimes I)\left|\psi_0\right>=H^{\otimes n}\left|\mathbf{0}\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)= \big(\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).\]
Then applying the \(c-U_f\) gate to \(\left|\psi_1\right>\) gives
\[\left|\psi_2\right>=(c-U_f)\left|\psi_1\right>= \big(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}\left|\mathbf{x}\right>\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),\]
and after the second set of Hadamard gates is applied to the control register the state becomes
\[\begin{array}{r l}
\left|\psi_3\right>=(H^{\otimes n}\otimes I)\left|\psi_2\right> &= \big(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}\big(\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>\big)\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
&= \big(\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}\big(
\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})+\mathbf{x}\cdot\mathbf{z}}\big)\left|\mathbf{z}\right>
\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)
\end{array}.\]
Let \(\left|\psi_4\right>\) represent the state of the control register after a measurement is performed on the control register of \(\left|\psi_3\right>\). In order analyze what state will be observed when the control register of \(\left|\psi_3\right>\) is measured, consider the amplitude \(\alpha_0\)  of the state \(\left|\mathbf{z}\right>=\left|\mathbf{0}\right>\) in the control register of \(\left|\psi_3\right>\):
\[\alpha_0= \displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})+\mathbf{x}\cdot\mathbf{0}}=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}.\]
Suppose the function \(f\) is constant. Then there are two cases with either \(f(\mathbf{x})=0\) for all \(\mathbf{x}\in\{0,1\}^n\) or \(f(\mathbf{x})=1\) for all \(\mathbf{x}\in\{0,1\}^n\), but either way
\[\alpha_0=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\pm 1=\displaystyle\frac{\pm2^n}{2^n}=\pm 1.\]
Therefore the state of the control register after the measurement will be in the state \(\left|\psi_4\right>=\left|\mathbf{0}\right>\) with certainty, implying that the function \(f\) is constant.

On the other hand suppose instead that the function \(f\) is balanced so that \(f(\mathbf{x})=0\) for exactly half of the states \(\left|\mathbf{x}\right>\) for \(\mathbf{x}\in\{0,1\}^n\) and \(f(\mathbf{x})=1\) for the remaining half. It then follows that
\[\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=0,\]
since exactly half of the contributing terms in the sum will be \(1\) while the other half will be \(-1\) so that the total sums to \(0\). Now recall the amplitude \(\alpha_0\) of the state \(\left|\mathbf{z}\right>=\left|0\right>\) in the control register of \(\left|\psi_3\right>\) in this case:
\[\alpha_0=\displaystyle \frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=0\].
This implies that there is zero probability in observing the state \(\left|0\right>\) when a measurement is performed on the control register of \(\left|\psi_3\right>\). Instead, some computational basis state \( \left|\psi_4\right>=\left|\mathbf{z}\right>\) with \(\mathbf{z}\in\{0,1\}^n\) such that \(\mathbf{z}\neq\mathbf{0}\) will be observed with nonzero probability.

The Deutsch-Jozsa algorithm shows that its possible to determine in a single query whether or not some function \(f:\{0,1\}^n\rightarrow \{0,1\}\) is constant or balanced provided that the function \(f\) is guaranteed to have one of these two properties. It was previously argued that the deterministic classical algorithm for solving the related problem must make at least \(2^{n-1}+1\) queries in the worst case to establish with certainty wether or not the function \(f\) is constant or balanced. Hence, the Deutsch-Jozsa algorithm gives an exponential speed up in the query complexity of the problem when compared to its deterministic classical analog.

However, it is worth mentioning that a probabilistic classical algorithm can actually solve the problem making only \(2\) queries to some black-box  if allowed to error with a probability at most \(p= \frac{1}{3}\). To decrease this probability of error to \(p<\frac{1}{2^n}\) only \(n+1\) queries need to be made. Therefore, when comparing the query complexity of the problem in the quantum case to the probabilistic classical case, the Deutsch-Jozsa algorithm only solves the problem by making one less query if the classical algorithm is allowed a constant probability of error, but the classical algorithm must make \(O(n)\) queries if exponentially small error probabilities are desired.