Efficient quantum circuit synthesis for SAT-oracle with limited ancillary qubit

Understand

How to implement quantum oracle with limited resources raises concerns these days.

• We design two ancilla-adjustable and efficient algorithms to synthesize SAT-oracle, the key component in solving SAT problems.
• The previous work takes 2m-1 ancillary qubits and O(m) elementary gates to synthesize an m clauses oracle.
• The first algorithm reduces the number of ancillary qubits to 2\sqrt{m}, with at most an eightfold increase in circuit size.