## Tuesday, 10 September 2013

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