1206.4747 (Hefeng Wang et al.)

A quantum algorithm for solving the 3-SAT problem    [PDF]

Hefeng Wang, Fuli Li

When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm to solve the 3-SAT problem, which is an NP-complete problem and there is no efficient algorithm that has been found for solving it. We show that on a quantum computer, the number of qubits increases linearly with the size of the 3-SAT problem, while the efficiency of the algorithm is independent of the size of the problem. Our results indicate that quantum computers may be able to outperform classical computers in solving NP-complete problems.

View original: http://arxiv.org/abs/1206.4747