In quantum circuit simulation, the decision diagram (DD) data structure enables fast linear-algebra calculations by transforming vectors into a normal form and merging equivalent ones. This paper presents a novel normal-form algorithm for Local Invertible Map Decision Diagrams (LIMDD), achieving a worst-case time complexity reduction from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node, while maintaining $O(n^3)$ runtime for two distinct child nodes.
We implement this algorithm as part of QolDDer, our Pauli-LIMDD quantum circuit simulator, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, significantly outperforming existing LIMDD simulators on such circuits, often by an order of magnitude on a public quantum circuit dataset.
In the future, we envision this work enabling further application and development of LIMDD variants not only for quantum design tasks but also for the analysis of linear-algebra-based systems in general.
Blogger's Review: The algorithm optimization presented in this paper demonstrates superiority both theoretically and practically, especially in quantum circuit simulation, advancing quantum computing technology. The new algorithm enhances efficiency and provides better tools for quantum design tasks, making it worthy of attention and application.