US Patent 11669763 Quantum procedures for approximate optimization by quenching

In this disclosure, example quantum algorithms for approximate optimization based on a sudden quench of a Hamiltonian. While the algorithm is general, it is analyzed in this disclosure in the specific context of MAX-EK-LIN2, for both even and odd K. It is to be understood, however, that the algorithm can be generalized to other contexts. A duality can be found: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. A classical approximation algorithm is then analyzed and a similar duality is found, though the quantum algorithm provides additional guarantees in certain cases.