Giulia Meuli (Ecole Polytechnique Fédérale de Lausanne), Mathias Soeken (Ecole Polytechnique Fédérale de Lausanne), Martin Roetteler (Microsoft), Giovanni De Micheli (Ecole Polytechnique Fédérale de Lausanne)

We present a completely automatic synthesis framework for oracle functions—a central part in many quantum algorithms. 

The proposed framework for resource-constrained oracle synthesis ROS is a LUT-based hierarchical method in which every step is specifically tailored to address hardware resource constraints.

ROS embeds a LUT mapper designed to simplify the successive synthesis steps, costing each LUT according to the resources used by its corresponding quantum circuit. 

In addition, the framework exploits a SAT-based quantum garbage management technique. 

Those two characteristics give ROS the ability to beat the state-of-the-art hierarchical method both in number of qubits and in number of operations.
The efficiency of the framework is demonstrated by synthesizing quantum oracles for the Grover’s algorithm.