Boosting quantum annealing performance through direct polynomial unconstrained binary optimization

Quantum annealing addresses optimization problems of practical relevance using quantum-computing hardware. While problems are typically formulated as quadratic unconstrained binary optimization (QUBO) and encoded into spin-glass Hamiltonians with two-body interactions, many optimization problems have more natural representations as higher-order polynomial unconstrained binary optimization (PUBO). Through a paradigmatic example, we demonstrate that PUBO encodings can reduce the required number of logical qubits by up to an order of magnitude while significantly decreasing the scaling exponent of the minimum energy gap compared to QUBO formulations. This advantage persists even when accounting for the overhead of synthesizing PUBO cost Hamiltonians through universal one- and two-qubit gate sets. We also examine important subtleties in comparing annealing times between problems with different relevant energy scales. Our findings suggest a promising approach to enhance both resource efficiency and sweeping speed in quantum annealing—crucial improvements for solving larger-scale optimization problems relevant to industry.