paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Minimal Equational Theories for Quantum Circuits

量子电路的极小等式理论
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 论文属于量子电路的形式语义与等式理论,虽与程序语言/形式化方法有理论关联,但未涉及用户核心关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。引用 20 inbox
Alexandre Clément, Noé Delorme, Simon Perdrix
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:首次给出量子电路的极小且完备的等式理论,并证明任何完备等式理论都需作用于无界数量量子比特的规则。

本文引入首个针对量子电路的极小且完备的等式理论。作者证明量子电路上的任何真等式都可由简单规则推出,这些规则除一条新颖但直观的规则外均为标准规则:多控制 2π 旋转等价于恒等。相比近期完备等式理论,该工作去掉了若干规则,包括一条很不实用的规则。主要贡献之一是证明该等式理论的极小性,即任何规则都不能由其余规则推出。更一般地,作者表明:当所有门均为酉门时,任何量子电路完备等式理论都要求规则作用于无界数量的量子比特。最后,该工作还简化了带辅助量子比特和/或量子比特丢弃的完备等式理论。

问题
量子电路缺乏极小且完备的等式理论,已有完备理论包含较多规则且含不实用规则。
方法
提出一套由标准规则和一条新规则(多控制 2π 旋转为恒等)组成的等式理论,并证明其完备性与极小性;同时推广到带辅助量子比特和量子比特丢弃的情形。
评估
以数学证明为主:证明该理论可推出所有真等式、各规则不可相互导出,并证明任意酉门量子电路完备等式理论都需要作用于无界数量量子比特的规则;此外给出辅助量子比特与量子比特丢弃理论的简化。
原文摘要(Abstract)

We introduce the first minimal and complete equational theory for quantum circuits. Hence, we show that any true equation on quantum circuits can be derived from simple rules, all of them being standard except a novel but intuitive one which states that a multi-control 2π rotation is nothing but the identity. Our work improves on the recent complete equational theories for quantum circuits, by getting rid of several rules including a fairly impractical one. One of our main contributions is to prove the minimality of the equational theory, i.e. none of the rules can be derived from the other ones. More generally, we demonstrate that any complete equational theory on quantum circuits (when all gates are unitary) requires rules acting on an unbounded number of qubits. Finally, we also simplify the complete equational theories for quantum circuits with ancillary qubits and/or qubit discarding.

链接与引用

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

BibTeX
@inproceedings{abs-2311-07476,
  title = {Minimal Equational Theories for Quantum Circuits},
  author = {Alexandre Clément and Noé Delorme and Simon Perdrix},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662088}
}