I understand that usually the combinatorial optimisation problems are turned into QUBO, which has a very simple mapping to Ising Hamiltonians. Ising Hamiltonians in turn have the desired properties of being diagonal in computational basis and the ground state is one of the computational basis vectors. It is thus easy to measure the state in the computational basis and obtain the bit string solution.
The problem is that Ising Hamiltonian and QUBO are quadratic in its terms and allows at most 2 body interactions. I recently came across a paper about integer factoring expressed as optimization problem (Quantum factorization of 56153 with only 4 qubits), where the cost function is a third degree polynomial. I was able to reduce this to 2 body interactions and thus make the problem QUBO, map it to Ising Hamiltonian and solve it on IBM machines using QAOA. However, this conversion between polynomial of degree 3 to degree 2 costs me extra qubits.
What is then the general approach when you have 3/4 body interactions, for example as in this paper I linked? The authors of this, as well as the authors of previous works they cite, are not concerned with the fact that this is not QUBO. Are there alternatives to Ising Hamiltonians and QUBOs in such cases? Is it correct that we could use any form of Hamiltonian (not necessarily Ising) for QAOA/VQE as long as it is decomposable into tensor products of Pauli Z operators (which makes it diagonal in computational basis)?