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?

enter image description here

  • 1
    $\begingroup$ they are entangled. The parenthesis should also include the $|f(x)\rangle$ term. Otherwise what would the $x$ in $|f(x)\rangle$ mean? $\endgroup$ – glS May 15 at 19:19
  • $\begingroup$ @gIS I think your comment should be an answer :-) $\endgroup$ – 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?).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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