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.
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 execution of quantum algorithms requires two key considerations. On the one hand, it should meet the connectivity constraint requirements of quantum circuit mapping for quantum architectures, and on the other hand, it needs to consider reducing the probability of errors in the execution of quantum circuits as much as possible. This paper proposes a novel optimization technique based on template matching that to satisfy both requirements. The template matching optimization method can significantly reduce the number of gates in a quantum circuit and further enhance its practicality. It stands as advanced optimization technology available today. Our method optimizes quantum logic circuits mapped onto quantum architecture by initially selecting their linear substructure. We then zone the circuit according to the gate dependency graph and optimize each block through template matching. Finally, we reorganize the circuit to obtain the optimized version as the final result. Our proposed method is amenable to various quantum architectures. To evaluate its efficacy, we conduct a comparative analysis with the t|ket⟩ and Qiskit compiler using a set of benchmark test circuits. Specifically, compare to the t|ket⟩ compiler method, the highest average optimization rate of our method can reach 25.75%. Compare with the Qiskit compiler method, the highest average optimization rate can reach 32.72%. Overall, our approach has significant optimization advantages.
The growing variety of quantum hardware technologies, each with unique peculiarities such as connectivity and native gate sets, creates challenges when selecting the best platform for executing a specific quantum circuit. This selection process usually involves a brute-force approach: compiling the circuit on various devices and evaluating performance based on factors such as circuit depth and gate fidelity. However, this method is computationally expensive and does not scale well as the number of available quantum processors increases. In this work, we propose a Graph Neural Network (GNN)based predictor that automates hardware selection by analyzing the Directed Acyclic Graph (DAG) representation of a quantum circuit. Our study evaluates 498 quantum circuits (up to 27 qubits) from the MQT Bench dataset, compiled using Qiskit on four devices: three superconducting quantum processors (IBM-Kyiv, IBM-Brisbane, IBM-Sherbrooke) and one trappedion processor (IONQ-Forte). Performance is estimated using a metric that integrates circuit depth and gate fidelity, resulting in a dataset where 93 circuits are optimally compiled on the trappedion device, while the remaining circuits prefer superconducting platforms. By exploiting graph-based machine learning, our approach avoids extracting the circuit features for the model evaluation but directly embeds it as a graph, significantly accelerating the optimal target decision-making process and maintaining all the information. Experimental results prove94.4%accuracy and an85.5%F1 score for the minority class, effectively predicting the best compilation target. The developed code is publicly available on GitHub (https://github.com/antotu/GNN-Model-Quantum-Predictor).
Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern , in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically 1 that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.
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 circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.
The current noisy intermediate-scale quantum (NISQ) era is characterized by substantial errors and noise, which limit the practical feasibility of deep, many-qubit circuits. To address these constraints, quantum circuit cutting has emerged as a promising tool. Recently, there has been significant research on methods for performing such cutting effectively. In this work, the duality between quantum circuits and classical graphs - specifically, directed acyclic graphs (dags) - is leveraged to analyze the complexity of finding an optimal circuit-cutting configuration that minimizes the number of cuts. After developing a rigorous graph-theoretic framework, the complexity of identifying cut locations that partition a given quantum circuit into smaller fragments is characterized. The corresponding graph-combinatorial task is then defined, and the resulting partition problem is shown to be NP-complete. Furthermore, even a simplified version of the problem, restricted to circuits composed only of one- and two-qubit gates, is shown to be NP-complete. Finally, based on these constraints, an algorithm grounded in satisfiability modulo theories (SMT) is proposed to find optimal cuts when the number of qubits per partition is bounded. This work therefore provides a complexity-theoretic characterization of cut placement and a practical solver for bounded-size decompositions.