  We present a multi-step quantum algorithm for solving the $3$-bit exact cover
problem, which is one of the NP-complete problems. Unlike the brute force
methods have been tried before, in this algorithm, we showed that by applying
the clauses of the Boolean formula sequentially and introducing non-unitary
operations, the state that satisfies all of the clauses can be projected out
from an equal superposition of all computational basis states step by step, and
the search space is reduced exponentially. The runtime of the algorithm is
proportional to the number of clauses, therefore scales polynomial to the size
of the problem. Our results indicate that quantum computers may be able to
outperform classical computers in solving NP-complete problems.
