Where does Deutsch's algorithm use entanglement?

Question

I have read that to be useful, all quantum algorithms must use entanglement somewhere. However, reading several tutorials describing Deutsch's algorithm, I haven't seen any mention of how entanglement is used there.

Answer 1

TL;DR: No entanglement is created in the course of Deutsch's algorithm.

Generalization

Deutsch's algorithm is a special case of Deutsch-Jozsa algorithm with $n=1$ qubits in the query register. Generally speaking, in the study of algorithms one should account for the dependence of algorithm's properties on input size. Therefore, we will look at a slightly more general question whether entanglement appears in the course of Deutsch-Jozsa algorithm.

It turns out that there are indeed many circumstances, depending on $n$ and on the test function $f$, in which no entanglement is created. In particular, no entanglement is created when $n<3$. However, for $n\ge 3$ and for some balanced test functions $f$ entanglement does appear.

Background

Deutsch-Jozsa algorithm decides deterministically whether or not a given function $f: \{0,1\}^n\to\{0,1\}$ is constant or balanced$^1$, assuming that $f$ is indeed either constant or balanced$^2$. It uses $n$-qubit query register initialized to $|0\rangle^{\otimes n}$ and a one-qubit result register initialized to $|1\rangle$ and begins by applying Hadamard to each of the $n+1$ qubits, followed by the black box unitary $U_f$, defined by

$$ U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle,\tag1 $$

applied to all qubits, followed by Hadamards and measurement on the query register.

Entanglement is created and destroyed only by interactions, i.e. gates on more than one qubit. Therefore, the only step in the algorithm that may create entanglement is the application of $U_f$ after which the two registers are in the state

$$ |\psi\rangle = \left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}|x\rangle\right)\otimes\left(\frac{|0\rangle-|1\rangle}{\sqrt2}\right).\tag2 $$

Case $n=1$

The product form of $(2)$ indicates that the result register is never entangled with the query register. Therefore, if any entanglement is created it resides within the state of the query register

$$ |\phi\rangle = \frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}|x\rangle.\tag3 $$

In Deutsch's algorithm $n=1$ and since a qubit cannot be entangled with itself, we see that in this case no entanglement appears.

Case $n=2$

In fact, there are other cases where entanglement is absent from the algorithm. For any $n$, if $f$ is constant then $|\phi\rangle=|+\rangle^{\otimes n}$ and once again no entanglement is created. Further, even if $f$ is balanced but can be written as a degree one multivariate polynomial in the bits $x_0, \dots, x_{n-1}$ then $|\phi\rangle$ is $|\pm\rangle^{\otimes n}$, where $|-\rangle$ appears on $k$th qubit if $f$ depends on $x_k$, and once again no entanglement is created. In particular, since for $n=2$ all balanced functions can be written as degree one polynomial, no entanglement is created when $n=2$.

Case $n=3$

However, for $n=3$ there are balanced functions that make $|\phi\rangle$ entangled. For example, letting

$$ f(x) = x_0x_1+x_1x_2+x_2x_0\tag4 $$

and computing the state $\rho_0$ of the first qubit in the query register after tracing out the other qubits

$$ \begin{align} \mathrm{tr}_{12}|\phi\rangle\langle\phi|&=\frac18\mathrm{tr}_{12}\sum_{x,y\in\{0,1\}^3}(-1)^{f(x)+f(y)}|x\rangle\langle y|\\ &=\frac18\sum_{x_0,y_0\in\{0,1\}}\left(\sum_{a,b\in\{0,1\}}(-1)^{x_0a+ab+bx_0+y_0a+ab+by_0}\right)|x_0\rangle\langle y_0|\\ &=\frac18\sum_{x_0,y_0\in\{0,1\}}\left(\sum_{a,b\in\{0,1\}}(-1)^{a(x_0+y_0)+b(x_0+y_0)}\right)|x_0\rangle\langle y_0|\\ &=\frac18\begin{bmatrix}4&0\\0&4\end{bmatrix}\\ &=\frac{I}{2} \end{align}\tag5 $$

we see that the qubits in the query register are entangled.

We conclude that $n=3$ is the smallest size of the query register for which entanglement may be created in the course of Deutsch-Jozsa algorithm.

---

$^1$ Recall that $f$ is balanced if it is $0$ on half of the input bit strings and $1$ on the other half.

$^2$ Thus, the problem solved by the algorithm is an example of a promise problem.