5
$\begingroup$

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"

$\endgroup$
5
  • $\begingroup$ +1 but I removed the second question since there's a "one question per post" policy. You can ask the second question in a different post. $\endgroup$ Feb 15, 2021 at 22:18
  • $\begingroup$ @user1271772 Huh, I feel like the two things I brought up are related ("X is not doable in Qiskit. I'm curious whether this is a Qiskit limitation or a theoretical limitation"), but okay, rules are rules - although "Qiskit" is still in the title of the post and in the tags, which I guess makes no sense after your edit... And I'm a bit puzzled by having my wording changed from "conversion" to "quadratization", since I didn't know this was the only way of achieving that, but hey, at least I got that part of my question answered by looking at the diff between edits ;) $\endgroup$
    – kontojulii
    Feb 16, 2021 at 11:46
  • $\begingroup$ Qiskit and the IBM hardware can treat super-quadratics, but if you can make it a quadratic with similar number of qubits and similar coefficients, the quadratic is usually better (lower error rates). $\endgroup$ Feb 16, 2021 at 15:20
  • $\begingroup$ @user1271772 I need to research the term "super-quadratics", because I've never heard of it. If it means polynomials with a higher degree, then I'm still pretty puzzled, because I didn't find anything related to that in the docs and all my attempts have ended in Qiskit throwing exceptions related to the degree being too high. I guess I'll try to ask this question separately - but first I need to understand if this is possible theoretically :) $\endgroup$
    – kontojulii
    Feb 16, 2021 at 17:03
  • 1
    $\begingroup$ IBM can do cubics. Kristan Temme from IBM told me that. Maybe you should ask a separate question about why it's not working in qiskit: show the code and the error. $\endgroup$ Feb 16, 2021 at 18:05

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yeah, thanks! I figured it out in the end :) This was purely a Qiskit issue. The default QuadraticProgram class does not allow for converting HOBO's into Hamiltonians (it throws errors about the order being too high), so I had to write my own PolynomialProgram class in order to be able to create the needed Hamiltonians easily :) $\endgroup$
    – kontojulii
    Aug 15, 2021 at 20:23
  • $\begingroup$ This may be worth pull requesting. I would be happy to check the code 😉 $\endgroup$
    – Adam Glos
    Aug 16, 2021 at 22:36

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.