Is $|x,y,z\oplus f(x,y)\rangle$ entangled?

Let $$f(x,y)$$ be a random 2n- to 1-bit function.

Consider the quantum circuit $$|x,y,z\rangle \to |x,y,z\oplus f(x,y)\rangle$$.

Is the new state entangled in general?

Is it entangled if $$x,y$$ are $$H^{\bigotimes n}|0\rangle$$ ?

• You still haven't specified what $z$ is. Apr 30 '19 at 8:19

If applied on $$H^{\otimes n}|0\rangle$$ then the result will be entangled if $$f$$ is not constant also in the simpler situation.

Suppose $$x,y$$ are $$n$$-bit strings, $$\forall x,y:~ U|x,y\rangle = |x, y \oplus f(x) \rangle$$ and $$|\phi\rangle = U \cdot H^{\otimes n}|0\rangle\otimes|y\rangle$$ for some bit string $$y$$. Let's calculate $$|\phi\rangle\langle\phi|$$. $$|\phi\rangle\langle\phi| = U \cdot \frac{1}{2^{n-1}}\sum_{i=0}^{2^n-1}|i\rangle\otimes|y\rangle \cdot \frac{1}{2^{n-1}}\sum_{j=0}^{2^n-1}\langle j|\otimes\langle y| \cdot U^\dagger =$$ $$= \frac{1}{2^{n}} \sum_{i=0}^{2^n-1}|i\rangle\otimes|y\oplus f(i)\rangle \cdot \sum_{j=0}^{2^n-1}\langle j|\otimes\langle y \oplus f(j)| =$$ $$= \frac{1}{2^{n}} \sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}|i\rangle\langle j|\otimes|y\oplus f(i)\rangle\langle y \oplus f(j)|$$ Now we can calculate partial trace of $$|\phi\rangle\langle\phi|$$ over the first subsystem $$\text{tr}_1\left(|\phi\rangle\langle\phi|\right) = \text{tr}_1\left(\frac{1}{2^{n}} \sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}|i\rangle\langle j|\otimes|y\oplus f(i)\rangle\langle y \oplus f(j)|\right) =$$ $$=\frac{1}{2^{n}} \sum_{i=0}^{2^n-1}|y\oplus f(i)\rangle\langle y \oplus f(i)|$$ The result is pure state if and only if $$f$$ is constant. Hence $$|\phi\rangle$$ is entagled iff $$f$$ is not constant.

• But f is a function of two parameters, not one May 2 '19 at 4:55
• You can treat two $n$-bit parameters as one $2n$-bit parameter. May 2 '19 at 7:00

It depends on the input state.

If f(x, y) is zero for all x, y in the superposition, then the output will equal the input.

This operation is its own inverse, so if you apply it to an unentangled state u and get an entangled state v, that means when you get v as an input state the operation actually disentangles it.

• I've added the extra condition, please take a look Apr 30 '19 at 3:43