Optimizing a quantum circuit is hard because it requires exploring a vast space of functionally equivalent circuits, produced by applying local circuit rewrites such as gate cancellation and commutation. Each additional rewrite can exponentially expand the space of equivalent circuits, so existing optimizers can only explore a tiny fraction of this space and often produce suboptimal results. We present Quasar , a new quantum circuit optimizer that can generate a step-limited optimal circuit: given a bound on rewrite iterations, it returns the lowest-cost circuit reachable within that bound. To achieve this, Quasar constructs two complementary e-graphs for the quantum circuit’s graph and sequence representations. Quasar then infers an atomic rewrite set for application on both e-graphs, which improves optimization performance by orders of magnitude. Finally, Quasar employs a series of new optimization techniques to ensure both soundness and scalability of equality saturation on quantum circuits. Across standard benchmarks, Quasar achieves geometric-mean reductions of 20.2% in 2-qubit gate count, 33.5% in total gate count, and 24.2% in circuit depth, and a 21.4% fidelity improvement over unoptimized circuits, outperforming or matching state-of-the-art rewrite-based optimizers on 75%, 92%, 62%, and 80% of circuits, respectively.
Optimizing a quantum circuit is hard because it requires exploring a vast space of functionally equivalent circuits, produced by applying local circuit rewrites such as gate cancellation and commutation. Each additional rewrite can exponentially expand the space of equivalent circuits, so existing optimizers can only explore a tiny fraction of this space and often produce suboptimal results. We present Quasar , a new quantum circuit optimizer that can generate a step-limited optimal circuit: given a bound on rewrite iterations, it returns the lowest-cost circuit reachable within that bound. To achieve this, Quasar constructs two complementary e-graphs for the quantum circuit’s graph and sequence representations. Quasar then infers an atomic rewrite set for application on both e-graphs, which improves optimization performance by orders of magnitude. Finally, Quasar employs a series of new optimization techniques to ensure both soundness and scalability of equality saturation on quantum circuits. Across standard benchmarks, Quasar achieves geometric-mean reductions of 20.2% in 2-qubit gate count, 33.5% in total gate count, and 24.2% in circuit depth, and a 21.4% fidelity improvement over unoptimized circuits, outperforming or matching state-of-the-art rewrite-based optimizers on 75%, 92%, 62%, and 80% of circuits, respectively.
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.
Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such asRx(θ1)⋅Rx(θ2), are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelityF≥0.99. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such aseiπ/4are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.
Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances of quantum computing hardware, the practical use of NISQ era devices remains severely limited due to resources constraints (e.g., noise, qubits, gates, circuit depth, and coherence time). QC optimization is an essential mitigation strategy to enable the execution of quantum programs on restricted quantum devices. In this context, ZX-calculus emerged as an alternative to conventional gate-level QC optimization approaches. Instead of depending upon gate set specific rewriting rules, it offers a compact, universal and semantics-preserving framework for QC optimization. However, ZX-based QC optimization faces two challenges in practice. On the one hand, ZX-calculus admits a non-terminating rewriting system. On the other hand, ZX-diagrams lose causality. As a consequence, only a subset of ZX-diagrams that preserve CFlow, GFlow or Pauli flow allow for the extraction of QCs in polynomial-time. The first challenge can be addressed by effective heuristics, search algorithms and pruning conditions while the latter is an optimization problem with an upper bound of NPNP#P, where the choice of the extraction algorithm can negate ZX-diagram level improvements. This thesis establishes a ZX-based end-to-end pipeline for QC optimization that leverages tree search for metric-agnostic ZX-diagram optimization and \gls{ilp} paired with backtracking search to improve the circuit extraction step. The contributions of this thesis are four-fold: (i) First, it presents a comprehensive survey of ZX-based QC optimization, categorizing them by the employed optimization strategy, the target metric, and the intended quantum computing architecture. (ii) Second, this work formalizes the ZX-diagram optimization problem as the explicit state-space exploration of rewriting rule sequences. (iii) Thirdly, the formal approach is put into practice by implementing tree search algorithms, in particular DFS, IDDFS, and LDS, to reduce the T-gate, and Edge count of ZX-diagrams. Furthermore, the efficacy of different pruning conditions are investigated. Lastly, the novel Local-Elimination (LE) is introduced as a metaheuristic to select growing sub ZX-diagrams around a target spider. Instead of performing tree search optimization on intractable large ZX-diagrams, LE changes one large optimization problem into a sequence of tractable small searches. All tree search strategies are extensively tested on benchmark data sets that contain different QC types. (iv) Finally, this work enhances two-qubit gate count during circuit extraction by introducing an ILP model that replaces the Gaussian Elimination steps present in current circuit extraction algorithms. Pairing the ILP model for circuit extraction with backtracking allows the exploration of multiple solutions that take advantage of gate commutation and cancellation rules during extraction. The last research artifact of this thesis is the introduction of \emph{ZX-benchmark}, a declarative end-to-end optimization pipeline and ZX benchmarking framework to compare different optimization and extraction algorithms on the same data sets and under comparable experimental conditions. To this end, it offers access to multiple data sets, and various third-party optimizers. With the intent to offer a framework that is useful beyond the scope of this thesis, the framework provides support of configuration files and a unified API to declare experiments. All artifacts produced are in the form of plain text formats (JSON, and OpenQASM). In summary, the thesis advances ZX-based compilation by connecting metric-agnostic diagram rewriting with extraction-aware optimization in a reusable, end-to-end workflow.
Quantum circuit transformation (QCT), necessary for adapting any quantum circuit to the qubit connectivity constraints of the NISQ device, often introduces numerous additional SWAP gates into the original circuit, increasing the circuit depth and thus reducing the success rate of computation. To minimize the depth of QCT circuits, we propose a Swapping-Sweeping-and-Rewriting optimizer. This optimizer rearranges the circuit based on generalized gate commutation rules via a genetic algorithm, extracts subcircuits consisting of CNOT gates using a circuit sweeping technique, and rewrites each subcircuit with a functionally equivalent and depth-optimal circuit generated by an SAT solver. Experimental results demonstrate that, compared with existing post-QCT optimization approaches such as CBIR and Q-Synth, SSR achieves superior performance, improving circuit depth by up to 29.04% and 16.59% on average across all benchmark circuits, whereas the depth reduction of CBIR and Q-Synth are, respectively, 12.17% and 16.63% at most and 6.45% and -0.53% on average on the same benchmarks.
Quantum circuit optimization is a key step toward the efficient execution of quantum algorithms. Template matching has emerged as one of the dominant approaches for simplifying quantum circuits, yet it confronts the intrinsic challenge of accommodating gate commutativity. The state-of-the-art template-matching algorithm relies on a directed acyclic graph (DAG) representation. While this DAG-based technique handles gate commutativity satisfactorily, it fails to preserve the local connectivity inherent to quantum circuits, thereby leading to relatively high matching complexity.
In this paper, we introduce a hypergraph representation (HG), a commutativity-aware representation that collapses commuting gates into a single super-node while retaining all local connectivity. This enables matches to be extended locally without revisiting the rest of the circuit, with incremental updates limited to the immediate neighborhood. Experimental results demonstrate that our HG matcher achieves 11--606x speed-up over the DAG-based implementation in Qiskit (Iten et al., 2022) on both random and arithmetic benchmarks, while maintaining the same optimization quality. The acceleration increases with circuit size, confirming that preserving locality and connectivity is the key to scalable quantum circuit optimisation.
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.