Leveraging Phase Polynomials for Quantum Circuit Optimization

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 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. 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. PhasePoly is available at https://github.com/ruadapt/PhasePoly.