Solving higher-order (unconstrained) binary optimization problems with QAOA without quadratization

Question

I am aware that it's possible to use QAOA to solve QUBO problems. However, I've recently seen some sources mentioning the possibility of solving HOBO/HUBO problems using QAOA as well [1][3].

While I understand that quadratization from HOBO/HUBO to QUBO could be done [1][2], I'm trying to understand if it's actually possible to solve problems with higher-order polynomials using QAOA without quadratizing them. Unfortunately, I haven't been able to find too many sources discussing this subject.

---

[1] Adam Glos, Aleksandra Krawiec, Zoltán Zimborás, "Space-efficient binary optimization for variational computing"

[2] Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima-Mwesigwa, "Compressed Quadratization of Higher Order Binary Optimization Problems"

[3] Yuichiro Minato, "Variational Quantum Factoring using QAOA and VQE on Blueqat"

Answer 1

Ok so this is pretty late, but let me still try to answer it as an author of [1] :)

When you want to implement QUBO, what you're actually doing is implementing the corresponding Ising model. The steps are following:

• prepare the QUBO
• replace each bit $b_i$ with $\frac{1}{2}(1-Z_i)$ where $Z_i$ is Pauli $Z$ operator acting on $i$-th qubit
• implement the resulted Ising model as follows
  • implement each $Z$ and $ZZ$ independently (one by one)
  • implement $Z$ by $R_z$ rotation
  • implement $Z_iZ_j$ by applying CNOT with control on $i$ and target on $j$, $R_z$ rotation on $j$ and CNOT as before
  • the rotations angle should be the weight of the Pauli operator times the angle coming from the QAOA

There is almost no difference with HOBO, however, you need to know how to implement general $Z_{i_1}Z_{i_2}\cdots Z_{i_k}$. For this you can use decompositions given in [1], Fig 3(a) (no ancilla) or Fig 3(b) (one ancilla qubits). In [1] we also use some tricks to slightly reduce the number of gates, but you can safely ignore them, but these are optional.

P.S.: In [1] we don't do any quadratization.