Solving Satisfiability Problems by the Ground-State Quantum Computer

Abstract

A quantum algorithm is proposed to solve the Satisfiability problems by the ground-state quantum computer. The scale of the energy gap of the ground-state quantum computer is analyzed for the 3-bit Exact Cover problem. The time cost of this algorithm on the general SAT problems is discussed.

Extended version of quant-ph/0411194. 8 pages, 7 figures

References in corpus (3)

• Relaxation and Metastability in the RandomWalkSAT search procedure
• Mimicking Time Evolution within a Quantum Ground State: Ground-State Quantum Computation, Cloning, and Teleportation
• Efficiency of Ground State Quantum Computer

Cited by in corpus (4)

• Adiabatic Quantum Computing
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• The Phase Transition in Exact Cover
• Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer