Quantum Algorithm for Solving an NP-Complete Problem

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 for solving a specific NP-complete problem, the 3-bit Exact Cover problem, EC3. We show that on a quantum computer, the number of qubits increases linearly with the size of the EC3 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.