Why do we decompose the hamiltonian into Pauli strings to measure the expectation value?

Question

Measuring the expectation value of a hamiltonian is an essential step in some algorithms like QAOA.

I noticed that the procedure always starts with decomposing the hamiltonian into a sum of Pauli strings, then proceeding to building separate circuits to measure the expectation value, then adding them all.

It seems like it would be simpler to simply measure the state, compute the hamiltonian on a classical computer for the bit string measured, repeat and take the average.

Is there a reason why we like to measure the expectation value using the Pauli decomposition method instead? I'm guessing the answer would be it's more efficient. But I can't see why or how. It seems like we need to repeat many measurements for both procedures.

Answer 1

This paragraph from Peruzzo et al. can help.:

"Thus the evaluation of $\langle{H}\rangle$ reduces to the sum of a polynomial number of expectation values of simple Pauli operators for a quantum state $\mid\psi_i\rangle$, multiplied by some real constants. A quantum device can efficiently evaluate the expectation value of a tensor product of an arbitrary number of simple Pauli operators, therefore with an $n$-qubit state we can efficiently evaluate the expectation value of this $2^n \times 2^n$ Hamiltonian."

In other words, Pauli decomposition decomposes the Hamiltonian into states that are easily preparable on a quantum computer.

Answer 2

If I understand you correctly, then you suggest to calculate the expectation value of the Hamiltonian as $$\langle \hat H\rangle=\sum_{i=1}^{2^N}p_i \langle i|\hat H| i\rangle$$ where $N$ is the number of qubits and $p_i$ is the probability to measure state $|i\rangle$.

If you do this, you're neglecting off-diagonal elements. This can easiest be seen by considering the state $$|{\Psi}\rangle=\frac{1}{\sqrt 2}\left(|0\rangle+|1\rangle\right)$$ with expectation value $$\langle \Psi|\hat H| \Psi\rangle=\frac{1}{2}(\langle 1|\hat H| 1\rangle+\langle 0|\hat H| 0\rangle+\langle 0|\hat H| 1\rangle+\langle 1|\hat H| 0\rangle)$$

where off-diagonal elements of the Hamiltonian are nonzero in general.