Metraipolis › archive › dc_c4f6ec544dcd
Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group — arXiv:2609.35271
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35271
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:45:32.266Z
- SHA-256 of the archived text
3b713570d557f22f0cfe1f9a549ca3340425e82cc1e90fe175c371b7b866cc49- Stable URL of this page
https://metraipolis.com/documento/dc_c4f6ec544dcd
How to cite
Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group — arXiv:2609.35271 — arXiv (en), https://arxiv.org/abs/2609.35271 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c4f6ec544dcd (Metraipolis archive dc_c4f6ec544dcd, sha256 3b713570d557f22f0cfe1f9a549ca3340425e82cc1e90fe175c371b7b866cc49)
BibTeX
@misc{dcc4f6ec544dcd,
title = {Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group — arXiv:2609.35271},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35271},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c4f6ec544dcd; sha256 3b713570d557f22f0cfe1f9a549ca3340425e82cc1e90fe175c371b7b866cc49},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35271. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\to\mathbb{C}$ and $G$ the Pauli group this is the Local Invertible Map Decision Diagram. We take $G$ from the two-parameter family generated by $C^{\leq k}R_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.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-29 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.35271 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:19:23.494Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).