Output of Quantum Phase Estimation Algorithm

Question

In section 5.2.1 of Nielsen Chuang, Performance and Requirements, there is an idea, that what happens if we can't prepare eigen state $|u\rangle$ and instead have a state $|\psi\rangle$ which is represented by $\sum_{u} c_{u}|u\rangle$. Output state is $\sum_{u} c_{u} |\phi_{u}\rangle|u\rangle$

Now we will measure the first qubit and it will turn out to be $|\phi_{u} \rangle$ with probability proportional to $c_{u}^{2}$.

But I am curious, what will be the state of the second qubit? (Is it entangled with the first qubit?)

Some excerpts from the book itself:

Answer 1

Quick side note before proceeding to answering your question: $|\phi_u\rangle$ and $|u\rangle$ are registers of qubits since they can represent a set of qubits (and not necessarily a single qubit).

Now on to answering your question: at the end of the phase estimation algorithm, if we make a measurement and the first register collapses to $|\phi_u\rangle$ then the second register will collapse to $|u\rangle$. This is because, as you mentioned, they are entangled. To make this more apparent, here is the state before the measurement written out explicitly: $$\sum_{u=1}^n c_u |\phi_u\rangle |u\rangle = c_1|\phi_1\rangle|1\rangle + c_2|\phi_2\rangle|2\rangle + ... + c_n|\phi_n\rangle|n\rangle.$$ Therefore whichever $|\phi_u\rangle$ you measure in the first register, the second register will collapse to the corresponding $|u\rangle$

Answer 2

The second register state stay as the state you prepared it in, that is, it is left unchanged. Note that if $|u\rangle$ is a eigenstate of $U$ with eigenvalue $e^{2\pi i \theta}$ then when you apply $U^{2^j}$ to the state $|u\rangle$, you will get $U^{2^j} |u\rangle = e^{2\pi i \theta 2^j}|u\rangle $.

And no, the state in the first register is not entangled to the state in the second register as you can see the output state is written as $\sum_u c_u |\varphi_u\rangle |u\rangle = \sum_u c_u |\varphi_u\rangle \otimes |u\rangle $, that is they can be written as a tensor product (not entangled).

---

For a quick example, consider the first part of the circuit:

In particular, let's suppose $U$ is the Pauli-Z operator and $|u\rangle$ is just the state $|1\rangle$. More specifically, we are considering the circuit below:

Note that the second qubit is in the state $|1\rangle$ after application of the $X$ gate. The first qubit is in the state $\dfrac{|0\rangle + |1\rangle}{\sqrt{2}}$ after the application of the Hadamard gate. Then we applied the Controlled-Z gate. Note that $|1\rangle$ is an eigenstate of the Pauli-Z operator with $Z|1\rangle = -|1\rangle$. The state of the overall system is now: $$ |\psi \rangle = \dfrac{|01\rangle - |11\rangle}{\sqrt{2}} $$ note the negative is resulted from the eigenvalue of $-1$ when we apply Pauli $Z$ to the state $|1\rangle$. It might be tempted to say that this state is entangled but it is not... because we can rewrite it as follow:

$$ |\psi \rangle = \overbrace{\bigg( \dfrac{|0\rangle - |1\rangle}{\sqrt{2}} \bigg)}^{\textrm{first qubit}} \otimes \overbrace{ |1\rangle}^{\textrm{second qubit}} $$

So the state of the second qubit stays the same. No changes. The state of the first qubit pick up a relative phase factor coming from the eigenvalue of $-1$ when we apply $Z$ to $|1\rangle$.

You can now try to look at:

which is now the circuit:

Once you worked it out, you will see that you can write the state of the system as follow:

$$ |\psi \rangle = \overbrace{\bigg( \dfrac{|0\rangle + |1\rangle}{\sqrt{2}} \bigg)}^{\textrm{first qubit}} \otimes \overbrace{\bigg( \dfrac{|0\rangle - |1\rangle}{\sqrt{2}} \bigg)}^{\textrm{2nd qubit}} \otimes \overbrace{ |1\rangle}^{\textrm{3rd qubit}}$$

As you can see, the state of the qubit $q_2$ stays the same. And they are not entangled to one another at all.