⚛️ quantum physics

Faster algorithm for achieving minimal-size quantum decision diagrams

This paper presents a novel $O(n^2)$ normal-form algorithm for Pauli-LIMDDs implemented in the QolDDer simulator, which significantly accelerates quantum circuit simulation—particularly for Clifford circuits—by achieving order-of-magnitude speedups over existing tools and realizing the theoretically proven exponential advantages of this data structure.

Original authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Organizing a Chaotic Library

Imagine you are trying to simulate a quantum computer. To do this, you have to track the state of many tiny particles (qubits). As you add more particles, the amount of information you need to store explodes. It's like trying to write down every single book in a library that doubles in size every time you add a new shelf. Eventually, the library becomes so huge that no computer can hold it.

To solve this, scientists use a data structure called a Decision Diagram (DD). Think of a DD not as a giant list, but as a flowchart or a tree. Instead of writing out every single detail, the flowchart branches out. If two branches lead to the exact same outcome, you don't draw them twice; you just draw one branch and point to it from both places. This "merging" saves massive amounts of space.

The Problem: The "Messy" Flowchart

There are different types of these flowcharts. The paper focuses on a very powerful type called LIMDD (Local Invertible Map Decision Diagram).

Standard Flowcharts (QMDDs): These are like a strict librarian who only merges two branches if they are exactly identical.
LIMDDs: These are like a genius librarian who can merge branches even if they look different, as long as they are related by a specific mathematical "translation" (like a Pauli gate). This allows LIMDDs to be much smaller and faster than standard ones.

However, there is a catch. To get the benefit of merging, the flowchart must be in a "canonical form." This means the librarian must follow a strict set of rules to ensure that if two things can be merged, they are merged.

The paper explains that previous attempts to build LIMDD simulators were like librarians who knew the rules but were too slow or lazy to follow them perfectly.

They were slow: The algorithm to check if two branches should be merged was like trying to solve a complex puzzle every time you added a book. It took too long ( $O(n^3)$ ).
They were messy: Because the rules weren't followed perfectly, the flowcharts ended up with duplicate branches that should have been merged. This made the simulation slow and bloated, losing the theoretical speed advantage.

The Solution: A Faster Sorting Algorithm

The authors of this paper, Juul Sanders and his team, created a new, faster algorithm to fix the "messy flowchart" problem.

The Analogy:
Imagine you have a pile of socks. You want to find pairs.

The Old Way: You pick up one sock, compare it to every single other sock in the pile to see if it matches. If you have 1,000 socks, this takes forever.
The New Way (This Paper): The authors found a clever trick. If you have a pile of socks where most are already sorted, you can find the matching pair much faster by looking at specific patterns. They adapted a math technique (the Zassenhaus algorithm) to act like a super-efficient sock-sorter.

What they achieved:

Speed: For many common cases (when a node has only one child), they sped up the sorting process from a slow, heavy task to a quick, light one (improving from $O(n^3)$ to $O(n^2)$ ).
Perfection: They implemented this in a new simulator called QolDDer. Because they followed the rules perfectly, their flowcharts are "reduced" (minimal size).

The Results: Proof in the Pudding

The team tested their new simulator against existing ones:

Against Standard Flowcharts (QMDDs): On "Clifford circuits" (a specific type of quantum circuit), their new LIMDD was exponentially faster. It was like comparing a bicycle to a rocket ship. The standard flowcharts got bogged down in huge amounts of data, while the new LIMDD kept things tiny.
Against Other LIMDDs: They compared their work to two other LIMDD simulators (MQT-LIMDD and LimTDD).
- One of the others didn't follow the merging rules strictly enough, so it ended up with a bloated flowchart and was much slower.
- The other one was faster than the standard ones but still couldn't match the new simulator's speed because it lacked the "perfect sorting" (canonicity) the authors achieved.

The Takeaway

The paper claims that LIMDDs are theoretically the best tool for simulating certain quantum circuits, but only if you can build them correctly.

Before: People knew LIMDDs were great in theory, but the tools to build them were too slow or imperfect, so they didn't work well in practice.
Now: The authors built a "perfect" tool (QolDDer) with a faster sorting algorithm. They proved that when you use this tool, LIMDDs actually live up to their promise, running orders of magnitude faster than older methods on specific tasks.

In short: They didn't invent a new type of quantum computer, but they invented a much better way to organize the "map" of the quantum computer's state, making simulations significantly faster and more efficient.

Technical Summary: Faster Algorithm for Achieving Minimal-Size Quantum Decision Diagrams

Problem Statement
Decision diagrams (DDs) are a compact data structure for representing quantum states and operations, achieving succinctness by merging equivalent sub-functions into a canonical form. While Local Invertible Map Decision Diagrams (LIMDDs) theoretically offer exponential advantages over other structures like Quantum Multiple-Valued Decision Diagrams (QMDDs) for specific circuit classes (e.g., Clifford circuits), these advantages have not fully materialized in existing implementations.

The primary bottleneck is the normal-form procedure, specifically the high determinism rule required to ensure canonicity. This rule resolves degrees of freedom where two nodes represent the same quantum state up to a local invertible map (LIM). The existing algorithm for this rule, based on group-theoretic tasks, has a worst-case time complexity of $O(n^3)$ for an $n$ -qubit node. Furthermore, existing open-source implementations (MQT-LIMDD and LimTDD) either fail to achieve minimal size in all cases or deliberately omit the canonicity property to avoid implementation complexity, leading to potential exponential blow-ups in node count.

Methodology
The authors propose a novel algorithm to transform semi-reduced Pauli-LIMDD nodes into fully reduced (canonical) forms, specifically optimizing the high determinism rule.

Algorithmic Improvement:
- The authors adapt the Zassenhaus procedure, a method for computing intersections and unions of vector spaces, to solve the minimization problem required for high determinism.
- Instead of calculating stabilizer group intersections and cosets separately, they construct a "Zassenhaus matrix" with three registers: binary vectors representing Pauli words, middle stabilizers, and right stabilizers.
- By performing Gaussian elimination on this matrix using Pauli-LIM multiplication rules, they simultaneously find the minimal Pauli word and the corresponding stabilizer generators.
- Complexity Reduction:
  - For nodes with two distinct children, the algorithm maintains the $O(n^3)$ worst-case complexity but with reduced overhead.
  - For nodes with a single child (a common case where DDs achieve succinctness), the problem simplifies to minimizing a vector against a single stabilizer group. This reduces the complexity from $O(n^3)$ to $O(n^2)$ .
Recursive Stabilizer Finding:
- The authors present a recursive algorithm to compute the stabilizer generating set for a reduced node using the Zassenhaus results. This avoids redundant group intersection calculations, further optimizing the $O(n^2)$ case for single-child nodes.
Implementation (QolDDer):
- The algorithm is implemented in QolDDer, a new, open-source, from-scratch Pauli-LIMDD simulator written in C/C++.
- QolDDer includes a separate library, PauliLim, for the core normalization logic.
- The implementation handles numerical precision by treating floating-point scalars with a configurable threshold ( $\delta = 10^{-13}$ ) and using search trees for equivalence checking, while preserving canonicity.

Key Results
The authors evaluated QolDDer against two existing LIMDD implementations (MQT-LIMDD, LimTDD) and the QMDD simulator (MQT-DDSIM) using the RandCliff (random Clifford) and MQT-Bench datasets.

Exponential Speedup on Clifford Circuits: On random Clifford circuits (RandCliff), QolDDer demonstrates an exponential speedup over QMDDs (MQT-DDSIM). This confirms the theoretical advantage of LIMDDs, which can represent Clifford circuit outputs in polynomial space, whereas QMDDs cannot succinctly represent the resulting highly entangled states.
Impact of Canonicity:
- Enabling full canonicity (High Determinism) in QolDDer results in significantly faster run times and drastically fewer nodes compared to semi-reduced (non-canonical) versions on Clifford circuits.
- QolDDer outperforms the existing MQT-LIMDD implementation by an order of magnitude on many instances, attributed to MQT-LIMDD's partial implementation of canonicity.
- QolDDer is consistently faster than LimTDD (which lacks canonicity guarantees) on Clifford circuits, often by a factor of 25 or more, due to the node count reduction achieved through canonical merging.
Limitations on General Benchmarks: On the broader MQT-Bench dataset, the performance advantage of canonicity is not universal. For certain circuit types (e.g., Quantum Neural Networks, Grover's algorithm), LIMs do not provide more merging than QMDDs, and the overhead of maintaining canonicity makes QolDDer slightly slower (by a constant factor) than MQT-DDSIM. However, the scaling remains linear.

Significance and Claims
The paper claims that the primary barrier to realizing the theoretical power of LIMDDs has been the lack of an efficient, fully canonical implementation. By providing an $O(n^2)$ algorithm for the critical single-child case and a robust, open-source implementation (QolDDer), the authors demonstrate that:

LIMDDs can indeed achieve exponential advantages over QMDDs for specific, important circuit classes (Clifford circuits).
Canonicity is essential to realizing these advantages; without it, node counts can blow up, negating the benefits of the data structure.
The work enables further development of LIMDD variants for both quantum design tasks and general linear-algebra-based system analysis.

The authors remain modest regarding general benchmarks, noting that for circuits where LIMs offer no additional merging over QMDDs, the canonical overhead may not be justified. Future work is envisioned to extend these algorithms to the broader XP group and apply LIMDDs to tasks like circuit equivalence checking and classical linear algebra problems.