Preparing ground states of quantum many-body systems on a quantum computer

References

Appendix A Jordan’s result

Our main tool of analysis is a result attributed to Jordan Jordan (1875), a more modern version of which can be found in Marriott and Watrous (2005). The result states that any two projectors $Q$ and $R$ on an $N$-dimensional Hilbert space can be put in a simultaneous block-diagonal form, with blocks of size at most 2. Clearly, the operators $QRQ$ and $RQR$ share the same spectrum $\{p_{a}\}$, bounded between 0 and 1 (this can be seen by left and right polar decomposition of the operator $QR$). Their respective eigenvectors $\{q_{a}\}$ and $\{r_{a}\}$ are in general different however. Since $Q$ and $R$ are purely contractive, it follows that if $p_{a}=1$ for some $a$, then the basis can be chosen such that $|q_{a}\rangle=|r_{a}\rangle$. When $p_{a}=0$, then either $Q|q_{a}\rangle=0$ or $R|r_{a}\rangle=0$. For the intermediate values $0<p_{a}<1$, Jordan found that we can group the remaining eigenvectors in pairs that we denote $(q_{a}^{0},q_{a}^{1})$ and $(r_{a}^{0},r_{a}^{1})$ such that

with the property that $Q|q_{a}^{b}\rangle=b|q_{a}^{b}\rangle$ and $R|r_{a}^{b}\rangle=b|r_{a}^{b}\rangle$. By enlarging the dimension of the Hilbert space (at most doubling its dimension) and allowing $p_{i}$ to take the values 0 and 1, we can assume that all eigenstates of $QRQ$ and $RQR$ are paired up in this fashion, so that both sets $\{q_{a}^{b}\}$ and $\{r_{a}^{b}\}$ are complete orthonormal bases.

Appendix B Failure of the naive algorithm

The naive algorithm to approximate the ground state of a local Hamiltonian consists of using phase estimation to mark the low-energy eigenstates of $H$, and then integrating this marking procedure in Grover’s algorithm to produce a state of low energy. This strategy can easily be analyzed with the help of Jordan’s result. Indeed, let $Q$ be the projector onto the all-zero state of the $k$ auxiliary qubits used by phase estimation and $R$ be the projector on the output of the phase estimation indicating an energy less than $E$.

As mentioned in the main text, the unitary evolution $U=e^{-iH}$ cannot be realized perfectly in general, but this is a source of error that can be ignored because it doesn’t build up during Grover’s algorithm. Thus, we will assume here that the phase estimation algorithm implements $U$ exactly.

In this language, the state $q_{a}^{1}$ corresponds to a state of the form $|a\rangle\otimes|0_{k}\rangle$ where $|a\rangle$ is an eigenstate of $H$ with energy $\varphi_{a}$. The eigenvalue $p_{a}$ of $QRQ$ associated to that state is equal to the probability that the phase estimation algorithm diagnoses $|a\rangle$ as having an energy less than $E$. This is where the finite success probability of the phase estimation algorithm comes into play. The important point is that even if the energy $\varphi_{a}$ is well below or well above $E$, there is a small probability that the algorithm will give the wrong answer. The effect is more pronounced when the actual energy of $\varphi_{a}$ is close to the acceptance threshold $E$, but it is the small error probabilities that will really cause a problem. The error is zero only when $\varphi_{a}$ can be expressed exactly in binary form with $k$ bits. Thus, unless very detailed knowledge of the spectrum of $H$ is available, these small errors are unavoidable.

Continuing with the naive algorithm, we prepare a random superposition $|\psi\rangle=\sum_{a}\alpha_{a}|q_{a}^{1}\rangle$, i.e. a random state of the $n$ system qubits with the $k$ auxiliary qubits in state 0, and use Grover’s algorithm to amplify the image of $R$. This results in the state

We see that, as a consequence of the amplification of $R$, the state $\psi^{\prime}$ is no longer supported only on the image of $Q$ as indicated by the presence of the $q_{a}^{0}$ in the state. The overlap with $Q$ is easily computed

and this can be arbitrarily small. For instance, if the vast majority of states have $p_{a}\sim 1/\sqrt{N}$ and a negligible fraction of them have $p_{a}$’s of order unity, this overlap is of order $1/\sqrt{N}$.

This example summarizes the main problem of the naive approach that is overcomed by our method. We want to create a state that has a large overlap with two projectors $Q$ and $R$. When $[Q,R]=0$, we can simply prepare a random state in the image of $Q$ and use Grover’s algorithm to amplify $R$. But when the two projectors do not commute, the amplification of $R$ can move the state almost completely outside the image of $Q$, so the technique fails.

Appendix C Detailed analysis for the ground state problem

We make use of an upper and a lower bound on the inner-product of two different momentum states (c.f. Eq. 1) used by our algorithm. 1) $|\langle\varphi|\mu\rangle|\leq\frac{1}{2^{k+1}|\varphi-\mu|}$ and 2) when $|\varphi-\mu|\leq 2^{-k}/(2\pi\sqrt{\eta})$, then $|\langle\varphi|\mu\rangle|^{\eta}\geq 1/2$.

To prove the first bound, we use the inequality $|1-e^{ix}|\geq 2|x|/\pi$ for $-\pi\leq x\leq\pi$ and elementary algebra to obtain

For the second bound, assume that $|\varphi-\mu|\leq 2^{-k}/(2\pi\sqrt{\eta})$. We can use the fact that $|\langle\varphi|\mu\rangle|\geq{\rm Re}(\langle\varphi|\mu\rangle)$ to obtain

Raising to the $\eta$th power and using the inequality $(1-x)^{n}>1-nx$ for $n<1$ and $x>0$ gives the desired result.

We will now demonstrate that our algorithm will work as advertised, i.e. produce a state of energy $\mu\pm\epsilon$, with high probability. We break this proof into two parts. First, we show that the algorithm does not systematically abort and second that when it does not abort it produces the right state.

Remember that the algorithm aborts when the overlap $\|Q|\Phi\rangle\|^{2}=\sum_{a}|\alpha_{a}|^{2}|\langle\varphi_{a}|\mu\rangle|^{2}$ is less than $\mathcal{O}(1/N)$. Using the lower bound derived above, we know that if there is at least one eigenvalue, say $\varphi_{0}$, that lies in the interval $\mu\pm 2^{-k}/(2\pi\sqrt{\eta})$, this overlap will be at least $|\alpha_{0}|^{2}/2$. Since the state is chosen at random, the amplitude $|\alpha_{0}|$ has an exponentially high probability of being greater than $1/(2\sqrt{N})$ which is sufficient for the success of the amplification procedure. Note that the interval $\mu\pm 2^{-k}/(2\pi\sqrt{\eta})$ has a polynomial width, i.e. $k$ scales only logarithmically with $n$ and $\eta$ polynomially. Thus, we can sweep all values of $\mu$ to this accuracy in polynomial time.

We must now demonstrate that when the amplification procedure succeeds, then with very high probability it generates a state with the desired energy. We can assume in this case that $\|Q|\Phi\rangle\|>1/N$ since otherwise the amplification procedure would have had an exponentially small chance of succeeding. Let us first upper bound the average energy:

where $\sum_{a}^{\prime}$ is the sum restricted to values of $a$ such that $\varphi_{a}\geq\mu+\epsilon/2$. Using the lower bound on $\|Q|\Phi\rangle\|$ and the fact that $0\leq\varphi\leq 1$ we obtain

Consequently, the desired bound is obtained when $N^{2}|\langle\mu+\epsilon/2|\mu\rangle|^{2\eta}\leq\epsilon/2$. Using our upper bound on the inner product $|\langle\mu+\epsilon/2|\mu\rangle|$ yields

which is satisfied with $k\geq 2\log_{2}(\frac{1}{\epsilon})$ and $\eta\geq 1+(n+1)/\log_{2}(\frac{1}{\epsilon})$.

Similar arguments produce an upper bound on the average energy

where $\sum_{a}^{\prime}$ is now the sum restricted to values of $a$ such that $\varphi_{a}\leq\mu-\epsilon/2$. Using the lower bound on $\|Q|\Phi\rangle\|$ and the upper bound on the inner product $|\langle\varphi_{a}|\mu\rangle|$ gives

which is greater than $\mu-\epsilon$ provided that $\eta\geq 1+(n+\log_{2}\mu)/\log_{2}(\frac{1}{\epsilon})$.

Note that with a $k$ growing polynomially with $\log(n)$ and $\eta$ growing polynomially with $n$, the error on the energy decreases as $1/{\rm poly}(n)$ and the total running time is $\sqrt{2^{n}}{\rm poly}(n)$ as desired.

Appendix D Detailed analysis for problems in QMA

The analysis of the general algorithm for problems in QMA follows similar lines, but the derivation of the filter function is slightly more involved. The verification circuit $V_{x}$ acts on $m=n+h$ qubits: the $n$ qubits containing the witness and a $h$-qubit scratchpad. We make use of Jordan’s result with $Q$ being the projector onto the all-zero state of the scratchpad and $R=V_{x}(|1\rangle\!\langle 1|\otimes I_{m-1})V_{x}^{\dagger}$ is the projector onto the accepting subspace of the verification procedure. Remember that the verification procedure takes inputs of the form $|\psi\rangle=|w\rangle\otimes|0_{h}\rangle$ and accepts with probability $\|(|1\rangle\!\langle 1|\otimes I_{m-1})V_{x}|\psi\rangle\|^{2}=\|QRQ|\psi\rangle\|^{2}$. Thus, the eigenstates $|q_{a}^{1}\rangle$ of $QRQ$ correspond to witnesses with all-zero scratchpads with an accepting probability $p_{a}$.

Our algorithm makes use of $k$ additional auxiliary qubits, for a total of $n+h+k$. Armed Eqs (3-6), we see that the circuit of Figure 1 applied to the state $|q_{a}\rangle\otimes|0_{k}\rangle$ produces the outcome

Indeed, we get factor of $\sqrt{1-p_{a}}$ each time the outcome switches from 0 to 1 or vice versa, and a factor of $\sqrt{p_{a}}$ otherwise. There is an additional factor of $-1$ for every pair of consecutive 0’s.

We now apply the inverse of the circuit shown on Figure 1, producing the state

where the ellipsis represents terms outside the image of $Q\otimes|0_{k}\rangle\!\langle 0_{k}|$. The filter function is defined by

In the last step, we have approximated the binomial distributions by normal distributions. At this point, we can use Grover’s algorithm to amplify the image of $Q\otimes|0_{k}\rangle\!\langle 0_{k}|$, and the rest of the analysis proceeds as above.