  We consider classical and quantum algorithms which have a duality property:
roughly, either the algorithm provides some nontrivial improvement over random
or there exist many solutions which are significantly worse than random. This
enables one to give guarantees that the algorithm will find such a nontrivial
improvement: if few solutions exist which are much worse than random, then a
nontrivial improvement is guaranteed. The quantum algorithm is based on a
sudden of a Hamiltonian; while the algorithm is general, we analyze it in the
specific context of MAX-$K$-LIN$2$, for both even and odd $K$. The classical
algorithm is a "dequantization of this algorithm", obtaining the same guarantee
(indeed, some results which are only conjectured in the quantum case can be
proven here); however, the quantum point of view helps in analyzing the
performance of the classical algorithm and might in some cases perform better.
