I am having trouble understanding some concepts in Quadratizing a high order polynomial. I am reading the review "Quadratization in Discrete Optimization and Quantum Mechanics" .

I would like to ask if there is an efficient way to reduce a generic function written in terms of pseudo-boolean variables, only in quadratic terms. In particular ,I am interested in the context of a diagonal Hamiltonian with only $I,Z$ terms. With generic, I mean, no symmetries or easy simplifications and also probably containing hundreds of high order terms.

My understanding of efficient is:

  1. With few auxilary qubits ( $ \leq n $ with $ n $ being the amount of qubits of the original high order Hamiltonian implementation ) .
  2. Without needing to measure the auxiliary qubits.

My main motivation is to find out if the quadratization can reduce the circuit depth of a random combinatorial problem. I would also like to ask if there ar any other depth reduction techniques for HOBOs , in QAOA ?

Finally, is there an library/software that does quadratizations automatically?


1 Answer 1


Quadratization is often used classically. On a quantum variational algorithm, like QAOA would be not so easy to put in practice, since it would add constraints and therefore penalties in the cost.

Another way is to directly write the Hamiltonian and the problem Hamiltonian, and use depth-reducing techniques. Check out this paper: https://arxiv.org/abs/2307.16756

  • 1
    $\begingroup$ Hi Andrea! Welcome to QCSE! Are you one of the authors in the linked paper? If so, it's quite OK to link to it - but it's best practice to at least at a little disclaimer. If possible, please edit your answer by clicking on the "Edit" button next to the "Share" button to say something like "Check out this paper: arxiv.org/abs/2307.16756 (disclaimer: I am one of the authors)." $\endgroup$ Feb 8 at 15:04

Your Answer

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

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