# Where does Deutsch's algorithm use entanglement?

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.

• I think this is because no entanglement is being generated in the entirety of the Duetsch's algorithm. Dec 17, 2021 at 21:28
• Where have you read this? Dec 29, 2021 at 15:54
• I don't remember exactly, but for example quantumcomputing.stackexchange.com/questions/2674/… Dec 29, 2021 at 17:22

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.

• nice answer. I wonder whether this is the right question to ask though. After all, even if the individual gates used in a gate decomposition of the algorithm never result in an entangled state, that doesn't mean that entanglement is not necessary to make the algorithm possible. The individual gates might only be implementable exploiting entanglement at some stage in the dynamics. Case in point, here $U_f$ does not generate entanglement, but can it be implemented with a dynamics that is such that the instantaneous states are never entangled?
– glS
Dec 18, 2021 at 19:16
• @gIS Yes, the black box $U_f$ might create and destroy entanglement internally without producing an entangled output. I thought whether this happens is an interesting question, but far from the original post (especially since I already generalized a little bit). Dec 18, 2021 at 21:03
• Moreover, in all cases above where $U_f$ doesn't produce entanglement ($f$ constant and $f$ degree one polynomial which subsumes $n=1$ and $n=2$), $U_f$ may be implemented as tensor product of identity and Pauli $Z$ gates! So at least in those cases it's possible to implement the full algorithm including the black box for suitable $f$ completely entanglement-free in many common gatesets. This is mostly a consequence of the fact that Deutsch-Jozsa algorithm only restricts the behavior of the black box on a single input $|+\rangle^{\otimes n}|-\rangle$. Dec 18, 2021 at 21:07