ROS: Resource-constrained Oracle Synthesis for Quantum Computers

Abstract

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 Grover's algorithm.

arXiv commentIn Proceedings QPL 2019, arXiv:2004.14750

References in corpus (8)

• Real-time dynamics of lattice gauge theories with a few-qubit quantum computer
• Scalable Quantum Simulation of Molecular Energies
• Demonstration of a small programmable quantum computer with atomic qubits
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• On the CNOT-complexity of CNOT-PHASE circuits
• Programmable networks for quantum algorithms