Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916996258463744 |
|---|---|
| author | Cheng, Bin Wang, Ziyuan Deng, Ruixuan Chen, Jianxin Ji, Zhengfeng |
| author_facet | Cheng, Bin Wang, Ziyuan Deng, Ruixuan Chen, Jianxin Ji, Zhengfeng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06775 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams Cheng, Bin Wang, Ziyuan Deng, Ruixuan Chen, Jianxin Ji, Zhengfeng Quantum Physics Data Structures and Algorithms 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. |
| title | Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.06775 |