Clarification on state prep for quantum phase estimation

Question

I have a question about how to prepare a state $|\psi\rangle$ for quantum phase estimation (QPE). My question is about whether the state prepared in QPE has to be the exact eigenstate of the operator or whether it is sufficient for applications to use another initial state that is easy to prepare.

My present understanding of phase estimation laid out below.

Phase estimation allows you to estimate the eigenvalue of a unitary operator applied to an eigenstate $|\psi \rangle $ by estimating the value of $\theta$ in the eigenvalue equation below.

\begin{equation} U |\psi \rangle = e^{2 \pi i \theta} |\psi \rangle \end{equation}

The algorithm works by preparing a state $|\psi \rangle $ and then applying some controlled $U$ operations between a state preparation register and a register of "evaluation qubits". The inverse Quantum Fourier transform is then applied before the evaluation register is measured. The phase $\theta$ can be known with greater precision by increasing the number of evaluation qubits.

A pytket circuit diagram of a trivial instance of QPE is shown below where I estimate the phase applied by a single qubit rotation gate. This is similar to a pedagogical example given in the qiskit textbook.

Here the $U$ is defined as follows

\begin{equation} U(\varphi) := \begin{pmatrix} 1 & 0 \\ 0 & e^{i \varphi} \end{pmatrix}. \end{equation}

In this case its super easy to just use the Pauli $X$ gate to prepare the $|1 \rangle$ eigenstate of $U$.

$$ \begin{equation} U(\varphi)|1\rangle = e^{i \varphi}|1\rangle \, . \end{equation} $$

My question is as follows... For more interesting applications of QPE does the state prepared have to be the eigenstate of the operator $U$ ? I don't know of a reason to expect that preparing the eigenstate $|\psi \rangle$ of some operator $U$ is an easy thing to do in general (especially without knowing the eigenvalues of $U$ to begin with).

I have heard that phase estimation is a "projective" algorithm and so projects into the eigenspace of $U$ even if the initial state isn't exactly $|\psi \rangle$. I wasn't sure exactly how to interpret this. Is it sufficient for the initial state to be "close" to $|\psi \rangle $ in some sense?

I would appreciate if someone could provide more detail on how this works or point me in the direction of some useful references. These can include how QPE is used in practice in chemistry etc.

Answer 1

Your supposition is spot on. Indeed, quantum phase estimation (QPE) can be applied even when the input state is not an eigenstate of the unitary $U$. The key point to note is that, by expanding the input state in the eigenbasis of $U$, the coefficients of such linear combination will remain unaffected by the controlled powers of $U$ as they do not mix eigenstates. As a result, given an input state $\sum_{i} c_i |\phi_i\rangle$, where $\{ |\phi_i \rangle \}$ is the eigenbasis of $U$, then the phase associated with eigenstate $|\phi_i \rangle$ is measured in the ancillary register with probability $\sim |c_i|^2$, in which case the main register is projected onto the corresponding eigenstate. This point is already noted in Nielsen & Chuang ($10^{\textrm{th}}$ anniversary edition, Exercise 5.8). Another reference that might be worth having a look at is this paper by O'Brien, Tarasinski and Terhal.

Starting from a linear combination of eigenstates is, in fact, the most relevant use of QPE, as far as applications are concerned. In particular, we foresee using QPE to find the ground state of quantum many-body systems by starting from an input state that has a non-negligible overlap with such exact ground state. By "non-negligible" we mean that the inverse of the overlap scales polynomially with the system size, otherwise the average number of repetitions will not be feasible for a sufficiently large system.

As you alluded to in your question, preparing such an input state is quite a challenge. Assuming we have no circuit depth constraints (i.e., that we have fully fault-tolerant quantum hardware at our disposal), the natural approach is to prepare such state adiabatically, although care must be taken with the choice of adiabatic path in order to avoid closing the spectral gap, in which case the adiabatic theorem breaks down. With noisy intermediate-scale quantum hardware, we have to be even more ingenious, exploiting physical insights about the specific problem we are tackling to find an easy-to-prepare input state that is close enough to the exact ground state.

Answer 2

As a follow-on to @bm442's already thorough answer, indeed given some Hamiltonian $\mathcal H$ such that we can efficiently simulate controlled versions of the corresponding unitary $U=e^{-i\mathcal H t}$, and given some arbitrary (pure) state $|\psi\rangle$ that is not necessarily an eigenstate of $U$, the mere sampling of the natural probability distribution so defined and supported on the $U$-eigendecomposition of $|\psi\rangle$ is promise-BQP complete, as noted by Wocjan and Zhang.

This idea that the QPE algorithm can be applied to states that are not necessarily eigenstates of the unitary was exploited by Harrow, Hassidim, and Lloyd in their linear systems algorithm. Therein, they initially prepare their input state $|b\rangle$, which is not even an eigenstate of $U$, but nonetheless run the QPE algorithm on $|\psi\rangle$ to leave the phases in superposition, and later apply filtering/post-selection. Gharibian has referred to this kind of operation as "eigenvalue surgery".

---

On another note, one thing that I've been curious about is the intuition in the old paper of Abrams and Lloyd, which is, as far as I can tell, precisely a description of the quantum phase estimation algorithm, but using old-timey late 1990's language, without anything like the nice pytket circuit diagram above that we know and love. Nonetheless they state:

If the state $V_a$ satisfies the property that $|\langle V_a|V\rangle|^2$ is not exponentially small - that is, the approximate eigenvector contains a component of the actual eigenvector that is bounded by a polynomial function of the problem size - then $V$ and $\lambda_v$ can be found in time proportional to $1/|\langle V_a|V\rangle|^2$ and $1/\epsilon$, where $\epsilon$ is the desired accuracy.

In the late 90's when Abrams and Lloyd had published their paper, you wanted to have an exponential overlap, but by the work of the late 2000's that was fully relaxed so that the test state $|\psi\rangle$ can be any arbitrary state, and as @bm442 states you can make a guess close to an eigenstate and adiabatically evolve towards one.