One approach to get the expectation value $\langle\psi|P\psi\rangle$ of a pauli string $P\in \{I, X, Y, X\}^{\otimes n}$ is the following.
- Let $(a_i, |\lambda_i\rangle)$ be eigenvalue-eigenvector pair of $P$ where $a_i\in \{0, 1\}$ as $P$ is unitary. We may write $$P = \sum_i a_i|\lambda_i\rangle\langle\lambda_i|$$ so it follows that $$\langle\psi|P\psi\rangle = \sum_i a_i|\langle\lambda_i|\psi\rangle|^2.$$
- We can thus perform a change of basis measure in the $|\lambda_i\rangle$ basis to recover the coefficients $|\langle\lambda_i|\psi\rangle|^2$ via repeated sampling.
- Evaluate the sum in step 1.
My questions about this are:
- How are we sampling? ie. Do we measure each of the $n$ qubits "separately" and estimate $p_0, p_1$ in $p_0|0\rangle + p_1|1\rangle$? This would lead to us adding $2^n$ numbers in step 3, so I don't think this is the case. Do we measure each outcome $|x_1\dots x_n\rangle$ and estimate its probability $|\langle\lambda_i|\psi\rangle|^2$ directly?
- If we measure each outcome and estimate $|\langle\lambda_i|\psi\rangle|^2$ directly, how many repeated measurements do we need to obtain accuracy within $\epsilon$? If we perform a polynomial number of measurements, most of our estimates for $|\langle\lambda_i|\psi\rangle|^2$ will be $0.$