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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.