# Computing the expectation values of a Hamiltonian constructed from a cost functions in combinatorial optimization

One of the main steps in Hybrid Quantum algorithms for solving Combinatorial Optimization problems is the calculation of the expected value of a hermitian operator $$H = \sum{H_i}$$ (where $$H_i$$ are products of Pauli Matrices on a subset of the qubits) constructed from the structure of the optimization function $$C(z)$$ with respect to some parametrized state $$\newcommand{\ket}[1]{\lvert#1\rangle}\ket{\theta}$$.

As far as I've read, in practice one of the main procedures in calculating this expectation value is through sampling, where you basically measure $$\ket{\theta}$$ on the computational basis and use the proportions of observed outcomes as the probability of each solution and then evaluating $$C(z)$$ on each outcome (https://qiskit.org/textbook/ch-applications/qaoa.html).

Wouldn't this procedure be infeasible when $$n$$ grows too big? If anyone knows of other alternatives it would be greatly appreciated

• What is the application you're interested in? Could you give more insight into the domain of alternatives that'd be of interest – C. Kang Aug 8 at 5:40
• Im particularly looking to solve decision problems mapped to combinatorial optimization problems. For example, 3-SAT or MAX-CUT – César Leonardo Clemente López Aug 10 at 17:33