A Short Path Quantum Algorithm for Exact Optimization
A Short Path Quantum Algorithm for Exact Optimization
We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi></mml:math>; this problem is called weighted MAX-E<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi></mml:math>-LIN2. We require …