QAOA calculation expectation value

Question

Given the QAOA circuit $U(\vec\gamma, \vec\beta)$, associated to some cost hamiltonian $H_C$, and evolving the state $|0\rangle^{\otimes n}$ into $|\vec\gamma, \vec\beta\rangle = U(\vec\gamma, \vec\beta)|0\rangle^{\otimes n}$, there is a difference in calculating the expectation value $$\langle H_C \rangle = \langle \vec\gamma, \vec\beta| H_C | \vec\gamma, \vec\beta \rangle $$ and calculating the value as shown in Qiskit Textbook by measuring observable $\sigma^z$ instead of $H_C$ (repeating the measure $N$ times), obtaining $N$ bitstring and calculating manually, classically, the "mean cost" which is a formula similar to $$ \text{cost}_{H_C} = \sum_{i=1}^N H_C(i\text{-th bitstring})/N$$ where $H_C(\text{bitstring})$ is an abuse of notation indicating the cost associated to a single bitstring, a single sample measured by this circuit.

For $N$ as large as you want, is $\langle H_C \rangle = \text{cost}_{H_C}$? Is there a proof for this?

Answer 1

Why do you think there is a difference between those two statements of the expectation value? Notice that the cost function only contains the operators $Z$ and $I$, so we only need to measure in the $z$-basis. The classical cost function is $$ \begin{align} C &= \sum_{\langle jk \rangle \in \text{edges}} C_{\langle jk \rangle}\\ C_{\langle jk \rangle} &= \frac{1}{2}(1 - g(j)g(k)) \end{align} $$ where $g(\cdot)$ assigns $+1$ or $-1$ to a vertex, depending on whether it is assigned to the left or the right of the cut. The cost is maximized when for as many edges as possible, we have assigned the vertices of the edge to different sides of the cut. This is directly mapped to a quantum Hamiltonian when we replace $g(\cdot)$ with $Z$ and interpret computational bitstrings as cut assignments.
$$ \begin{align} C_{\langle jk \rangle} \rightarrow \hat{C}_{\langle jk \rangle} = \frac{1}{2}(I - Z_j \otimes Z_k) \end{align} $$ Notice that the Qiskit notebook says that "the problem Hamiltonian specific to the Max-Cut problem up to a constant is..." because we don't care about the identity term in each $\hat{C}_{\langle jk \rangle}$. When we sample the state $|\vec{\gamma},\vec{\beta}\rangle$ and obtain a bitstring, evaluating the Hamiltonian for that string, by construction, yields the classical cost of that cut assignment, so it's not an abuse of notation to evaluate the classical cost function on a classical bitstring. The probabilistic nature of the sum is implicitly included by the fact that the $i$-th bitstring is obtained with some probability that depends on the particular distribution of $|\vec{\gamma},\vec{\beta}\rangle$. The final equality you mention holds in the limit of infinite samples, where for a finite number of samples we would expect an error that scales like $\sigma/\sqrt{N}$ (where $\sigma$ is the true standard deviation).

Please let me know if this helps or if I should include more details somewhere :)