4
$\begingroup$

I met a subroutine to change the phase for a subset of basis vectors, and I can't understand why uncomputing in this case removes the entanglement. I want to generalize it a little. Specifically, I want to know whether in general, uncomputing removes the entanglement.

The algorithm is like follows (a is a temporary qubit, and I generalized it.)

$$U_f\left|x,a\right\rangle$$ $$P\left|a\right\rangle$$ $$U_f^{-1}\left|x,a\right\rangle$$ Where $U_f\left|x,y\right\rangle\mapsto\left|x,y\oplus f(x)\right\rangle$, and P is an arbitrary operator. In the textbook, it is a phase shift operator for only $\left|1\right\rangle$.

Since when we operate on a, x also changes, the "uncompute" doesn't undo what the computation has done in line 1. Why does it remove the entanglement? I think in the two qubit case, it is possible to write the matrices and calculate, but what about the general case? And if in addition to operate on a, we also operate on x in between, does it also have the same effect?

Thanks in advance.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

First of all, this is not true for every operator $P$. For instance, let us assume that the starting state is: $$\newcommand\ket[1]{\left|#1\right\rangle}\frac{\ket{0}+\ket{1}}{\sqrt{2}}\ket{0}=\frac{1}{\sqrt{2}}\left(\ket{00}+\ket{10}\right)$$ Let us assume that $f=\mathrm{id}$, that is $f(x)=x$ for all $x$. Applying $U_f$ yields: $$\frac{1}{\sqrt{2}}\left(\ket{00}+\ket{11}\right)$$ We now use the Hadamard gate as our operator $P$, which transforms that state into: $$\frac{1}{2}\left(\ket{00}+\ket{01}+\ket{10}-\ket{11}\right)$$ And finally, we apply $U_f$ once again: $$\frac{1}{2}\left(\ket{00}+\ket{01}-\ket{10}+\ket{11}\right)$$ This state is entangled. Thus, uncomputing $U_f$ is not enough for ensuring the resulting state is not entangled.

So, to answer your question: it does not necessarily remove entanglement. In fact, it most generally doesn't.

Just to mention, there are some corner cases though. For instance, if the second register is a basis state $\ket{a}$ and if $P$ is a diagonal gate, then the final state will always be separable, with the second register being in state $\ket{a}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much for you answer. I have a hard time follow it. According to my calculation, $U_f(I \otimes P)U_f^{-1}$ would not be $I\otimes D$ but something like a diagonal matrix $ e^{i\theta_1}, e^{i\theta_2}, e^{i\theta_2}, e^{i\theta_1} $, when f(x) = -x for 1-qubit case, and $P = [e^{i\theta_1}, e^{i\theta_2}]$. Did I make a mistake? I am not good at linear algebra so maybe I made a mistake somewhere. $\endgroup$
    – Curiosity
    Dec 10, 2022 at 6:41
  • $\begingroup$ @Curiosity You're totally right! I messed up with the $1$ and $2$-qubit cases. I've removed this example from my answer. Thanks for spotting this! $\endgroup$
    – Tristan Nemoz
    Dec 10, 2022 at 19:30
  • $\begingroup$ Thank you very much. The book uses this method for many subroutines and I thought it is a general pattern. $\endgroup$
    – Curiosity
    Dec 12, 2022 at 1:04
1
$\begingroup$

The idea is to remove the entanglement between $a$ and $x$. It doesn't mean the operations between steps 1 and 3 did not happen. The operations only alter the amplitudes of $x$ after the uncomputation

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.