Optimizing Quantum Circuit Synthesis with Dominator Analysis

Quantum circuit synthesis translates a classical Boolean function into an equivalent quantum circuit. The synthesis is solvable by playing the reversible pebble game on the logic network of the function. However, optimal solutions are impractical for large networks, affecting the number of qubits and gates of the final quantum circuit. In this work, we improve the solution of the reversible pebble game by leveraging dominance relations on the directed acyclic graph of the classical function, reducing qubits needed for syntheses. The proposed algorithm exposes a tunable tradeoff between the available number of qubits and the circuit size expressed as T-count and T-depth. We experimentally validate our methodology on cryptographic and arithmetic benchmarks, reporting reductions between 37% and 83% in qubit number with respect to Bennet syntheses algorithms and complete the majority of our syntheses in less than a second, improving on the current running times of state of the art approaches.