Solving satisfiability problems by the ground-state quantum computer
Wenjin Mao · Physical Review A · 2005
A quantum algorithm is proposed to solve the satisfiability (SAT) problems by the ground-state quantum computer. The scale of the energy gap of the ground-state quantum computer is analyzed for the $3\text{\ensuremath{-}}\text{bit}$ exact cover problem. The time cost of this algorithm on the general SAT problems is discussed.