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
    Aug 8 '20 at 5:40
  • $\begingroup$ Im particularly looking to solve decision problems mapped to combinatorial optimization problems. For example, 3-SAT or MAX-CUT $\endgroup$ Aug 10 '20 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.