Quantum phase estimation predicts the eigenvalues of a unitary operator given an eigenstate, using a sequence of controlled versions of that operator. The math relies on the fact that $ |0, \psi \rangle + |1 \rangle \otimes U | \psi \rangle = | 0, \psi \rangle + e^{2\pi i \theta} |1, \psi \rangle = (|0 \rangle + e^{2\pi i \theta} | 1 \rangle) \otimes | \psi \rangle$.

But what if we are given a circuit that looks a bit like this?

circuit example

Where $| \psi \rangle$ is just a random state.

Taking a look at the first CNOT, the control qubit looks like:

$$ \frac{1}{\sqrt{2}} ( | 0 \rangle + | 1 \rangle) $$

and the target is just $| \psi \rangle$.

This produces a state

$$ \frac{1}{\sqrt{2}} ( |0, \psi \rangle + |1 \rangle \otimes X | \psi \rangle) $$

The trouble comes with the next CNOT gate; how would we find the state? There is no direct target state, it is already entangled with another qubit (the first control bit).

So what is the math behind this?

  • $\begingroup$ By hypothesis, $|\psi\rangle$ is in a superposition of eigenstates. Everything is linear, so if you were to measure you would get one of the eigenstates, with probability determined by the amount of overlap with $|\psi\rangle$. $\endgroup$ Commented Mar 28, 2023 at 11:50

1 Answer 1


A general $n$-qubit (pure) state $|\psi\rangle$ that is not necessarily an eigenstate of a unitary operator $U$ that acts on $n$ is nonetheless in a linear superposition of the eigenstates of $U$, regardless of what $|\psi\rangle$ or $U$ are. Running the quantum phase estimation algorithm on such a state leads to a natural probability distribution, with support on the eigenvectors (eigenphases) of $U$. The probability of sampling eigenvalue $\phi$ is given by the squared overlap with $|\psi\rangle$.

In the late 90's Abrams and Lloyd assumed that $|\psi\rangle$ has an exponential amount of overlap with an eigenbasis of $U$, but by the mid-2000's Wocjan and Zhang had relaxed this requirement and had just defined, by fiat, that particular probability distribution (which they then proved was promise-BQP complete to sample therefrom).

Your question may in particular be when $U=X^{\otimes n}$, e.g. when $U$ is the bit flip of each of the qubits $n$. If you have a particular $|\psi\rangle$ in mind, you could probably patiently work it out by decomposing $|\psi\rangle$ into the eigenbasis of $U$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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