Sequence of controlled gates on non-eigenstates

Question

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?

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?

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$