Toffoli Gate Rewrite Rules for Quantum Circuit Optimisation
Linh Bui
Abstract
Quantum circuit optimisation is essential for reducing the resource requirements of quantum algorithms, particularly on current noisy and resource-constrained quantum hardware. Since several well-defined quantum circuit optimisation problems are classified as NP-hard, heuristic approaches, such as rewrite rules, are widely adopted. This thesis implements a set of Toffoli gate rewrite rules with an appropriate dependency-check algorithm within Pandora and evaluates their effectiveness on NRSCM and VBE adder circuits ranging from 16 to 2048 bits. The benchmarking results show that the effectiveness of the optimiser using the implemented rewrite rules strongly depends on input circuit structures and the selection of rules. In particular, a 50% reduction in the CNOT gate count was achieved for VBE circuits with an appropriate combination of rules, while NRSCM circuits did not exhibit any meaningful reduction. These results show the potential of the implemented method in reducing gate counts of certain types of quantum circuits with trade-offs in other gate counts. Future work could investigate and improve the current rewrite rule set to increase its effectiveness and enable a broader range of applicable circuits.