REVIEW 3 major objections 7 minor 1 cited by
Pattern Tree: Enhancing Efficiency in Quantum Circuit Optimization Based on Pattern-matching
T0 review · 3 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Organizing quantum rewrite rules into a shared-prefix pattern tree cuts matching time by 20% and can reach 90% on larger rule sets.
desk verdict A credible engineering transfer of prefix-sharing matching to quantum rewrite rules, with a plausible 20% speedup inside the authors' own framework, but the headline 90% claim lacks quality evidence at the operating point where it is achieved. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The pattern tree is an abstract tree whose nodes are circuit patterns and whose edges add one quantum gate to a parent pattern, so the source patterns of transformation rules appear as nodes and shared prefixes appear as shallow nodes. A prefix rule is a special rule whose source is a common prefix and whose target is empty; it is used solely for matching, so a failed prefix match prunes all descendant rules at once, and a successful one hands its matching context to descendants. This machinery is what eliminates redundant feasibility-rule checks during the pattern-matching algorithm.
What would settle it
Run a pattern-matching quantum compiler on a benchmark set with a different rule library and compare wall-clock matching time with and without pattern-tree organization; if the time does not drop, or the optimized circuits change, the central claim is false. More sharply, if feasibility-rule checks are not a dominant cost, the pattern tree will show little benefit.
Extended reading notes
Core claim
The paper's central claim is that transformation-rule redundancy can be made explicit and profitable: if two rules' source circuits have a common gate-sequence prefix, the matcher should match that prefix once and reuse the context, rather than redoing it for each rule. The paper defines circuit precedence, packs common-prefix patterns into prefix rules that never rewrite, and gives a greedy algorithm for choosing which prefixes to add. Under this scheme, failed matches of one rule leave a matching context that the next rule inherits, and rules sharing a prefix are excluded together as soon as a prefix fails. The paper reports a 20% average reduction in pattern-matching execution time on a well-accepted benchmark set with one percent of prefix candidates, and, when about 40% of prefix candidates are added, feasibility-rule checks and compilation time both fall by more than 90% on two benchmark circuits.
Load-bearing premise
The central assumption is that the time spent re-checking the same gate subsequences while trying many similar rewrite rules is a large enough share of compilation time that reusing it speeds up real compilers, not just the authors' prototype.
Editorial extensions
If this is right
- Any pattern-matching quantum compiler that currently uses a flat rule list can adopt the same prefix-sharing organization and should see compilation-time reductions that grow with the number of rules sharing prefixes.
- The optimized circuit produced with a pattern tree is identical to the one produced without it, so users get faster compilation without any change to output quality.
- Because the paper's preprocessing routine is separate, the pattern-tree idea composes with other preprocessing and rewriting strategies rather than replacing them.
- Variational algorithms that recompile circuits every iteration benefit most, since their wall-clock time is dominated by repeated compilation.
- Larger transformation-rule libraries should amplify the effect because more rules mean more shared prefixes and more redundant matching to prune.
Reading between the lines
- A testable extension is to apply the pattern-tree construction to search-based optimizers rather than greedy rule-by-rule matching; if prefix matching dominates there too, similar savings should appear.
- The current prefix-rule selection is heuristic, so a principled optimization of prefix-rule count and placement could turn the 20% average into a predictable bound rather than a tuning parameter.
- The 20% figure is tied to one rule set and one matcher; I would expect the speedup to be larger on rule libraries with more structural redundancy, since the paper's own scaling argument makes the saving roughly proportional to how many rules share prefixes.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes the pattern tree, a trie-like structure (PTree and RTree) that organizes quantum circuit transformation rules by common prefix source patterns, and introduces 'prefix rules' whose source is a common prefix and whose target is empty, used only for feasibility checking. A greedy depth-first scheduler (Algorithm 1) traverses the tree to share matching context and skip rules with a failing prefix. The implementation is built on the authors' QCiR framework with Quartz-generated rules over the Nam gate set. Experiments report that with 8 prefix rules, pattern-matching execution time falls by an average of 20% on a subset of benchmarks shown in Fig. 8(a), and that with roughly 40% of the 845 candidate prefix rules, feasibility checks and compilation time for adder_8 and qcla_mod_7 drop by more than 90%. The paper also reports optimized gate counts versus Qiskit, Quartz, and Nam, and verifies equivalence for benchmarks with fewer than 16 qubits using Qiskit's unitary simulator.
Significance. If the results hold, the pattern tree is a useful engineering contribution to PMT-based quantum compilation: it formalizes a common-prefix redundancy that arises when matching many transformation rules, gives a concrete heuristic (Algorithm 2) for selecting prefix rules, and provides a falsifiable benchmark claim about compilation-time reduction. The paper's use of Quartz-generated rules and Qiskit-based equivalence verification is a strength, as is the explicit ablation of the pattern tree against the same framework without it. However, the headline numbers are currently tied to an internal baseline, an unspecified benchmark subset, and two circuits at the 90% operating point, so the significance of the claims is narrower than the abstract suggests.
major comments (3)
- [§4, Algorithm 1, line 17] Algorithm 1 line 17 reads 'if find and isPrefix(R_f) then Rewrite(C, r, Context)'. Taken literally, this rewrites the circuit whenever the last matched rule is a prefix rule, but Def. 4.1 states that a prefix rule has no feasible target and will not be applied. The condition should presumably be 'if find and not isPrefix(R_f)', or the rewrite should be guarded by checking that the matched rule is an actual transformation rule; otherwise the published pseudocode describes a scheduler that deletes the matched prefix subcircuit, which cannot be what was evaluated. Please correct the pseudocode and make the guard consistent with the definition and with the surrounding text.
- [§5.4, Fig. 9 and Fig. 8(b)] The 90% compilation-time improvement is reported at the point where roughly 40% of the 845 prefix-rule candidates are inserted, but the only evidence that the pattern tree preserves the optimized circuit is for the N=8 setting in §5.3 (Fig. 8(b)). This preservation is not automatic: Algorithm 1 is a greedy depth-first traversal that applies the first successful match, and inserting about 338 prefix nodes changes the order in which rules are first tried relative to the no-prefix baseline. No gate-count, depth, or equivalence data are given for adder_8 and qcla_mod_7 at the 40% operating point, so the 90% result could be accompanied by a different or worse output circuit. Please report output-circuit quality at the operating point used for the 90% claim, or restrict the claim to feasibility-check reduction.
- [§5.3, Fig. 8(a)] The abstract states a 20% average reduction 'on a well-accepted benchmark set', but the text in §5.3 reports the 20% average only for 'the selected benchmarks' shown in Fig. 8(a), without specifying which benchmarks were selected and why. The compilation-time comparison is also against the authors' own QCiR framework without any external baseline, so it is an ablation of one component rather than a demonstration of a speedup that transfers to other PMT-based compilers. Please state the exact benchmark subset and the selection criterion, and qualify the 20% claim as applying within the QCiR framework; if the 20% figure holds over all 26 benchmarks, report that number explicitly.
minor comments (7)
- [§1, Introduction] The acronym PMT is defined as 'pattern matching and transformation' at first use, but the next paragraph expands it as 'Pattern Matching Tree'; please make the acronym definition consistent.
- [Def. 2.1] There is a typo, 'minimun' for 'minimum', and the constraint that fixes the gate sequence should state explicitly why the depth and min_index rules make the sequence unique for a given circuit.
- [Algorithm 1] The comment on line 2 contains the typo 'varibale'; please also clarify the invariant that Context is associated with the last successful Match call, since the loop body overwrites Context while descending and backtracking.
- [Example 3.2] Example 3.2 says the RTree in Fig. 3(b) is built from the transformation rules in Fig. 2(c), but the referenced nodes appear to correspond to the rules in Fig. 1; please fix the cross-reference.
- [§5.1, Transformation rules] Please state whether the exclusion of cost-preserving and cost-increasing rules happens before or after Quartz's rule verification, and give the resulting rule count in addition to the 1669 generated rules.
- [§5.3, Fig. 8(b)] The caption 'The optimization rate and the gate count' does not explain the axes or the two series; add explicit axis labels and a legend so the reader can see which points are with and without the pattern tree.
- [§5.4, Fig. 9] The right y-axis is labeled 'optimization time'; please define it as compilation or pattern-matching time so the 90% claim is unambiguous.
Circularity Check
No significant circularity: the pattern tree is a prefix-sharing index over the same transformation rules, and the reported speedups are empirical measurements, not predictions derived from the method's own outputs.
full rationale
The paper's central derivation is a data-structure argument: transformation-rule sources that share common prefixes can be organized into a tree (Def 3.2, Def 3.3), and matching can reuse the common-prefix matching context. This is self-contained: Algorithm 2 constructs the tree directly from the input transformation rules, and Algorithm 1 traverses it. The 20% and 90% compilation-time figures are measured comparisons between the same QCiR-based matcher with and without prefix-rule nodes (Sections 5.3 and 5.4), not quantities derived from the pattern-tree definition itself. The use of QCiR, the authors' prior framework, is as an implementation platform and baseline, not as a cited theorem that carries the argument; no uniqueness theorem or externally imported result is invoked to force the conclusion. The paper also reports output-circuit gate counts and verifies equivalence via Qiskit's unitary simulator for the small benchmarks (Section 5.2), giving independent evidence that the pattern tree does not change optimization quality at the tested N=8 operating point. The only concerns are evidential, not circular: the 90% claim is a tuned, two-circuit result without quality-preservation data at that operating point, and Algorithm 1's printed condition 'if find and isPrefix(R_f) then Rewrite' appears inconsistent with Def 4.1 (prefix rules should not rewrite). These are correctness and evaluation gaps, not circular reductions. Accordingly, no step of the claimed derivation reduces by construction to its own inputs.
Assumptions & free parameters
free parameters (3)
- Number of prefix rules N =
8 (1% of 845 candidates) for the 20% experiment; swept up to 40% for the 90% result
- Maximum qubits (3) and gates (6) for Quartz rule generation =
3 qubits, 6 gates
- Coverage heuristic conditions in Algorithm 2 =
children > 1, non-empty, connected
assumptions (4)
- standard math Quantum circuits are modeled as unitary matrices up to global phase (Def 2.3).
- domain assumption Transformation rules generated by Quartz are sound and sufficient for the chosen gate set {H, X, Rz, CNOT}.
- domain assumption Pattern matching on quantum circuits is NP-complete (cited to Iten et al.).
- ad hoc to paper The greedy multi-pass rule scheduler with prefix rules preserves optimization quality.
invented entities (2)
-
Pattern tree (PTree and RTree)
independent evidence
-
Prefix rule
independent evidence
Cite this review
Pith. "Pith review of Pattern Tree: Enhancing Efficiency in Quantum Circuit Optimization Based on Pattern-matching." pith.science (2026). https://pith.science/paper/EBI6A2U5
@misc{pith2026241207803,
author = {Pith},
title = {Pith review of: Pattern Tree: Enhancing Efficiency in Quantum Circuit Optimization Based on Pattern-matching},
year = {2026},
howpublished = {\url{https://pith.science/paper/EBI6A2U5}},
note = {Machine review of arXiv:2412.07803}
}
read the original 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%.
Figures
Figures from the paper (6 more)
Forward citations
Cited by 1 Pith paper
-
Quantum Circuit Optimization Based on Dynamic Grouping and ZX-Calculus for Reducing 2-Qubit Gate Count
A dynamic grouping plus ZX-calculus lookahead framework reduces two-qubit gate counts in quantum circuits by 18% on average across 25 benchmarks.
Reference graph
Works this paper leans on
-
[1]
Qcir: Pattern matching based universal quantum circuit rewriting framework
Mingyu Chen, Yu Zhang, Yongshang Li, Zhen Wang, Jun Li, and Xiangyang Li. Qcir: Pattern matching based universal quantum circuit rewriting framework. In Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, pages 1–8, 2022
work page 2022
-
[2]
Company Outlines Path Towards Quantum-Centric Supercomputing with New Hardware and Software and System Breakthrough. Ibm unveils 400 qubit-plus quantum processor and next-generation ibm quantum system two, October 2022
work page 2022
-
[3]
Source matching and rewriting for mlir using string-based automata
Vinicius Espindola, Luciano Zago, Hervé Yviquel, and Guido Araujo. Source matching and rewriting for mlir using string-based automata. ACM Transactions on Architecture and Code Optimization , 20(2):1–26, 2023
work page 2023
-
[4]
Partial compilation of variational algorithms for noisy intermediate-scale quantum machines
Pranav Gokhale, Yongshan Ding, Thomas Propson, Christopher Winkler, Nelson Leung, Yunong Shi, David I Schuster, Henry Hoffmann, and Frederic T Chong. Partial compilation of variational algorithms for noisy intermediate-scale quantum machines. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture , pages 266–278, 2019
work page 2019
-
[5]
Thomas Häner, Torsten Hoefler, and Matthias Troyer. Assertion-based optimization of quantum programs.Proceedings of the ACM on Programming Languages , 4(OOPSLA):1–20, 2020
work page 2020
-
[6]
Exact and practical pattern matching for quantum circuit optimization
Raban Iten, Romain Moyard, Tony Metger, David Sutter, and Stefan Woerner. Exact and practical pattern matching for quantum circuit optimization. ACM Transactions on Quantum Computing , 3(1), jan 2022
work page 2022
-
[7]
Qiro: A static single assignment-based quantum program representation for optimization
David Ittah, Thomas Häner, Vadym Kliuchnikov, and Torsten Hoefler. Qiro: A static single assignment-based quantum program representation for optimization. ACM Transactions on Quantum Computing , 3(3):1–32, 2022
work page 2022
-
[8]
Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D
Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, 2024
2024
Show all 25 references
-
[9]
Llvm: A compilation framework for lifelong program analysis & transformation
Chris Lattner and Vikram Adve. Llvm: A compilation framework for lifelong program analysis & transformation. In International symposium on code generation and optimization, 2004. CGO 2004. , pages 75–86. IEEE, 2004
2004
-
[10]
Mlir: Scaling compiler infrastructure for domain specific computation
Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. Mlir: Scaling compiler infrastructure for domain specific computation. In 2021 IEEE/ACM International Symposium on...
2021
-
[11]
Quarl: A learning-based quantum circuit optimizer
Zikun Li, Jinjun Peng, Yixuan Mei, Sina Lin, Yi Wu, Oded Padon, and Zhihao Jia. Quarl: A learning-based quantum circuit optimizer. Proceedings of the ACM on Programming Languages , 8(OOPSLA1):555–582, 2024
2024
-
[12]
Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization
Dmitri Maslov. Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization. Physical Review A, 93(2):022311, 2016
2016
-
[13]
Automated optimization of large quantum circuits with continuous parameters
Yun Seong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4(1):23, 2018
2018
-
[14]
Nielsen and Isaac L
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, UK, 10th Anniversary edition, 2010
2010
-
[15]
Demonstration of the trapped-ion quantum CCD computer architecture
JM Pino, JM Dreiling, C Figgatt, JP Gaebler, SA Moses, MS Allman, CH Baldwin, M Foss-Feig, D Hayes, K Mayer, et al. Demonstration of the trapped-ion quantum CCD computer architecture. Nature, 592(7853):209–213, 2021
2021
-
[16]
Quantum computing in the NISQ era and beyond
Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018
2018
-
[17]
Optimized compilation of aggregated instructions for realistic quantum computers
Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry Hoffmann, and Frederic T Chong. Optimized compilation of aggregated instructions for realistic quantum computers. InProceedings of the Twenty-Fourth International Conference on Architectural Support ...
2019
-
[18]
t |ket⟩: A retargetable compiler for NISQ devices
Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t |ket⟩: A retargetable compiler for NISQ devices. Quantum Science and Technology, 6(1):014003, 2021
2021
-
[19]
Bello-Rivas, Daniel Kochmanski, Zach Beane, Robert Smith, Andrew Shi, Cole Scott, Adam Paszke, Eric Hulburd, Matthew Young, Aaron S
Mark Skilbeck, Eric Peterson, appleby, Erik Davis, Peter Karalekas, Juan M. Bello-Rivas, Daniel Kochmanski, Zach Beane, Robert Smith, Andrew Shi, Cole Scott, Adam Paszke, Eric Hulburd, Matthew Young, Aaron S. Jackson, BHAVISHYA, M. Sohaib Alam, Wilfredo Velázquez-Rodríguez, c....
2020
-
[20]
Quingo: A programming framework for heterogeneous quantum-classical computing with nisq features
The Quingo Development Team. Quingo: A programming framework for heterogeneous quantum-classical computing with nisq features. arXiv preprint arXiv:2009.01686, 2020
2009 arXiv
-
[21]
The variational quantum eigensolver: a review of methods and best practices
Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, et al. The variational quantum eigensolver: a review of methods and best practices. arXiv preprint arXiv:2111.05176, 2021
2021 arXiv
-
[22]
Strong quantum computational advantage using a superconducting quantum processor
Yulin Wu, Wan-Su Bao, Sirui Cao, et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett., 127:180501, Oct 2021
2021
-
[23]
Aquila: Quera’s 256-qubit neutral-atom quantum computer
Jonathan Wurtz, Alexei Bylinskii, Boris Braverman, Jesse Amato-Grill, Sergio H Cantu, Florian Huber, Alexander Lukin, Fangli Liu, Phillip Weinberg, John Long, et al. Aquila: Quera’s 256-qubit neutral-atom quantum computer. arXiv preprint arXiv:2306.11727, 2023
2023 arXiv
-
[24]
Synthesizing quantum-circuit optimizers
Amanda Xu, Abtin Molavi, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. Synthesizing quantum-circuit optimizers. Proceedings of the ACM on Programming Languages , 7(PLDI):835–859, 2023
2023
-
[25]
Quartz: superoptimization of quantum circuits
Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A Acar, et al. Quartz: superoptimization of quantum circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design ...
2022
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.