QUBO, Ising Hamiltonians and VQA

Question

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

Answer 1

In the definition from this paper [1] the cost Hamiltonian is not restricted to the Ising Hamiltonian case. The paper also has an answer for the mentioned "general approach for $3/4$ ($n$) body interactions".

A direct quote from [1]:

From a classical cost function that is a polynomial in binary variables $x_1 , . . . , x_n $, we can construct a Hamiltonian $H_C$ on $n$ qubits by first rewriting the cost function in terms of variables $z_i \in \{−1, 1 \}$, where $x_i = (1 − z_i )/2$ to obtain a polynomial $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ and then replacing each occurrence of $z_i$ with the Pauli operator $\sigma_i^z$ . Thus, $H_C$ is diagonal in the $\sigma_z$-basis and takes the form

$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$

where $C$ is a subset of all qubits, and $\alpha_C$ is a real coefficient for the many-body coupling between qubits in the subset $C$.

This means that if we have a classical cost function $f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$, we should replace $x$s with $z$s and obtain:

$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$

After simplifying replace $z$s with $\sigma_z$s:

$$H_C = 4 I - 5 \sigma_1^z - 2 \sigma_2^z + \sigma_3^z + \sigma_4^z + 3 \sigma_1^z \sigma_2^z -\sigma_2^z \sigma_3^z -\sigma_3^z \sigma_4^z -\sigma_2^z \sigma_4^z + \sigma_2^z \sigma_3^z \sigma_4^z$$

and done. Note that this procedure will work also for QUBO$\rightarrow$Ising Hamiltonian (see this answer). This way we will be able to construct the cost Hamiltonian with the desired (in QAOA) property:

$$H_C |x\rangle = f(x)|x\rangle$$

where $x = x_1 x_2 x_3 x_4$ is a bitstring.

An example of the cost Hamiltonian with $3$-body coupling between qubits can be found in this paper [2] for the E3LIN2 problem ([2] Eq. $6$ with slightly changed notations):

$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$

where $d_{abc}$ is $0$ or $+1$ or $-1$, $a$, $b$ and $c$ are qubit indexes.

---

[1] Z. Wang, S. Hadfield, Z. Jiang, E. G. Rieffel, "The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View"

[2] E. Farhi, J. Goldstone, S. Gutmann, "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem"