  To demonstrate the advantage of quantum computation, many attempts have been
made to attack classically intractable problems, such as the satisfiability
problem (SAT), with quantum computer. To use quantum algorithms to solve these
NP-hard problems, a quantum oracle with quantum circuit implementation is
usually required. In this manuscript, we first introduce a novel algorithm to
synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared
with linear ancillary qubits in the implementation of Qiskit open-source
framework, our algorithm can synthesize an m clauses n variables k-CNF with
$O(k^2 m^2/n)$ quantum gates by only using three ancillary qubits. Both the
size and depth of the circuit can be further compressed with the increase in
the number of ancillary qubits. When the number of ancillary qubits is
$\Omega(m^\epsilon)$ (for any $\epsilon > 0$), the size of the quantum circuit
given by the algorithm is O(km), which is asymptotically optimal. Furthermore,
we design another algorithm to optimize the depth of the quantum circuit with
only a small increase in the size of the quantum circuit. Experiments show that
our algorithms have great improvement in size and depth compared with the
previous algorithms.
