paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness

ZX-图的一般范式及其在有理角完备性中的应用
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 1/10 · 该论文研究 ZX-演算的通用范式与有理角完备性,属于量子计算/范畴论式形式语义,与用户关注的 PL 与 AI/LLM 交叉、静态分析、浮点程序分析或贝叶斯程序分析均无直接关系,仅在“形式化方法”大方向上存在极弱关联。引用 1 inbox
Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart
crossref: 2026-09-12

AI 速览

一句话:为 ZX-图给出通用范式与算法,并证明 Clifford+T 公理对二进角及有理角片段的完备性。

此前 ZX-演算的完备性结果多通过第三方语言 ZW-演算获得,证明优雅但非构造性。本文为包含 Clifford+T 量子力学的任意 ZX-图片段引入通用范式,给出公理化完备的充分条件,并设计达到该范式的算法。作者将结果应用于 Clifford+T 片段、一般 ZX-演算以及有理角片段:证明 Clifford+T 公理对任意二进角片段完备;对其它有理角片段,则证明一条新的消去(cancellation)规则是必要且充分的。该工作为 ZX-演算的有理角完备性提供了构造性框架。

问题
此前 ZX-演算的完备性证明依赖 ZW-演算,缺乏构造性。
方法
提出包含 Clifford+T 的任意 ZX-图片段中的通用范式与完备性充分条件,并给出达到范式的算法。
评估
在 Clifford+T、一般 ZX-演算及有理角片段上验证,证明二进角完备性与其余有理角所需的新消去规则。
原文摘要(Abstract)

Recent completeness results on the ZX-calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give sufficient conditions for an axiomatisation to be complete, and an algorithm to reach the normal form. Finally, we apply these results to the Clifford+T fragment and the general ZX-calculus - for which we already know the completeness-, but also for any fragment of rational angles: we show that the axiomatisation for Clifford+T is also complete for any fragment of dyadic angles, and that a simple new rule (called cancellation) is necessary and sufficient otherwise.

链接与引用

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

BibTeX
@inproceedings{paperbot5011,
  title = {A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness},
  author = {Emmanuel Jeandel and Simon Perdrix and Renaud Vilmart},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785754}
}