Quantum computing has transformative computational power to make classically intractable computing feasible. As the algorithms that achieve practical quantum advantage are beyond manual tuning, quantum circuit optimization has become extremely important and integrated into today's quantum software stack. This paper focuses on a critical type of quantum circuit optimization - phase-polynomial optimization. Phase polynomials represents a class of building-block circuits that appear frequently in quantum modular exponentials (the most time-consuming component in Shor's factoring algorithm), in quantum approximation optimization algorithms (QAOA), and in Hamiltonian simulations. Compared to prior work on phase polynomials, we focus more on the impact of phase polynomial synthesis in the context of whole-circuit optimization, from single-block phase polynomials to multiple block phase polynomials, from greedy equivalent sub-circuit replacement strategies to a systematic parity matrix optimization approach, and from hardware-oblivious logical circuit optimization to potential hardware and fault-tolerant friendly circuit optimization. Our experiments demonstrate improvements of up to 48.58 % with an average total gate reduction of 35.83%-and reductions in the CNOT gate count of up to 40.63%, averaging 27.9%, for logical circuits across a representative set of important benchmarks.
Quantum computing has transformative computational power to make classically intractable computing feasible. As the algorithms that achieve practical quantum advantage are beyond manual tuning, quantum circuit optimization has become extremely important and integrated into today's quantum software stack. This paper focuses on a critical type of quantum circuit optimization - phase-polynomial optimization. Phase polynomials represents a class of building-block circuits that appear frequently in quantum modular exponentials (the most time-consuming component in Shor's factoring algorithm), in quantum approximation optimization algorithms (QAOA), and in Hamiltonian simulations. Compared to prior work on phase polynomials, we focus more on the impact of phase polynomial synthesis in the context of whole-circuit optimization, from single-block phase polynomials to multiple block phase polynomials, from greedy equivalent sub-circuit replacement strategies to a systematic parity matrix optimization approach, and from hardware-oblivious logical circuit optimization to potential hardware and fault-tolerant friendly circuit optimization. Our experiments demonstrate improvements of up to 48.58 % with an average total gate reduction of 35.83%-and reductions in the CNOT gate count of up to 40.63%, averaging 27.9%, for logical circuits across a representative set of important benchmarks.
Quantum circuits on resource-limited hardware require optimizing regions dominated by {CNOT,Rz}, 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 {CNOT,Rz} 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.
Blocks composed of {CNOT, Rz} are ubiquitous in modern quantum applications, notably in circuits such as QAOA ansatzes and quantum adders. After compilation, many of them exhibit large CNOT counts or depths, which lowers fidelity. Therefore, we introduce HOPPS: a SAT-based hardware-aware optimal phase polynomial synthesis algorithm that could generate {CNOT, Rz} blocks with CNOT count or depth optimality.
Sometime {CNOT, Rz} blocks are large, such as in QAOA ansatzes, HOPPS's pursuit of optimality limits its scalability. To address this issue, we introduce an iterative blockwise optimization strategy: large circuits are partitioned into smaller blocks, each block is optimally refined, and the process is repeated for several iterations.
Empirical results show that HOPPS is more efficient comparing with existing near optimal synthesis tools. Used as a peephole optimizer, HOPPS reduces the CNOT count by up to 50.0% and the CNOT depth by up to 57.1% under OLSQ. For large QAOA circuit, after mapping by Qiskit, circuit can be reduced CNOT count and depth by up to 44.4% and 42.4% by our iterative blockwise optimization. Index Terms-Phase Polynomial, Quantum Circuit Synthesis, Quantum Circuit Optimization.
In the NISQ era, where quantum computing is dominated by hybrid quantum algorithms, it is important for quantum circuits to be well-optimized to reduce noise from unnecessary gates. We investigate different phase polynomial-based compilation strategies to determine the current best practices and compare them against the DAG-based Qiskit and TKET compilers. We find that phase polynomial-based compiling is very fast compared to DAG-based compiling. For long circuits, these compilers generate fewer CNOT gates than Qiskit or TKET, but for short circuits, they are quite inefficient. We also show that supplementary algorithms such as Reverse Traversal and simulated annealing mightimprove the generated CNOT count slightly, but the effect is negligible in most settings and generally not worth the additional compiler runtime. Instead, more sophisticated phase polynomial synthesis algorithms are needed.
Quantum circuit optimization - the process of transforming a quantum circuit into an equivalent one with reduced time and space requirements - is crucial for maximizing the utility of current and near-future quantum devices. While most automated optimization techniques focus on transforming circuits into equivalent ones that implement the same unitary, we show that substantial new opportunities for resource reduction can be achieved by (1) allowing approximate local transformations and (2) employing mixed quantum channels to approximate pure circuits. Our novel automated protocol for approximate circuit rewriting is a refined evolution of automated optimization techniques based on the ZX-calculus, where we add a greedy strategy that selectively replaces ZX-diagrams with small phase angles with stochastic mixtures of the identity and carefully chosen over-rotations, which are designed to reduce the overall gate count in expectation while staying within a strict error budget. This approach yields modest two-qubit gate count reduction in random quantum circuits, and achieves a substantial reduction in structured circuits such as the quantum Fourier transform. Fundamentally, our protocol converts experimental noise due to gate applications into deliberately engineered random noise, outperforming many other approximation methods on average. These results highlight the potential of mixed-channel approximations to enhance future quantum circuit performance, suggesting new directions for resource-aware automated quantum compilation beyond pure unitary channels.
Blocks composed of {CNOT, Rz} are ubiquitous in modern quantum applications, notably in circuits such as QAOA ansatzes and quantum adders. After compilation, many of them exhibit large CNOT counts or depths, which lowers fidelity. Therefore, we introduce HOPPS: a SAT-based hardware-aware optimal phase polynomial synthesis algorithm that could generate {CNOT, Rz} blocks with CNOT count or depth optimality. Sometime {CNOT, Rz} blocks are large, such as in QAOA ansatzes, HOPPS's pursuit of optimality limits its scalability. To address this issue, we introduce an iterative blockwise optimization strategy: large circuits are partitioned into smaller blocks, each block is optimally refined, and the process is repeated for several iterations. Empirical results show that HOPPS is more efficient comparing with existing near-optimal synthesis tools. Used as a peephole optimizer, HOPPS reduces the CNOT count by up to 50.0 % and the CNOT depth by up to 57.1 % under OLSQ. For large QAOA circuit, after mapping by Qiskit, circuit can be reduced CNOT count and depth by up to 44.4 % and 42.4 % by our iterative blockwise optimization.
The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.