# Output of Quantum Phase Estimation Algorithm

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:

• They seem to make the implicit assumption that $|u\rangle$ is measured as well since $|\varphi_u\rangle$ is obtained with probability $|c_u|^2$. If you measure only the first qubit, I guess that you are left with a superposition of all the $|u\rangle$ that have eigenvalue $e^{2\pi i\varphi_u}$. – lamontap Jan 15 at 21:38
• @lamontap Where do you find that assumption? yes so if there is just one such $|u\rangle$ then it will be just single state else superposition of all two or three etc. – user27286 Jan 15 at 23:01
• The book says "where $u$ is chosen at random with probability $|c_u|^2$". This happens when you measure the second register of $\sum_u c_u|\varphi_u\rangle|u\rangle$. If you were to measure only the first register, you would only get the same probability distribution if the $|\varphi_u\rangle$'s are orthogonal (which may not necessarily be the case). – lamontap Jan 22 at 16:40

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$$

• How do you know it is entangled? This is a general question, how do we know if a state is entangled or not? – user27286 Jan 27 at 15:59
• In general two states are entangled if you can't write them as a product state. A simple example: $\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$ is not entangled because you can write it as $\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right) \otimes \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)$. However a state like $\frac{1}{\sqrt{2}}\left(|00\rangle+|11\rangle\right)$ cannot be written as $\left(|a|0\rangle+b|1\rangle\right) \otimes \left(c|0\rangle+d|1\rangle\right)$. A quick way to check is see if measuring one state will give you info about the second – Rajiv Krishnakumar Jan 29 at 13:46

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.

• But here in the second register we pass $\sum_{u} c_{u}|u\rangle$..it can't stay the same isn't it? – user27286 Jan 15 at 9:51