Why uncomputing removes entanglement in general?

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?

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.
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}$$.
• 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. Commented Dec 10, 2022 at 6:41
• @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! Commented Dec 10, 2022 at 19:30
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