Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors generalize Local Invertible Map Decision Diagrams (LIMDDs) by coarsening Myhill–Nerode automata quotients over a two-parameter group family generated by multi-controlled phase rotations $C^{\leq k}R_q$ with and without bit flips. This generalization achieves exponential succinctness improvements over standard Pauli-LIMDDs—rendering complex quantum structures like hypergraph states efficiently representable—while completely preserving the tractability of five core queries and eight transformations. Furthermore, they establish a five-rule confluent reduction system that computes unique canonical representations in polynomial time, while proving that coarsening beyond (anti-)diagonal groups causes minimal diagram reduction to become non-local.
Coarsening decision diagram quotients modulo multi-controlled phase rotations unlocks exponential compression for quantum states like hypergraph states without sacrificing polynomial-time canonicity or query tractability.
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.