2025/10/08 by Bin Cheng, Ziyuan Wang, Cheng, Bin +7
Computer Science · Engineering · #Advancements in Semiconductor Devices and Circuit Design #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2510.06775
openalex publication_date 2025/10/08 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
Classical simulation of quantum circuits is a critical tool for validating quantum hardware and probing the boundary between classical and quantum computational power. Existing state-of-the-art methods, notably tensor network approaches, have computational costs governed by the treewidth of the underlying circuit graph, making circuits with large treewidth intractable. This work rigorously analyzes FeynmanDD, a decision diagram-based simulation method proposed in CAV 2025 by a subset of the authors, and shows that the size of the multi-terminal decision diagram used in FeynmanDD is exponential in the linear rank-width of the circuit graph. As linear rank-width can be substantially smaller than treewidth and is at most larger than the treewidth by a logarithmic factor, our analysis demonstrates that FeynmanDD outperforms all tensor network-based methods for certain circuit families. We also show that the method remains efficient if we use the Solovay-Kitaev algorithm to expand arbitrary single-qubit gates to sequences of Hadamard and T gates, essentially removing the gate-set restriction posed by the method.