Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group
Abstract
A reduced ordered decision diagram is the minimal automaton of a function on words of fixed length: its nodes are the residuals, and reduction is the Myhill--Nerode quotient. We study what happens when that quotient is coarsened by a group. Fix a group G acting on residuals, merge two nodes when their residuals lie in one G-orbit, and record the group element on the edge. For functions {0,1}n→ℂ and G the Pauli group this is the Local Invertible Map Decision Diagram. We take G from the two-parameter family generated by C≤ kRq, the phase rotation of order q with up to k control qubits, with and without the bit flip X. We show that this gives exponential succinctness improvements compared to Pauli-LIMDD, and we determine the succinctness order of the family completely. The separating objects are hypergraph states, which can always be efficiently represented by some member of the family. We settle the tractability of five queries and eight transformations, which is invariant across the family, and shows the same behavior as Pauli-LIMDD. We give a five-rule reduction system whose normal forms are unique for every member of the family, and we show that this canonical form is computable in polynomial time in the size of the LIMDD. We show that, when coarsening beyond the (anti-)diagonal groups, the calculation of a minimal sized normal form turns out to be non-local and it might to rebuild the whole diagram.
Related
- Generalized Toric Threefolds from Scattering Diagrams and Broken Lines
- Oracle Synthesis Based on X-Map Decision Diagrams
- How strange: Phase diagrams with 3 critical points
- Subtraction method for disconnected diagrams in full QCD
- Finite-temperature grain boundary phases, transformations, and diagrams in alloys
BibTeX
@misc{quist2026generalized,
title = {{Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group}},
author = {Arend-Jan Quist and Alexis de Colnet and Thomas Reps and Alfons Laarman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35271},
eprint = {2609.35271},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35271},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group
AU - Arend-Jan Quist
AU - Alexis de Colnet
AU - Thomas Reps
AU - Alfons Laarman
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35271
UR - https://arxiv.org/abs/2609.35271
AB - A reduced ordered decision diagram is the minimal automaton of a function on words of fixed length: its nodes are the residuals, and reduction is the Myhill--Nerode quotient. We study what happens when that quotient is coarsened by a group. Fix a group G acting on residuals, merge two nodes when their residuals lie in one G-orbit, and record the group element on the edge. For functions {0,1}^n→ℂ and G the Pauli group this is the Local Invertible Map Decision Diagram. We take G from the two-parameter family generated by C^≤ kR_q, the phase rotation of order q with up to k control qubits, with and without the bit flip X. We show that this gives exponential succinctness improvements compared to Pauli-LIMDD, and we determine the succinctness order of the family completely. The separating objects are hypergraph states, which can always be efficiently represented by some member of the family. We settle the tractability of five queries and eight transformations, which is invariant across the family, and shows the same behavior as Pauli-LIMDD. We give a five-rule reduction system whose normal forms are unique for every member of the family, and we show that this canonical form is computable in polynomial time in the size of the LIMDD. We show that, when coarsening beyond the (anti-)diagonal groups, the calculation of a minimal sized normal form turns out to be non-local and it might to rebuild the whole diagram.
ER -