Leveraging Phase Polynomials for Quantum Circuit Optimization

Abstract

Quantum circuits on resource-limited hardware require optimizing regions dominated by $\{\mathrm{CNOT},R_z\}$, which account for a large fraction of operations and often dominate execution cost. This optimization can be challenging because phase-polynomial blocks are fragmented by basis-changing gates such as $H$, and optimizing phase parities alone may increase the cost of downstream basis transformations. Existing phase-polynomial approaches are limited to single-block or phase-only optimization, while subcircuit rewriting approaches are local and scale poorly beyond small rewrite windows. We introduce \emph{PhasePoly}, a compiler optimization pass that jointly optimizes phase-parity and output-parity networks and employs a cross-block intermediate representation to reuse parities across phase-polynomial block barriers. This approach is effective because its unified parity-matrix representation exposes long-range $\{\mathrm{CNOT},R_z\}$ structure that local rewriting and single-block methods cannot capture. \emph{PhasePoly} reduces total gate count by up to 50.00\% (34.70\% on average) and CNOT count by up to 48.57\% (26.83\% on average), while scaling to large circuits and improving both fault-tolerant compilation and near-term hardware execution. \emph{PhasePoly} is available at https://github.com/ruadapt/PhasePoly.

To appear in ISCA 2026