← 研踪 PaperTrailarXiv:2603.06764 · v2
Efficient Classical Simulation of Low-Rank-Width Quantum Circuits Using ZX-Calculus
首次提交 2026-03-06 23:00
版本更新 2026-11-04 16:06
雷达观测 2026-11-05 12:13
摘要
In this paper, we introduce an algorithm for contracting (i.e. numerically evaluating) ZX-diagrams whose computational complexity is governed by rank-width, a structural graph parameter that behaves nicely under ZX rewrite rules. Our method evaluates a graph-like ZX-diagram in ~O(4^R) time, given its rank-decomposition of width R. By constructing suitable rank-decompositions, we provide a classical simulation algorithm for quantum circuits whose runtime is bounded by both ~O(2^n) and ~O(2^(t/2)), where n is the number of qubits and t is the number of non-Clifford phase gates. Thus, our method is no slower than either the naive state-vector simulation or the elementary stabiliser decomposition baseline, and in practice can be even faster when the reduced ZX-diagram has low rank-width. We benchmark our simulation algorithm against Quimb, a popular tensor contraction library, and observe substantial reductions in floating-point operations, often by several orders of magnitude, for random and structured non-Clifford circuits and for random ZX-diagrams.
作者备注：In Proceedings QPL 2026, arXiv:2611.04069
期刊信息：EPTCS 456, 2026, pp. 219-235
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 16:06 · 最新观测版本
Efficient Classical Simulation of Low-Rank-Width Quantum Circuits Using ZX-Calculus
In this paper, we introduce an algorithm for contracting (i.e. numerically evaluating) ZX-diagrams whose computational complexity is governed by rank-width, a structural graph parameter that behaves nicely under ZX rewrite rules. Our method evaluates a graph-like ZX-diagram in ~O(4^R) time, given its rank-decomposition of width R. By constructing suitable rank-decompositions, we provide a classical simulation algorithm for quantum circuits whose runtime is bounded by both ~O(2^n) and ~O(2^(t/2)), where n is the number of qubits and t is the number of non-Clifford phase gates. Thus, our method is no slower than either the naive state-vector simulation or the elementary stabiliser decomposition baseline, and in practice can be even faster when the reduced ZX-diagram has low rank-width. We benchmark our simulation algorithm against Quimb, a popular tensor contraction library, and observe substantial reductions in floating-point operations, often by several orders of magnitude, for random and structured non-Clifford circuits and for random ZX-diagrams.
查看此版本解读 →查看此版本原文 ↗