Improving Quantum Optimization Algorithms by Constraint Relaxation

Quantum optimization is a significant area of quantum computing with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational Hamiltonian-based algorithms, struggle on present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning but often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for the Quantum Approximate Optimization Algorithm to satisfy all the requirements that correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities of measuring solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in linear number of entangleming gates instead of exponential and superior performance compared to standard formulations. Specifically, we achieve higher probabilities of measuring feasible solutions in 9 out of 9 instances compared to standard Hamiltonian formulations and surpass quadratic programming formulations known from quantum annealers in 7 out of 9 instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future.