What is the complexity of estimating the expectation value of an observable?

Question

The average value of an operator $O$ in the state $\left.|\psi\right>$ is $$\overline{O}=\left<\psi|O|\psi\right>$$ Now for simplicity let $\left.|\psi\right>=\left.|0\right>^n$ and assume we have a circuit that prepares $O$. How many times one has to run this circuit and measure $O$ in the computational basis to get an accurate estimation of $\overline{O}$ ?

I guess one needs to somehow describe what kind of operator $O$ is. For example, if there is a very large eigenvalue $\lambda$ of $O$ which appears with a very low probability $p$ in the state $\left.|0\right>^n$ I expect the required number of trials to depends strongly on $p$ and $\lambda$.

Initially my question arose when reading this paper which states on the first page that when $O$ is a product of single-qubit observables its average can be computed efficiently by running the quantum circuit $O$ many times and averaging the results. Then the authors go on to give efficient classical algorithms for the same task, but they do not explain what is the complexity of the quantum algorithm. It is not clear to me if it is not exponential in the number of qubits.

Another motivation for my question. Say we use the VQE (variational quantum eigensolver) to find the ground state of some Hamiltonian. The procedure is to build an ansatz quantum circuit, measure its average energy and then optimize the ansatz parameters to go towards lower energy. My problem is with the second step "measure average energy". How many times one is supposed to run the quantum circuit for to get the average energy estimation?

Answer 1

If you want to extract the exact value then would need infinite number of samples.

However, assume no hardware noise, based in the Chebyshev's inequality you would need to do $O(1/\epsilon^2)$ to get within $\epsilon$ accuracy for each circuit in your experiment. Here, each circuit correspond to a Pauli term that your operator $O$ decomposed into. For instance, $O = 1.5Z + 2X - 3Y$. Then you would need to create 3 circuits to calculate each expectation $\langle \psi | Z | \psi \rangle$, $\langle \psi | X | \psi \rangle$, $\langle \psi | Y | \psi \rangle$. See this answer here for more detail. Each of those circuit will require $O(1/\epsilon^2)$ shots/runs to extract an expectation value within $\epsilon$ from the true expectation value.

Thus, you can see that it can be quite expensive.

However, on current quantum devices, the noise is so large that you will never able to get within says $10^{-3}$ accuracy anyway. So by doing a lot of shots/runs won't help much. If you running VQE or any type of variational quantum algorithms on current hardware, $\approx 10,000$ shots should be enough. If you do too many shots, you will ended up picking up the noise landspace of the cost function...