Let \(f: \{0,1\}\rightarrow \{0,1\}\) be some function encoded in a black-box which takes as input some \(x\in\{0,1\}\) and returns the value \(f(x)\in\{0,1\}\). There are only \(4\) different functions that can be defined in this case:
\[\begin{array}{r l l}
f_{00}:& 0 \mapsto 0,& 1\mapsto 0, \\
f_{11}:& 0 \mapsto 1,& 1\mapsto 1, \\
f_{01}:& 0 \mapsto 0,& 1\mapsto 1, \\
f_{10}:& 0 \mapsto 1,& 1\mapsto 0 .\end{array}\]
Notice that two of these functions, \(f_{00}\) and \(f_{11}\) are constant, where \(f(x)=c\) for some fixed \(c\in\{0,1\}\). The other two functions, \(f_{01}\) and \(f_{10}\), are balanced since \(f(x)=0\) for half of the possible inputs \(x\) and \(f(y)=1\) for the other half of remaining inputs \(y\).
The Deutsch problem, originally formulated and solved in \cite{deutsch}, and is the problem of determining whether or not some unknown function \(f: \{0,1\}\rightarrow \{0,1\}\) is constant or balanced by making queries to the function \(f\). Observe that the property of being constant or balanced can be determined by simply evaluating the sum \(f(0)\oplus f(1)\), since \(f(0)\oplus f(1)=0\) if and only if \(f\) is constant and \(f(0)\oplus f(1)=1\) if and only if \(f\) is balanced.
The Deutsch Problem
Input: A black-box that computes an unknown function \(f:\{0,1\}\rightarrow \{0,1\}\)
Problem: Determine whether or not the function is constant or balanced, or equivalently the value of \(f(0)\oplus f(1)\), by making queries to the black-box.
Trivially, making two queries to the black-box for the values of \(f(0)\) and \(f(1)\) is enough to completely determine the function $f$. The question then becomes whether or not the Deutsch problem can be solved by making only a single query. Classically, only a single query will never be enough to completely determine whether or not the function in constant or balanced, because provided with only a single value of say $f(0)$ the function may still be any two of the four possible functions described above. One of these possibilities is a constant function and the other is a balanced function so the Deutsch problem remains undetermined with only a single query in the classical case. The quantum algorithm described below shows that its possible to solve the Deutsch problem by making only a single query.
To represent the quantum black-box that encodes some unknown function \(f:\{0,1\}\rightarrow \{0,1\}\), define the following controlled gate acting on two qubits
\[\begin{array}{r l}
c-U_f: &\mathcal{H}^2\otimes\mathcal{H}^2\rightarrow \mathcal{H}^2\otimes \mathcal{H}^2, \\
& \left|x\right>\left|y\right>\mapsto \left|x\right>\left|y\oplus f(x)\right>.
\end{array}\]
Observe what happens when \(c-U_f\) acts on the state \(\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) in the two cases where \(\left|x\right>=\left|0\right>\) or \(\left|x\right>\left|1\right>\):
\[\begin{array}{r l}
c-U_f\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) & =c-U_f\big(\displaystyle\frac{\left|x\right>\left|0\right>}{\sqrt{2}}\big)-c-U_f\big(\displaystyle\frac{\left|x\right>\left|1\right>}{\sqrt{2}}\big) \\
& = \big(\displaystyle\frac{\left|x\right>\left|0\oplus f(x)\right>}{\sqrt{2}}\big)-\big(\displaystyle\frac{\left|x\right>\left|1\oplus f(x)\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(x)}\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).
\end{array}\]
This we can consider the control register as picking up the phase factor \((-1)^{f(x)}\) which depends on the value of \(f(x)\). Now consider the circuit shown in the figure below.
(A circuit solving the Deutsch problem by making a single query to the black-box \(c-U_f\). Applying a Hadamard gate to the first qubit in the state \[\left|\psi_0\right>=\left|0\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\] yields the state \(\left|\psi_1\right>\) which is an equally weighted superposition of two eigenstates of the \(c-U_f\) gate. After one query is made with \(c-U_f\) the first qubit in the state \(\left|\psi_2\right>\) has a relative phase factor that gets encoded into the state \(\left|\psi_3\right>\) after the Hadamard gate. The state then yields \(\left|\psi_4\right>=\left|f(0)\oplus f(1)\right>\) when measured which determins wether \(f\) is constant or balanced.)
The initial state of the input is \(\left|\psi_0\right>=\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) and after the Hadamard gate is applied to the first qubit it is put into an equally weighted superposition
\[\left|\psi_1\right>=(H\otimes I)\left|\psi_0\right>=H\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)=\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).\]
Then after making one query to the black-box by applying the $c-U_f$ gate to$ \left|\psi_1\right>$ gives
\[\begin{array}{r l}
\left|\psi_2\right>=c-U_f\left|\psi_1\right> &=c-U_f\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
&= c-U_f\big(\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) +c-U_f\big(\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)+(-1)^{f(1)}\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = \big(\displaystyle\frac{(-1)^{f(0)}\left|0\right>+(-1)^{f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),
\end{array}\]
where the factor \((-1)^{f(0)}\) has been factored out using \((-1)^{f(0)}(-1)^{f(1)}=(-1)^{f(0)\oplus f(1)}\). The first qubit in \(\left|\psi_2\right>\) now has a relative phase factor of \((-1)^{f(0)\oplus f(1)}\), which contains the value of \(f(0)\oplus f(1)\). Applying a second Hadamard gate to the first qubit effectively decodes the value of \(f(0)\oplus f(1)\) after measurement. To see this, consider the state of the first qubit in \(\left|\psi_3\right>$\)after the Hadamard gate is applied in the two cases where \(f(0)\oplus f(1)=0\) and \(f(0)\oplus f(1)=1\):
If \(f(0)\oplus f(1)=0\):
\[\begin{array}{r l}
\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),
\end{array}\]
If \(f(0)\oplus f(1)=1\):
\[\begin{array}{r l}
\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|1\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).
\end{array}\]
Note that the first qubit is in the state \(\left|0\right>\) if \(f(0)\oplus f(1)=0\) and is in the state \(\left|1\right>\) if \(f(0)\oplus f(1)=1\). Therefore, measuring the first qubit will return the state \(\left|\psi_4\right>=\left|0\right>\) with certainty if \(f\) is constant, and will instead return the state \(\left|\psi_4\right>=\left|1\right>\) with certainty if \(f\) is balanced.
The circuit constructed solves the Deutsch problem by making only one query to the black-box, whereas \(2\) queries were necessary in the classical query complexity. Despite being a somewhat contrived example, this is the first example presented in the black-box model that exploits the phase kick-back technique where a quantum algorithm can solve the problem by making fewer queries than needed in the classical case.
\[\begin{array}{r l l}
f_{00}:& 0 \mapsto 0,& 1\mapsto 0, \\
f_{11}:& 0 \mapsto 1,& 1\mapsto 1, \\
f_{01}:& 0 \mapsto 0,& 1\mapsto 1, \\
f_{10}:& 0 \mapsto 1,& 1\mapsto 0 .\end{array}\]
Notice that two of these functions, \(f_{00}\) and \(f_{11}\) are constant, where \(f(x)=c\) for some fixed \(c\in\{0,1\}\). The other two functions, \(f_{01}\) and \(f_{10}\), are balanced since \(f(x)=0\) for half of the possible inputs \(x\) and \(f(y)=1\) for the other half of remaining inputs \(y\).
The Deutsch problem, originally formulated and solved in \cite{deutsch}, and is the problem of determining whether or not some unknown function \(f: \{0,1\}\rightarrow \{0,1\}\) is constant or balanced by making queries to the function \(f\). Observe that the property of being constant or balanced can be determined by simply evaluating the sum \(f(0)\oplus f(1)\), since \(f(0)\oplus f(1)=0\) if and only if \(f\) is constant and \(f(0)\oplus f(1)=1\) if and only if \(f\) is balanced.
The Deutsch Problem
Input: A black-box that computes an unknown function \(f:\{0,1\}\rightarrow \{0,1\}\)
Problem: Determine whether or not the function is constant or balanced, or equivalently the value of \(f(0)\oplus f(1)\), by making queries to the black-box.
Trivially, making two queries to the black-box for the values of \(f(0)\) and \(f(1)\) is enough to completely determine the function $f$. The question then becomes whether or not the Deutsch problem can be solved by making only a single query. Classically, only a single query will never be enough to completely determine whether or not the function in constant or balanced, because provided with only a single value of say $f(0)$ the function may still be any two of the four possible functions described above. One of these possibilities is a constant function and the other is a balanced function so the Deutsch problem remains undetermined with only a single query in the classical case. The quantum algorithm described below shows that its possible to solve the Deutsch problem by making only a single query.
To represent the quantum black-box that encodes some unknown function \(f:\{0,1\}\rightarrow \{0,1\}\), define the following controlled gate acting on two qubits
\[\begin{array}{r l}
c-U_f: &\mathcal{H}^2\otimes\mathcal{H}^2\rightarrow \mathcal{H}^2\otimes \mathcal{H}^2, \\
& \left|x\right>\left|y\right>\mapsto \left|x\right>\left|y\oplus f(x)\right>.
\end{array}\]
Observe what happens when \(c-U_f\) acts on the state \(\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) in the two cases where \(\left|x\right>=\left|0\right>\) or \(\left|x\right>\left|1\right>\):
\[\begin{array}{r l}
c-U_f\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) & =c-U_f\big(\displaystyle\frac{\left|x\right>\left|0\right>}{\sqrt{2}}\big)-c-U_f\big(\displaystyle\frac{\left|x\right>\left|1\right>}{\sqrt{2}}\big) \\
& = \big(\displaystyle\frac{\left|x\right>\left|0\oplus f(x)\right>}{\sqrt{2}}\big)-\big(\displaystyle\frac{\left|x\right>\left|1\oplus f(x)\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(x)}\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).
\end{array}\]
This we can consider the control register as picking up the phase factor \((-1)^{f(x)}\) which depends on the value of \(f(x)\). Now consider the circuit shown in the figure below.
(A circuit solving the Deutsch problem by making a single query to the black-box \(c-U_f\). Applying a Hadamard gate to the first qubit in the state \[\left|\psi_0\right>=\left|0\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\] yields the state \(\left|\psi_1\right>\) which is an equally weighted superposition of two eigenstates of the \(c-U_f\) gate. After one query is made with \(c-U_f\) the first qubit in the state \(\left|\psi_2\right>\) has a relative phase factor that gets encoded into the state \(\left|\psi_3\right>\) after the Hadamard gate. The state then yields \(\left|\psi_4\right>=\left|f(0)\oplus f(1)\right>\) when measured which determins wether \(f\) is constant or balanced.)
The initial state of the input is \(\left|\psi_0\right>=\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) and after the Hadamard gate is applied to the first qubit it is put into an equally weighted superposition
\[\left|\psi_1\right>=(H\otimes I)\left|\psi_0\right>=H\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)=\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).\]
Then after making one query to the black-box by applying the $c-U_f$ gate to$ \left|\psi_1\right>$ gives
\[\begin{array}{r l}
\left|\psi_2\right>=c-U_f\left|\psi_1\right> &=c-U_f\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
&= c-U_f\big(\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) +c-U_f\big(\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)+(-1)^{f(1)}\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = \big(\displaystyle\frac{(-1)^{f(0)}\left|0\right>+(-1)^{f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),
\end{array}\]
where the factor \((-1)^{f(0)}\) has been factored out using \((-1)^{f(0)}(-1)^{f(1)}=(-1)^{f(0)\oplus f(1)}\). The first qubit in \(\left|\psi_2\right>\) now has a relative phase factor of \((-1)^{f(0)\oplus f(1)}\), which contains the value of \(f(0)\oplus f(1)\). Applying a second Hadamard gate to the first qubit effectively decodes the value of \(f(0)\oplus f(1)\) after measurement. To see this, consider the state of the first qubit in \(\left|\psi_3\right>$\)after the Hadamard gate is applied in the two cases where \(f(0)\oplus f(1)=0\) and \(f(0)\oplus f(1)=1\):
If \(f(0)\oplus f(1)=0\):
\[\begin{array}{r l}
\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),
\end{array}\]
If \(f(0)\oplus f(1)=1\):
\[\begin{array}{r l}
\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|1\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).
\end{array}\]
Note that the first qubit is in the state \(\left|0\right>\) if \(f(0)\oplus f(1)=0\) and is in the state \(\left|1\right>\) if \(f(0)\oplus f(1)=1\). Therefore, measuring the first qubit will return the state \(\left|\psi_4\right>=\left|0\right>\) with certainty if \(f\) is constant, and will instead return the state \(\left|\psi_4\right>=\left|1\right>\) with certainty if \(f\) is balanced.
The circuit constructed solves the Deutsch problem by making only one query to the black-box, whereas \(2\) queries were necessary in the classical query complexity. Despite being a somewhat contrived example, this is the first example presented in the black-box model that exploits the phase kick-back technique where a quantum algorithm can solve the problem by making fewer queries than needed in the classical case.