To efficiently develop algorithms for quantum com-puters, a quantum simulator capable of handling many qubits at high speed is essential. However, a state vector-based simulator needs to store a vector of length
2Nfor
Nqubits. In today's typical desktop computing environment, a maximum of around 30 qubits can be handled. A decision diagram-based simulator is expected to solve the problem of memory requirement for some set of quantum algorithms. Decision diagram stores state vectors as graphs, which may significantly reduce memory usage in the presence of regularities in the state vector. In this study, we have implemented our decision diagram-based quantum simulator and conducted experiments using various algorithms to compare with the state vector-based simulator. Algorithms such as Grover and Shor show significant speedup and superiority of performance for larger numbers of qubits, whereas random circuits with many parameterized rotation gates show slower performance. As described above, researchers should understand the characteristics of simulators so that quantum algorithms can be developed more efficiently.
The classical simulation of quantum circuits is inherently constrained by the exponential growth of the quantum state. Strategies based on decision diagrams, such as the Quantum Multiple-valued Decision Diagram structure, exploit regularities in the tensor descriptions of quantum operators and states to mitigate this limitation. This paper presents QOLE, a browser-compatible simulator for quantum circuits, that utilizes these diagrams in its implementation. QOLE offers a simple and intuitive high-level programming interface for building circuits, while its internal diagram-based compiler maps quantum gates and state vectors into compact graphs that enable more efficient simulation. The open implementation of QOLE demonstrates how diagram-based simulation can be made accessible within the constraints of modern web execution environments.
The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from
O(n3) to
O(n2) for an
n-qubit DD node with a single child node while keeping the
O(n3) run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.