Does QAOA require that the problem Hamiltonian be an Ising Hamiltonian as a quadratic function of the spin variables?

Question

In the context of QAOA, I often see the problem Hamiltonian being called an "Ising Hamiltonian", and shortly after, I that the Hamiltonian is a quadratic function of the spin variables.

Is this required? If I tried to optimize a function of boolean variables which is a polynomial of degree 3 using QAOA, this would not fit the description of a quadratic. But I could still make the following substitution: $$x=\frac{1-s}{2}$$

Perhaps related: Why does the problem Hamiltonian of QAOA always consist of $Z$ and $I$ gates? Creating Ising Hamiltonian with Qiskit

EDIT In particular, I'm trying to express the following constraint: either $\sum_{i} x_i > 0$ or $\sum_{j} x_j > 0$ (or both). There might be an easier way to express this but currently my expression is of the following form:

$$(\sum_{i} x_i - k_1) (\sum_{j} x_j - k_2) ... (\sum_{i} x_i - K_1) (\sum_{j} x_j - K_2)$$

score 3 · Answer 1 · answered Apr 26 '23 at 00:09

QAOA can be applied to Ising models that contain higher order terms; see this paper and this paper. QAOA applied to higher order Ising models does not necessarily require the use of ancilla qubits, although depending on the problem and the hardware ancilla qubits may be useful.

Quantum annealing, specifically the D-Wave quantum annealers, do not natively handle higher order terms, which is why order reduction is necessary for mapping Ising models that contain higher order terms onto D-Wave quantum annealers. However, it is not required that quantum annealing in general could not handle higher order terms - that is just a question of hardware implementation. Order reduction for quantum annealing does require the use of auxiliary, or ancilla, QA qubits.

QAOA, and D-Wave quantum annealers, can handle variable states of {+1, -1} (called an Ising model) as well as {0, 1} (called a QUBO), but usually it is a bit easier to construct QAOA circuits when the variables are spins (i.e. the problem being an Ising model). Also, I should mention that QUBO and Ising models are equivalent - you can convert from one to the other easily.

To summarize, QAOA does not require that that variables states are either {+1, -1} or {0, 1}, and it does not require that there are only linear and qaudratic terms in the problem Hamiltonian.

score 1 · Answer 2 · answered Apr 24 '23 at 09:16

QAOA is designed to work with Ising Hamiltonians only. This means that the algorithm can be employed for optimization of only quadratic problems which are related directly to Ising Hamiltonians. However, it is possible to convert high order problems to quadratic ones. In other words, you can convert multi-body interactions to only two-body ones. See for example this article or this one. However, higher the power of the optimization problem, (significantly) higher the number of needed ancilla qubits.

Does QAOA require that the problem Hamiltonian be an Ising Hamiltonian as a quadratic function of the spin variables?

2 Answers2