Pattern Tree: Enhancing Efficiency in Quantum Circuit Optimization Based on Pattern-matching
Authors:
- Mingyu ChenMCMingyu Chen
- Yu ZhangYZYu Zhang
- Zhaoyu ZhengZZZhaoyu Zheng
- Yongshang LiYLYongshang Li
- Haoning DengHDHaoning Deng
Preprint
Abstract
Quantum circuit optimization is essential for improving the performance of quantum algorithms, particularly on Noisy Intermediate-Scale Quantum (NISQ) devices with limited qubit connectivity and high error rates. Pattern matching has proven to be an effective technique for identifying and optimizing subcircuits by replacing them with functionally equivalent, efficient versions, including reducing circuit depth and facilitating platform portability. However, existing approaches face challenges in handling large-scale circuits and numerous transformation rules, often leading to redundant matches and increased compilation time. In this study, we propose a novel framework for quantum circuit optimization based on pattern matching to enhance its efficiency. Observing redundancy in applying existing transformation rules, our method employs a pattern tree structure to organize these rules, reducing redundant operations during the execution of the pattern-matching algorithm and improving matching efficiency. We design and implement a compilation framework to demonstrate the practicality of the pattern tree approach. Experimental results show that pattern-tree-based pattern matching can reduce execution time by an average of 20% on a well-accepted benchmark set. Furthermore, we analyze how to build a pattern tree to maximize the optimization of compilation time. The evaluation results demonstrate that our approach has the potential to optimize compilation time by 90%.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Quarl: A Learning-Based Quantum Circuit OptimizerProceedings of the ACM on Programming Languages, 2024
- Source Matching and Rewriting for MLIR Using String-Based AutomataACM Transactions on Architecture and Code Optimization, 2023
- The Variational Quantum Eigensolver: A review of methods and best practicesPhysics Reports, 2022
- QIRO: A Static Single Assignment-based Quantum Program Representation for OptimizationACM Transactions on Quantum Computing, 2022
- Exact and Practical Pattern Matching for Quantum Circuit OptimizationACM Transactions on Quantum Computing, 2022
- Strong Quantum Computational Advantage Using a Superconducting Quantum ProcessorPhysical Review Letters, 2021
- t|ket⟩: a retargetable compiler for NISQ devicesQuantum Science and Technology, 2020
- Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimizationPhysical Review A, 2016