ROS: Resource-constrained Oracle Synthesis for Quantum Computers

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.