# Max eigenvalue algorithm via annealing starting from Gibbs state

In this talk, and the corresponding slides on page 24/44, Brandao talks about the max eigenvalue problem which is: Given a Hermitian $$n\times n$$ matrix $$H$$, approximate its largest eigenvalue. (Note that this is basically the problem of finding the ground state energy for Hamiltonian $$-H$$) He then suggests the following algorithm to solve this problem with a quantum computer:

1. Prepare the Gibbs state $$\rho=e^{\beta H}/\text{tr}(e^{\beta H})$$
2. Cool down the system, i.e. take the limit $$\beta \to \infty$$

I can see, how in this limit, the Gibbs state tends to the ground state of $$-H$$, i.e. the maximum eigenvalue state of $$H$$ since in the eigenbasis with eigenvalues of $$H$$ given by $$E_1\geq E_2 \geq \dots \geq E_n$$, we have \begin{align} \rho=e^{\beta H}/\text{tr}(e^{\beta H})&=\frac{1}{\sum_{i=1}^n e^{\beta E_i}}\text{diag}(e^{\beta E_1}, \dots,e^{\beta E_n} )\\ &=\frac{1}{1+\sum_{i=2}^n e^{\beta (E_i-E_1)}}\text{diag}(1, e^{\beta (E_2-E_1)} \dots,e^{\beta (E_n-E_1)} )\\ & \overset{\beta\to\infty}{\to} \text{diag}(1, 0, \dots, 0) \end{align} and thus the state ends up in the pure state $$\rho=|\psi_{max}\rangle \langle \psi_{max}|$$ where $$|\psi_{max}\rangle$$ is the eigenstate to the maximum eigenvalue $$E_1$$.

So far, so good. Now, I have two questions:

1. Brandao has on his slides the result that cooling down to $$\beta = O(\log (n) /\delta)$$ one can approximate the max eigenvalue to precision $$\delta$$. How do you derive this? Does one need to solve $$|E_1-\text{tr}(\rho H)|<\delta$$ for $$\beta$$?
2. In this abstract algorithm, how does one actually get the eigenvalue from the cooled down Gibbs state? One still has to measure the system somehow as far as I understand.