3
$\begingroup$

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}$$

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

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)$$

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ OK, thanks for interesting papers. However, QAOA as originally designed by Farhi is intended for quadratic problems, right? It of course can be exapnded but then it is not QAOA but general simulation of multi-body interaction Hamiltonian, right? $\endgroup$
    – Martin Vesely
    Apr 26 at 15:29
  • 1
    $\begingroup$ The original Quantum Approximate Optimization Algorithm (QAOA) paper does not mention higher order terms, at least as far as I can tell. However, the algorithm itself, along with the generalization called the Quantum Alternating Operator Ansatz (same acronym of QAOA) can directly be applied to problems with higher order terms. $\endgroup$
    – Elijah Pelofske
    Apr 27 at 3:40
  • 1
    $\begingroup$ Thank you for the confirmation. That was a reason for my answer below where I mentioned that original QAOA is designed only for QUBO. To use it for HUBO you need to reduce the power. However, this doesn't rule out existence of native algorithms for HUBO based on Hamiltonian simulation. $\endgroup$
    – Martin Vesely
    Apr 27 at 6:21
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Okay, thanks. I'm still perplexed by a few things. In other papers, I've seen Hamiltonians that have multi-body terms referred to as "Ising Hamiltonians". For example, the well-known paper arxiv.org/pdf/1804.09130.pdf, in the abstract refers to "Ising Spin Operators", but then clearly there are multi-body terms $Z_1 Z_2...Z_n$ in the RHS of Table 1, and other places. Are they assuming that these Hamiltonians will be approximated? Or, are they Ising Hamiltonians readily implementable in QAOA, etc.? $\endgroup$
    – underdog987
    Apr 24 at 14:48
  • 1
    $\begingroup$ @underdog987: If you look at the page 1, the author said that so far many researches focused on reduction of optimization problems to quadratic one to be solvable with annealing approach. On page 2, the author said that his work generalize Ising Hamiltonians. On page 12, in fig. 1, you can see implementation of a Hamiltonian with three-body interaction. The circuit is clearly different from the one used in QAOA which assumes only two-body interaction. In sum, the author introduces more general approach to translation of Boolean functions to Hamiltonians. QAOA is only special case. $\endgroup$
    – Martin Vesely
    Apr 24 at 21:24
  • 1
    $\begingroup$ @underdog987: continued: So, QUBO, Ising and QAOA are directly related. Higher order polynomial binary functions can be either reduced to quadratic ones at the cost of additional ancilla qubits or simulated with different kind of Hamiltonians than Ising. By the way, thank you for bringing the article to my attention. It is really interesting. $\endgroup$
    – Martin Vesely
    Apr 24 at 21:36
  • 1
    $\begingroup$ Great paper right? I'm implementing this on qiskit, so the hardware is limited to what QisKit can simulate. One of the papers you cited seems to require "couplers" which I'm not familiar with. The other seems to double the total number of qubits, since it requires an ancilla qubit for each logical qubit. Thanks for the resources. $\endgroup$
    – underdog987
    Apr 28 at 2:39
  • 1
    $\begingroup$ @underdog987: couplers are devices used in quantum annealers coonecting two qubits mutually. This allows to represent quadratic terms. In QAOA, CNOTs coupled with Rz gates are equivalent to the couplers. $\endgroup$
    – Martin Vesely
    Apr 28 at 6:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.