# Sequence of controlled gates on non-eigenstates

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?

• 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$. Mar 28 at 11:50

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