Fast Template Matching for Quantum Circuits Using Hypergraph

AI summary

Overview

Research area: Quantum computing — quantum circuit compilation and optimization (quantum computer-aided design / EDA), specifically template-based circuit simplification.

Technical level: Intermediate. The paper assumes familiarity with quantum gates, unitary equivalence, and graph/subgraph isomorphism, but its central idea (replacing a DAG with a hypergraph) is explained with a worked example.

Scope in one sentence: The paper introduces a hypergraph representation of quantum circuits that preserves gate-level connectivity and locality while remaining invariant under gate commutation, and uses it to speed up template matching by 11–606× over Qiskit's DAG-based matcher without losing optimization quality.

What This Paper Is About

Template matching simplifies a quantum circuit by finding fragments that match a known identity "template" and replacing the expensive part with the cheaper inverse remainder. The hard part is doing this while respecting that many quantum gates commute, so the same circuit can be written in many equivalent orderings. The state-of-the-art approach encodes the circuit as a DAG that is blind to commutation, but in doing so it throws away edges between commuting gates, which destroys the circuit's connectivity and forces the matcher to search globally; this paper proposes a hypergraph that keeps those gates grouped without discarding structure.

Key Contributions

1. A hypergraph representation (HG) of quantum circuits in which commuting gates on the same qubit are collapsed into a single "super-node" annotated with an algebraic fingerprint (the gates' eigen-directions on that qubit), rather than deleting the edges between them as the DAG approach does.
2. A canonicity theorem (Theorem 1): for circuits composed solely of multi-controlled single-target gates, two circuits are equivalent under gate commutation if and only if their hypergraph representations are isomorphic — so the representation can be used for matching without enumerating gate permutations.
3. A template-matching algorithm over hypergraphs using exhaustive depth-first search with three incrementally maintained partial mappings (matched nodes, matched qubits, matched gates) and three feasibility rules: node consistency, qubit consistency, and gate adjacency.
4. An experimental demonstration of 11–606× speed-up over the DAG-based matcher in Qiskit on random circuits, arithmetic benchmarks, and a scalability study, with construction cost reduced from O(n_C|C|²) to O(n_C|C|) and matching complexity from O(|C|^(|T|+3)|T|^(|T|+4)n_C^(n_T−1)) to O(|C|^(|T|+1)|T|^(|T|)n_C²).

Main Findings

• Speed-up range: HG achieves 11–606× speed-up over the DAG-based implementation in Qiskit on random and arithmetic benchmarks, while the paper reports the same optimization quality.
• Random circuits (10 qubits, gate set {X, CX, CCX}, 24 templates of ≤8 gates): 15–65× faster than Qiskit and 11–29× faster than Qiskit with heuristics enabled. For 100 gates, HG took 1.75 s versus 27.64 s (Qiskit) and 18.97 s (Qiskit-heur), with final gate counts of 73, 73, and 75 respectively.
• Largest random instance (700 gates): HG finished in 20.26 s with 550 gates, versus 1321.91 s (549 gates) for Qiskit and 587.15 s (556 gates) for Qiskit-heur.
• Largest arithmetic instance (gf2^E16_mult, 2707 initial gates, 48 qubits): HG finished in 20.99 s versus 12 737.50 s for Qiskit — the source of the headline 606× figure. The table lists 2599 final gates for HG and 2617 for Qiskit, although the text states both stop at the same fixed point.
• Arithmetic suite overall: the HG matcher uses "two orders of magnitude less time"; for example, gf2^E10_mult drops from 1322.18 s to 9.95 s and qcla_adder_10 from 143.27 s to 0.91 s.
• Gate-count parity: most arithmetic results are identical between the two matchers (e.g., csla_mux_3 at 153, csum_mux_9 at 266, mod_mult_55 at 91); a few differ slightly (adder_8: 601 vs 598; vbe_adder_3: 86 vs 82; qcla_mod_7: 613 vs 612).
• Scalability (6-qubit random circuits, 10–250 gates, 15 instances per point): the quadratic fit is y = 3.75×10⁻⁷x² + 5.04×10⁻⁴x + 1.55×10⁻³, described as essentially linear in the observed range, staying below 200 ms even for the largest circuits. The corresponding DAG fit (taken from the prior work) is y = 6.8×10⁻⁵x² + 1.26×10⁻³x + 8.84×10⁻³.
• Acceleration grows with circuit size, which the authors attribute to preserving locality and connectivity rather than to any heuristic.

Methodology in Plain English

The authors start from a simple observation about the existing DAG encoding: when two gates on the same qubit commute, the DAG draws no edge between them, so the circuit shatters into loosely connected pieces and the matcher has to hunt across the whole circuit for the next gate to match.

Their fix is to merge instead of delete. For every gate, they compute its eigen-directions on each qubit it touches — an "algebraic fingerprint" that determines what it can commute past. Scanning the circuit gate by gate, if a gate's fingerprint on a qubit matches the most recently built super-node on that qubit, the gate is absorbed into that node; otherwise a new super-node is created and linked to the previous one, so each qubit wire remains an unbroken directed chain. Multi-qubit gates become hyperedges connecting the nodes that contain them.

Template matching then becomes subgraph isomorphism on this structure. For each starting node in the circuit hypergraph, the algorithm tries to pair it with a node in the template hypergraph having the same fingerprint, then recursively extends the match to neighbouring gates, accepting a pairing only if it does not conflict with already-matched nodes or qubits and if the newly matched gate is not separated from the matched region by unmatched gates. Every branch is explored, and the largest match found is kept. If more than half the template's gates are matched, the matched segment is replaced by the inverse of the template's remaining gates — a strictly smaller, functionally equivalent circuit.

Why This Matters

Impact on research. The paper reframes the central difficulty of template matching: it is not only about handling commutation, but about handling it without destroying locality. Showing that a representation can be simultaneously commutation-invariant and connectivity-preserving, with a canonicity proof for multi-controlled single-target gates, gives compiler designers a new structural primitive and a cleaner complexity profile than the DAG formulation.

Real-world applications (potential, as motivated by the paper's benchmark suite):

• Compiling arithmetic circuits (adders, multipliers, modular arithmetic) that underpin Shor-style factoring and other cryptographic algorithms.
• Reducing gate count and depth for NISQ devices, where qubit count, connectivity, and coherence time are severely constrained.
• Front-end simplification passes in quantum compiler toolchains, before routing and scheduling.
• Repeated simplification as a fixed-point pass over already-optimized circuits, as done on the benchmarks inherited from Nam et al.

Industry relevance. The work is published at DAC '26 and evaluated against the matcher shipped in Qiskit, the most widely used open-source quantum SDK. A 606× reduction in compile time on a 48-qubit, 2707-gate circuit is the kind of change that makes a pass practical inside a production compiler rather than an offline experiment.

Future Directions

1. Broadening the canonicity guarantee. Theorem 1 is proved only for multi-controlled single-target gates; extending it to general gate sets (arbitrary unitaries, parameterized rotations) is the obvious open question.
2. Scaling the template library. The experiments deliberately exclude Qiskit's 9-gate templates; the authors note that including them would widen the gap further, but the effect on matching complexity at larger |T| is untested.
3. Hardware-aware optimization. The current objective is gate count; incorporating device topology, fidelity, and depth costs into the matching search is not addressed.
4. Tighter complexity bounds and parallelism. The reported bound for the HG matcher is still exponential in |T|, leaving room for pruning strategies, better orderings, or parallel exploration of the search tree.

Target Audience

Quantum compiler and EDA researchers, graduate students working on circuit optimization, and engineers integrating optimization passes into quantum SDKs (Qiskit, tket, and similar). Readers who only want the practical takeaway can focus on the benchmark tables; those interested in the representation theory should read the canonicity proof and the worked example in Section 5.

Authors’ abstract

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.