paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Completeness for arbitrary finite dimensions of ZXW-calculus, a unifying calculus

任意有限维度下 ZXW 演算的完备性:一个统一的演算
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 2/10 · 论文研究量子计算中的 ZXW 图形演算及其在任意有限维 qudit 上的完备性,属于量子程序语义与形式化方法,与用户关注的 PL/AI 交叉、静态分析、浮点程序分析、贝叶斯程序分析及 LLM/Agent 改进验证等方向没有直接交集。仅在“形式语义/程序语言理论”层面存在较边缘的关联。引用 28 inbox
Boldizsár Poór, Quanlong Wang, Razin A. Shaikh, Lia Yeh, Richie Yeung, Bob Coecke
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:把 ZXW 演算推广到任意有限维 qudit,并证明其完备性,是首个超越 qubit 的通用图形语言完备性结果。

ZX-calculus 与 ZW-calculus 都是 qubit 量子计算的通用图形语言,且均已被证明完备;二者结合而成的 ZXW-calculus 使图形微分、积分与指数运算成为可能,从而支撑量子机器学习与量子化学等新方法,但其此前仅适用于 qubit。本文将 ZXW-calculus 推广到任意有限维度,即 qudit,并证明该图形重写系统对任意有限维度都完备。这是首个超越 qubit 的通用图形语言的完备性结果,为高维量子电路的优化、编译与推理提供了统一的图形化基础。

问题
ZXW 演算统一了 ZX 与 ZW 两种通用图形语言,但此前只定义并证明完备于 qubit,缺乏对任意有限维度(qudit)的推广与完备性保证。
方法
将 ZXW 演算的生成元与重写规则推广到任意有限维度,并借助 Hilbert 空间语义模型证明该重写系统对每个有限维度都完备,即所有在该形式化下成立的高维线性映射等式均可在演算中推导。
评估
以数学证明作为评估方式,给出任意有限维度的完备性定理;论文属于理论结果,未报告实现或实验评估。
原文摘要(Abstract)

The ZX-calculus is a universal graphical language for qubit quantum computation, meaning that every linear map between qubits can be expressed in the ZX-calculus. Furthermore, it is a complete graphical rewrite system: any equation involving linear maps that is derivable in the Hilbert space formalism for quantum theory can also be derived in the calculus by rewriting. It has widespread usage within quantum industry and academia for a variety of tasks such as quantum circuit optimisation, error-correction, and education.The ZW-calculus is an alternative universal graphical language that is also complete for qubit quantum computing. In fact, its completeness was used to prove that the ZX-calculus is universally complete. This calculus has advanced how quantum circuits are compiled into photonic hardware architectures in the industry.Recently, by combining these two calculi, a new calculus has emerged for qubit quantum computation, the ZXW-calculus. Using this calculus, graphical-differentiation, -integration, and -exponentiation were made possible, thus enabling the development of novel techniques in the domains of quantum machine learning and quantum chemistry.Here, we generalise the ZXW-calculus to arbitrary finite dimensions, that is, to qudits. Moreover, we prove that this graphical rewrite system is complete for any finite dimension. This is the first completeness result for any universal graphical language beyond qubits.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{PoorWSYYC23,
  title = {Completeness for arbitrary finite dimensions of ZXW-calculus, a unifying calculus},
  author = {Boldizsár Poór and Quanlong Wang and Razin A. Shaikh and Lia Yeh and Richie Yeung and Bob Coecke},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175672}
}