FlatDD: Parallel Quantum Circuit Simulation using Decision Diagram and Flat Array
TL;DR
FlatDD is presented, a parallel QCS that capitalizes on the strength of both DD- and array-based approaches and enhances the simulation performance for deep circuits, and introduces a gate-fusion algorithm to reduce the computational cost.
Abstract
Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a parallel QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages caching to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 54.35 × speed-up and 1.91 × memory reduction.