## Tuesday, 10 September 2013

### The Deutsch Problem and Algorithm

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.