Fast Template Matching for Quantum Circuits Using Hypergraph
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.
Versions
Related
- Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
- Random Quantum Circuits Beyond Moment Matching
- Neural-network-assisted binary template optimization for online pattern matching of the STCF main drift chamber
- Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes
- Three-uniform edge-ordered hypergraph quantum states: entanglement and its relation to hypergraph properties
BibTeX
@misc{hong2026fast,
title = {{Fast Template Matching for Quantum Circuits Using Hypergraph}},
author = {Xin Hong and Jintao Yu and Runhong He and Shenggang Ying and Sanjiang Li and Mingsheng Ying},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29095},
eprint = {2610.29095},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29095},
}
RIS
TY - UNPB
TI - Fast Template Matching for Quantum Circuits Using Hypergraph
AU - Xin Hong
AU - Jintao Yu
AU - Runhong He
AU - Shenggang Ying
AU - Sanjiang Li
AU - Mingsheng Ying
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29095
UR - https://arxiv.org/abs/2610.29095
AB - 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.
ER -