A Divide-And-Conquer Pebbling Strategy for Oracle Synthesis in Quantum Computing

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.