Pith. sign in

REVIEW 2 major objections 42 references

Faster algorithm for achieving minimal-size quantum decision diagrams

T0 review · 2 major / 0 minor · reviewed 2026-06-25 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read New normal-form algorithm for Pauli-LIMDDs reduces single-child node time from O(n^3) to O(n^2).

desk verdict The paper gives a working O(n^2) normal-form path for single-child Pauli-LIMDD nodes plus a C++ implementation that makes the speedups real on Clifford circuits. read the letter →

arxiv 2606.24789 v1 pith:NFVA22P2 submitted 2026-06-23 quant-ph cs.DS

Juul Sanders , Sebastiaan Brand , Arend-Jan Quist , Tim Coopmans This is my paper · ORCID
classification quant-phcs.DS
keywords Pauli-LIMDDdecisiondiagramsnormalformquantumcircuitsimulationCliffordcircuitsstates
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces a novel algorithm to compute the normal form of Pauli-LIMDDs, which merge quantum state vectors that are equivalent under local invertible maps such as Pauli gates. This normal form produces the smallest possible diagram by identifying and merging equivalent substructures. The main contribution is a reduction in worst-case runtime from cubic to quadratic in the number of qubits for nodes with a single child, while retaining cubic time when two distinct children are present. The authors implement the method in a new simulator and show it makes the theoretical advantages of LIMDDs practical for Clifford circuits, with order-of-magnitude speedups over prior implementations on benchmark sets.

What carries the argument

The normal-form algorithm that reduces LIM-equivalent vectors to a canonical representative for Pauli-LIMDDs, with a specialized reduction path for the single-child case.

What would settle it

Construct an arbitrary n-qubit single-child Pauli-LIMDD node for successive values of n and measure whether the observed runtime follows O(n^2) scaling or remains O(n^3).

Watch

Extended reading notes

Core claim

We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from O(n^3) to O(n^2) for an n-qubit DD node with a single child node while keeping the O(n^3) run time in case of two distinct children nodes. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude.

Load-bearing premise

The claimed O(n^2) bound for the single-child case holds after all correctness-preserving reductions are applied and does not rely on special structure that appears only in the tested circuits.

Editorial extensions

If this is right

  • The implementation realizes the exponential advantages of Pauli-LIMDDs on Clifford circuits.
  • The simulator is significantly faster than existing LIMDD simulators on Clifford circuits.
  • On a public quantum-circuit data set the new simulator often outperforms prior LIMDD simulators by an order of magnitude.
  • The work supports further application of LIMDD variants to quantum design tasks and linear-algebra systems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The quadratic scaling for single-child nodes could extend the practical reach of LIMDD simulation to larger qubit counts than before.
  • Similar case-splitting optimizations might be adaptable to other decision-diagram normal-form procedures used in linear algebra.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 0 minor

Summary. The paper presents a novel normal-form algorithm for Pauli-LIMDDs that claims a worst-case speedup from O(n^3) to O(n^2) for an n-qubit DD node with a single child node (retaining O(n^3) for two distinct children). The algorithm is implemented in the new QolDDer simulator (C/C++), which is reported to realize theoretical advantages on Clifford circuits, run significantly faster than prior LIMDD simulators, and often outperform them by an order of magnitude on a public quantum-circuit dataset.

Significance. If the O(n^2) single-child bound is shown to survive all required equivalence checks and reductions, the work would be a meaningful step toward making the theoretically exponential advantages of LIMDDs practically usable for quantum-circuit simulation. The from-scratch implementation and reported empirical gains on Clifford circuits are concrete strengths that could support further LIMDD variants.

major comments (2)
  1. [Abstract] Abstract: the central claim requires that the optimized single-child normal-form path remains O(n^2) once every equivalence check and reduction required for the LIM normal form is performed. The text does not exhibit an invariant guaranteeing that no reduction step invokes an operation whose cost is Ω(n^3) (e.g., full LIM composition) or that the single-child case never produces a second distinct child during reduction.
  2. [Abstract] The manuscript states the O(n^2) improvement while “keeping the O(n^3) run time in case of two distinct children nodes,” but supplies neither the algorithm steps nor the benchmark data needed to check whether the bound is achieved without hidden assumptions or post-hoc restrictions on the tested circuits.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments. We address each major comment below and will revise the manuscript to strengthen the presentation of the complexity analysis.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim requires that the optimized single-child normal-form path remains O(n^2) once every equivalence check and reduction required for the LIM normal form is performed. The text does not exhibit an invariant guaranteeing that no reduction step invokes an operation whose cost is Ω(n^3) (e.g., full LIM composition) or that the single-child case never produces a second distinct child during reduction.

    Authors: Section 3 of the manuscript details the algorithm and proves that single-child nodes remain single-child under all LIM reductions, with equivalence checks performed via O(n^2) operations that avoid full LIM composition. We will add an explicit reference to this invariant in the abstract and introduction. revision: yes

  2. Referee: [Abstract] The manuscript states the O(n^2) improvement while “keeping the O(n^3) run time in case of two distinct children nodes,” but supplies neither the algorithm steps nor the benchmark data needed to check whether the bound is achieved without hidden assumptions or post-hoc restrictions on the tested circuits.

    Authors: The algorithm steps, including pseudocode for both single- and two-child cases, appear in Section 3 with the O(n^3) bound for the latter. Section 5 reports benchmarks on the public Clifford-circuit dataset with no circuit restrictions. We will add cross-references to these sections from the abstract. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; algorithmic complexity claim is self-contained

full rationale

The paper introduces a new normal-form algorithm for Pauli-LIMDDs and states a complexity improvement (O(n^2) for single-child nodes, O(n^3) otherwise). This is a direct claim about the runtime of the presented procedure after reductions. No equations or steps reduce the claimed bound to a fitted parameter, self-citation chain, or input by construction. The abstract and description treat the speedup as arising from the algorithm design itself, with no load-bearing self-citation or renaming of known results. The analysis is therefore independent of the reported performance numbers and does not match any enumerated circularity pattern.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The work rests on standard algorithmic complexity analysis and the correctness of the existing LIMDD equivalence relation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster algorithm for achieving minimal-size quantum decision diagrams." pith.science (2026). https://pith.science/paper/NFVA22P2

@misc{pith2026260624789,
  author       = {Pith},
  title        = {Pith review of: Faster algorithm for achieving minimal-size quantum decision diagrams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NFVA22P2}},
  note         = {Machine review of arXiv:2606.24789}
}
abstract

The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node while keeping the $O(n^3)$ run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.

Figures

Figures reproduced from arXiv: 2606.24789 by the authors.

Figure 1
Figure 1. Structurally, a DD that encodes a vector |ψ⟩ is a directed acyclic graph whose internal nodes have two outgoing edges. An example of a QMDD or LIMDD node is shown in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. In this figure, it is shown how a vector of size 2 n is represented as a decision tree of depth n. A QMDD (c) represents this vector more succinctly by factoring out scalars and storing these on edges. The LIMDD representation (d) compresses the data even further by putting Kronecker products of local (2 × 2) matrices on the edges (d). to nodes corresponding to subvectors |ψ0⟩ and |ψ1⟩ respectively. A DD achieves su… view at source ↗
Figure 3
Figure 3. Normalization rules that bring LIMDD nodes to their reduced form [37], as￾suming reduced children u, w. Reproduced and adjusted from [37, Fig.11] (CC-BY 4.0) [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The goal of the high determinism algorithm is to evalu￾ate eq. (1), i.e. to find αA given βB and Stab(v0), Stab(v1). In general, there are multiple tuples (g, h, s, x) that achieve the minimum of Eq. (1). However we show in Sec. A that any two such tuples (g, h, s, x),…
Figure 5
Figure 5. Figure 5: Run times and node counts of canonical and semi-canonical versions of our Pauli-LIMDD simulator QolDDer on the RandCliff benchmark set. Note the log-log scales, on which a monomial function (x 7→ x k ) shows up as a straight line. The dotted grey line visualizes break-…
Figure 6
Figure 6. Figure 6: Run time comparisons of our implementation (QolDDer) to the QMDD imple￾mentation (MQT-DDSIM) and the two LIMDD implementations (MQT-LIMDD and LimTDD) on log-log scales. As is shown by the legends, sub-figures (a-c) show the run time comparison for the RandCliff benchma…
Figure 7
Figure 7. Figure 7: Run times and node counts of reduced and semi-reduced versions of our Pauli￾LIMDD simulator on the MQT-Bench benchmark set. Note the log-log axes scales. 5 Discussion We presented a novel, more efficient algorithm to bring LIMDD nodes into a canonical form, and impleme…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 5 canonical work pages

  1. [1]

    https://gitlab.tudelft.nl/ardeq-group/paulilim (2026)

    PauliLim. https://gitlab.tudelft.nl/ardeq-group/paulilim (2026)

    2026

  2. [2]

    https://gitlab.tudelft.nl/ardeq-group/qoldder (2026)

    QolDDer. https://gitlab.tudelft.nl/ardeq-group/qoldder (2026)

    2026

  3. [3]

    Physical Review A—Atomic, Molecular, and Optical Physics70(5), 052328 (2004)

    Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Physical Review A—Atomic, Molecular, and Optical Physics70(5), 052328 (2004)

    2004

  4. [4]

    In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems

    Ardeshir-Larijani, E., Gay, S.J., Nagarajan, R.: Verification of concurrent quan- tum protocols by equivalence checking. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 500–514. Springer (2014)

    2014

  5. [5]

    New Journal of Physics7(1), 170 (2005), http: //stacks.iop.org/1367-2630/7/i=1/a=170

    Audenaert, K.M.R., Plenio, M.B.: Entanglement on mixed stabilizer states: normal forms and reduction procedures. New Journal of Physics7(1), 170 (2005), http: //stacks.iop.org/1367-2630/7/i=1/a=170

    2005

  6. [6]

    Formal methods in system design10(2), 171–206 (1997)

    Bahar, R.I., Frohm, E.A., Gaona, C.M., Hachtel, G.D., Macii, E., Pardo, A., Somenzi, F.: Algebric decision diagrams and their applications. Formal methods in system design10(2), 171–206 (1997)

    1997

  7. [7]

    Brand, S., Laarman, A.: Q-Sylvan: a parallel decision diagram package for quantum computing.In:InternationalSymposiumonAutomatedTechnologyforVerification and Analysis. pp. 260–273. Springer (2025)

    2025

  8. [8]

    In: International Conference on Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems

    Brand, S., Quist, A.J., van Dijk, R.M., Laarman, A.: Numerical errors in quan- titative system analysis with decision diagrams. In: International Conference on Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems. pp. 371–388. Springer (2025)

    2025

Show all 42 references
  1. [9]

    ACM Computing Surveys (CSUR)24(3), 293–318 (1992)

    Bryant, R.E.: Symbolic Boolean manipulation with ordered binary-decision dia- grams. ACM Computing Surveys (CSUR)24(3), 293–318 (1992)

    1992

  2. [10]

    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40(9), 1810–1824 (2020)

    Burgholzer, L., Wille, R.: Advanced equivalence checking for quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40(9), 1810–1824 (2020)

    2020

  3. [11]

    Chemical reviews119(19), 10856–10915 (2019)

    Cao, Y., Romero, J., Olson, J.P., Degroote, M., Johnson, P.D., Kieferová, M., Kivlichan, I.D., Menke, T., Peropadre, B., Sawaya, N.P., et al.: Quantum chemistry in the age of quantum computing. Chemical reviews119(19), 10856–10915 (2019)

    2019

  4. [12]

    In: International Conference on Tools and Algo- rithms for the Construction and Analysis of Systems

    Chen, T.F., Jiang, J.H.R.: SliQSim: A quantum circuit simulator and solver for probability and statistics queries. In: International Conference on Tools and Algo- rithms for the Construction and Analysis of Systems. pp. 129–138. Springer (2025)

    2025

  5. [13]

    Formal methods in system design10(2), 149–169 (1997)

    Fujita, M., McGeer, P.C., Yang, J.Y.: Multi-terminal binary decision diagrams: An efficient data structure for matrix representation. Formal methods in system design10(2), 149–169 (1997)

    1997

  6. [14]

    Reviews of Modern Physics86(1), 153–185 (2014)

    Georgescu, I.M., Ashhab, S., Nori, F.: Quantum simulation. Reviews of Modern Physics86(1), 153–185 (2014)

    2014

  7. [15]

    IEEE Transac- tions on Quantum Engineering2, 1–17 (2021)

    Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal, D., Greenberg, D.: Formulating and solving routing problems on quantum computers. IEEE Transac- tions on Quantum Engineering2, 1–17 (2021)

    2021

  8. [16]

    arXiv preprint arXiv:2504.01168 (2025)

    Hong, X., Dai, A., Gao, D., Li, S., Ji, Z., Ying, M.: LimTDD: A compact decision diagram integrating tensor and local invertible map representations. arXiv preprint arXiv:2504.01168 (2025)

    2025

  9. [17]

    In: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design

    Hong, X., Feng, Y., Li, S., Ying, M.: Equivalence checking of dynamic quan- tum circuits. In: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design. pp. 1–8 (2022)

    2022

  10. [18]

    Physical Review B100(13), 134306 (2019) 18 J

    Li, Y., Chen, X., Fisher, M.P.: Measurement-driven entanglement transition in hybrid quantum circuits. Physical Review B100(13), 134306 (2019) 18 J. Sanders et al

    2019

  11. [19]

    Journal of Symbolic Computation23(4), 335–354 (1997)

    Luks, E.M., Rákóczi, F., Wright, C.R.: Some algorithms for nilpotent permutation groups. Journal of Symbolic Computation23(4), 335–354 (1997)

    1997

  12. [20]

    In: Symbolic model checking, pp

    McMillan, K.L.: Symbolic model checking. In: Symbolic model checking, pp. 25–60. Springer (1993)

    1993

  13. [21]

    In: 36th International Symposium on Multiple-Valued Logic (ISMVL’06)

    Miller, D.M., Thornton, M.A.: QMDD: A decision diagram structure for reversible and quantum circuits. In: 36th International Symposium on Multiple-Valued Logic (ISMVL’06). pp. 30–30. IEEE (2006)

    2006

  14. [22]

    Cambridge University Press (2000)

    Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)

    2000

  15. [23]

    Reviews in Physics4, 100028 (2019)

    Orús, R., Mugel, S., Lizaso, E.: Quantum computing for finance: Overview and prospects. Reviews in Physics4, 100028 (2019)

    2019

  16. [24]

    Quantum7, 1062 (2023)

    Quetschlich, N., Burgholzer, L., Wille, R.: MQT Bench: Benchmarking Software and Design Automation Tools for Quantum Computing. Quantum7, 1062 (2023). https://doi.org/10.22331/q-2023-07-20-1062, MQT Bench is available at https:// mqt-bench.app/

    2023 doi

  17. [25]

    arXiv:2602.17775 (2026)

    Quist, A.J., Coopmans, T., Laarman, A.: Exact quantum decision diagrams with scaling guarantees for Clifford+Tcircuits and beyond. arXiv:2602.17775 (2026)

    2026

  18. [26]

    In: European Symposium on Algorithms

    Samoladas, V.: Improved BDD algorithms for the simulation of quantum circuits. In: European Symposium on Algorithms. pp. 720–731. Springer (2008)

    2008

  19. [27]

    faster algorithm for achieving minimal-size quantum decision diagrams

    Sanders, J., Brand, S., Coopmans, T.: QEST+FORMATS 2026 artifact for "faster algorithm for achieving minimal-size quantum decision diagrams". https://doi.org/ 10.5281/zenodo.19763549 (2026)

    2026 doi

  20. [28]

    In: IJCAI

    Sanner, S., McAllester, D.: Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference. In: IJCAI. vol. 2005, pp. 1384– 1390 (2005)

    2005

  21. [29]

    In: FOCS

    Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factor- ing. In: FOCS. pp. 124–134. IEEE (1994)

    1994

  22. [30]

    Sistla,M.,Chaudhuri,S.,Reps,T.:SymbolicquantumsimulationwithQuasimodo. In: CAV. pp. 213–225. Springer (2023)

    2023

  23. [31]

    Proceedings of the ACM on Programming Languages 8(OOPSLA2), 1390–1419 (2024)

    Sistla, M., Chaudhuri, S., Reps, T.: Weighted context-free-language ordered bi- nary decision diagrams. Proceedings of the ACM on Programming Languages 8(OOPSLA2), 1390–1419 (2024)

    2024

  24. [32]

    https: //web.archive.org/web/20171208230728/http://vlsi.colorado.edu/~fabio/CUDD/ cudd.pdf (2015)

    Somenzi, F.: CUDD: CU decision diagram package release 3.0.0. https: //web.archive.org/web/20171208230728/http://vlsi.colorado.edu/~fabio/CUDD/ cudd.pdf (2015)

    2015

  25. [33]

    For- mal Methods in System Design10(2), 243–270 (1997)

    Tafertshofer, P., Pedram, M.: Factored edge-valued binary decision diagrams. For- mal Methods in System Design10(2), 243–270 (1997)

    1997

  26. [34]

    In: International Symposium on Automated Technology for Verification and Analysis

    Thanos, D., Coopmans, T., Laarman, A.: Fast equivalence checking of quantum circuits of Clifford gates. In: International Symposium on Automated Technology for Verification and Analysis. pp. 199–216. Springer (2023)

    2023

  27. [35]

    In: 2021 58th ACM/IEEE Design Automation Conference (DAC)

    Tsai, Y.H., Jiang, J.H.R., Jhang, C.S.: Bit-slicing the hilbert space: Scaling up ac- curate quantum circuit simulation. In: 2021 58th ACM/IEEE Design Automation Conference (DAC). pp. 439–444. IEEE (2021)

    2021

  28. [36]

    In: Proceedings Design, Automation and Test in Europe Conference and Exhibition

    Viamontes, G.F., Markov, I.L., Hayes, J.P.: High-performance QuIDD-based simu- lation of quantum circuits. In: Proceedings Design, Automation and Test in Europe Conference and Exhibition. vol. 2, pp. 1354–1355. IEEE (2004)

    2004

  29. [37]

    Quantum7, 1108 (2023) Faster algorithm for achieving minimal-size quantum decision diagrams 19

    Vinkhuijzen, L., Coopmans, T., Elkouss, D., Dunjko, V., Laarman, A.: LIMDD: A decision diagram for simulation of quantum computing including stabilizer states. Quantum7, 1108 (2023) Faster algorithm for achieving minimal-size quantum decision diagrams 19

    2023

  30. [38]

    In: Proceedings of the AAAI Conference on Artificial Intel- ligence

    Vinkhuijzen, L., Coopmans, T., Laarman, A.: A knowledge compilation map for quantum information. In: Proceedings of the AAAI Conference on Artificial Intel- ligence. vol. 40, pp. 19406–19414 (2026)

    2026

  31. [39]

    In: International Symposium on Model Checking Software

    Vinkhuijzen, L., Grurl, T., Hillmich, S., Brand, S., Wille, R., Laarman, A.: Effi- cient implementation of LIMDDs for quantum circuit simulation. In: International Symposium on Model Checking Software. pp. 3–21. Springer (2023)

    2023

  32. [40]

    In: Proceedings of the 59th Design Automation Conference

    Wei, C.Y., Tsai, Y.H., Jhang, C.S., Jiang, J.H.R.: Accurate BDD-based unitary operator manipulation for scalable and robust quantum circuit verification. In: Proceedings of the 59th Design Automation Conference. pp. 523–528 (2022)

    2022

  33. [41]

    In: 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

    Zulehner, A., Hillmich, S., Wille, R.: How to efficiently handle complex values? Implementing decision diagrams for quantum computing. In: 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). pp. 1–7. IEEE (2019)

    2019

  34. [42]

    u≼w” in the caption. This condition would be replaced by “max precedence holds

    Zulehner, A., Wille, R.: Advanced simulation of quantum computations. IEEE TCAD38(5), 848–859 (2018) A Proof of High Determinism minimizer form Fix the number of qubitsn≥0. LetG 0, G1 ben-qubit stabilizer groups and letBbe ann-qubit Pauli word. Suppose that both(g, h, s, x),(g...

    2018

Pith tools

Reviewed June 25, 2026 · model on record in the stance chip above.