Resource constrained oracle synthesis for quantum circuits

Daniele Cuomo

Giulia Meuli, Mathias Soeken, Martin Roetteler +1 more

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.

Rafael Pereira da Silva

Mariam Zomorodi Moghadam, Mohammad Amin Taherkhani, Keivan Navi

Kezhen Zhang, Riling Li, Mingsheng Ying

Quantum oracles are quantum circuits that implement classical Boolean functions, frequently used as independent black boxes in quantum algorithm design. The hierarchical reversible logic synthesis approach, a scalable method for large-scale oracle synthesis, relies on ancilla qubits to store intermediate results. The sequence in which these results are computed and uncomputed, governed by the reversible pebble game, greatly affects both qubit usage and circuit gate count. This paper introduces a novel divide-and-conquer pebbling strategy that reduces qubit count while maintaining a reasonable circuit gate count. Experimental results show up to a 90% reduction in qubits compared to the most commonly-used strategy, with an average increase of 3 to 4 times in quantum operations, all achieved within a reasonable runtime. In qubit-constrained tasks, our method achieves over 90% reduction in T-count. Additionally, we have incorporated our strategy into the hierarchical synthesis method and implemented it as a potential synthesizer for Qiskit, with experiments demonstrating that it outperforms the default synthesizer. The proposed approach shows promise in optimizing both qubit usage and circuit gate count for large-scale oracle synthesis problems.

Shuai Yang, Wei Zi, Bujiao Wu +3 more

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an$m$-clause SAT-oracle necessitates$2m-1$ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to$\tilde {O}(\log m)$using$m$ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.