  We give a general method of construting quantum circuit for random
\QTR{it}{satisfiability} (SAT) problems with the basic logic gates such as
multi-qubit controlled-NOT and NOT gates. The sizes of these circuits are
almost the same as the sizes of the SAT formulas. Further, a parallelization
scheme is described to solve random SAT problems efficiently through these
quantum circuits in \QTR{it}{nuclear magnetic resonance} (NMR) ensemble quantum
computing. This scheme exploits truly mixed states as input states rather than
pseudo-pure states, and combines with the topological nanture of the NMR
spectrum to identify the solutions to SAT problems in a parallel way. Several
typical SAT problems have been experimentally demonstrated by this scheme with
good performances.
