Approximate quadratization of high-order Hamiltonians for combinatorial quantum optimization
Sabina Drăgoi, Alberto Baiardi, Daniel J. Egger · Physical Review Research · 2026
Combinatorial optimization problems have wide-ranging applications in industry and academia. Quantum computers may help solve them by sampling from appropriately prepared Ansatz quantum circuits. However, current quantum computers are limited by their qubit count, connectivity, and noise. This is particularly restrictive when considering optimization problems beyond the quadratic order. Here, we introduce Ansätze based on an approximate quadratization of high-order Hamiltonians that do not incur a qubit overhead. The price paid is a loss in the quality of the noiseless solution. Crucially, these approximations yield shallower Ansätze that are more robust to noise than the standard Quantum Approximate Optimization Algorithm one. We show this through simulations with variable noise strengths. Furthermore, we also propose a noise-aware Ansatz design method for quadratic optimization problems. This method implements only a portion of the target Hamiltonian by limiting the number of layers of gates in the Ansatz. We find that for both problem types, under noise, our approximate implementation of the full problem structure can significantly enhance the solution quality. Our work opens a path to enhance the solution quality that approximate quantum optimization achieves on noisy hardware.