Quantum exact optimisation of MAX-2-SAT

"A Short Path Quantum Algorithm for Exact Optimization"

Published by Matthew B. Hastings (Microsoft), 26th February 2018

NISQ algorithms
Quantum exact optimisation of MAX-2-SAT

Qu&Co comments on this publication:

In this paper, Matthew Hastings presents a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT.  While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian.