Optimal sampling strategy for VQE

Question

In VQE we wish to minimize some cost function $F(\vec{x})$ that is dependent on a quantum state $\left| \psi_\vec{x} \right>$ which is prepared by a unitary $U(\vec{x})$ depending on some (typically real) parameters $\vec{x} \in \mathbb{R}^n$. A typical example for the cost function is the energy expectation value of some hamiltonian, i.e. $F(\vec{x}) = \left< \psi_\vec{x} \right|H \left|\psi_\vec{x} \right>$. Usually I can't measure my cost function directly, but only learn about it by making more and more measurements. For optimization I need some accuracy to decide in which direction to take the next optimization step, but I don't want to take arbitrarily many samples before moving on, since each sample means preparing $\psi_\vec{x}$ and measuring its energy w.r.t $H$.

Is there any research done, on what are optimal (in the sense of minimizing the number of calls to my quantum computer) sampling strategies for this kind of problem? Or what should I search for? "optimizing functions from samples" doesn't get me anywhere.

Cheers, Jan Lukas

Answer 1

This is an interesting question. I was looking into optimize the number of samples needed in VQE as well.

We know that that the number of samples in VQE to get accuracy error of $\epsilon$ scales as $O(1/\epsilon^2)$. To be more precise, if

$$ H = \sum_{i=1}^N h_i P_i $$

where $P_i$ represent the pauli string then $$\langle H \rangle = \sum_{i=1}^N h_i \langle P_i \rangle $$ by linearity and $$ Var[H] = \sum_{i=1}^N h_i^2 \langle \Delta P_i^2 \rangle \ \ \ \textrm{where} \ \ \ \langle \Delta P_i^2 \rangle = \langle P_i^2 - \langle P_i\rangle^2 \rangle $$ So the error of $\langle H \rangle$ after taking $S$ samples is $$ \epsilon^2 = \dfrac{Var[H]}{S} \leq \dfrac{N h}{S} \ \ \ \textrm{where} \ h = max\{|h_1|^2, |h_2|^2, \cdots, |h_N|^2 \} $$

So this is a problem since to get a chemical accuracy, especially for large system, we would probably need hundred of thousands of samples. Which give us a big overhead.

After looking around, I found this paper: Accelerated Variational Quantum Eigensolver

It claims to have up-to-exponential reduction on the number of samples required.

Maybe you already know about this but I thought to put this here anyway.