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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.