# Is the final state in the quantum period finding algorithm entangled?

In the period finding algorithm (see the picture), through the standard procedure in quantum computing algorithms, we have $$U_f|\Psi\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\left(\sum_{x=0}^{2^n-1}|x\rangle\right)\otimes|f(x)\rangle.$$ Then the next key step, we apply the measurement. My question is, if we apply the measurement with computational basis $$P_m$$ only in the second component (the space where $$|f(x)\rangle$$ lives), then this measurement with respect to the whole composite system is $$I\otimes P_m$$.

Then follow this viewpoint, the "first" component should not be changed after the measurement right? (Since $$\left(\sum_{x=0}^{2^n-1}|x\rangle\right)$$ and $$|f(x)\rangle$$ are clearly not entangled, i.e. it can be written as the form $$|\phi\rangle\otimes|\psi\rangle$$). Therefore the resulting state should be something like $$\underbrace{\left(\sum_{x=0}^{2^n-1}|x\rangle\right)}_{\text{unchanged}}\otimes|f_0\rangle$$.

Where did I have the mistake?

• they are entangled. The parenthesis should also include the $|f(x)\rangle$ term. Otherwise what would the $x$ in $|f(x)\rangle$ mean? – glS May 15 at 19:19
• @gIS I think your comment should be an answer :-) – Adam Zalcman May 15 at 19:37

The state is indeed entangled. The parenthesis should include the $$|f(x)\rangle$$ factor in the equation (otherwise, what would the $$x$$ in $$f(x)$$ mean?).