paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On incorrectness logic for Quantum programs

论量子程序的不正确性逻辑
OOPSLA 6(OOPSLA1)2022匹配度 2/10 · 论文讨论量子程序的不正确性逻辑与静态查错,属于程序验证/静态分析方向,与用户对形式化验证的广义兴趣有弱交集;但其核心是量子程序,未涉及 ML/Agentic 系统、浮点程序分析、贝叶斯程序分析或 LLM 与程序分析的交叉。引用 27 inbox
Peng Yan, Hanru Jiang, Nengkun Yu
crossref: 2026-09-10

AI 速览

一句话:提出量子程序的不正确性逻辑,为静态查错提供可靠完备的逻辑基础。

量子程序开发中的查错十分重要,但已有工作多集中于动态分析,难以给出可靠且完备的静态论证。受经典程序的不正确性逻辑启发,本文提出面向量子程序的不正确性逻辑,作为静态查错的逻辑基础。该逻辑中公式的有效性与量子 Hoare 逻辑形成对偶。作者从可达性视角对有效性的定义给出直观解释,并与若干替代形式进行比较,进而给出可靠且完备的推理规则。文章通过 Grover 搜索、量子隐形传态以及 repeat-until-success 程序等示例展示该逻辑的实用性,并基于逻辑规则实现原型静态分析器,以自动化推理过程。

问题
如何为量子程序建立面向静态查错的逻辑基础,并克服现有动态分析难以提供可靠完备论证的问题。
方法
借鉴经典不正确性逻辑,定义与量子 Hoare 逻辑对偶的有效性概念,从可达性视角进行论证并比较替代形式,给出可靠且完备的推理规则。
评估
通过 Grover 搜索、量子隐形传态和 repeat-until-success 等示例进行推理,并实现基于逻辑规则的原型静态分析器来自动化推理过程。
原文摘要(Abstract)

Bug-catching is important for developing quantum programs. Motivated by the incorrectness logic for classical programs, we propose an incorrectness logic towards a logical foundation for static bug-catching in quantum programming. The validity of formulas in this logic is dual to that of quantum Hoare logics. We justify the formulation of validity by an intuitive explanation from a reachability point of view and a comparison against several alternative formulations. Compared with existing works focusing on dynamic analysis, our logic provides sound and complete arguments. We further demonstrate the usefulness of the logic by reasoning several examples, including Grover's search, quantum teleportation, and a repeat-until-success program. We also automate the reasoning procedure by a prototyped static analyzer built on top of the logic rules.

链接与引用

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

BibTeX
@article{paperbot1520,
  title = {On incorrectness logic for Quantum programs},
  author = {Peng Yan and Hanru Jiang and Nengkun Yu},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {OOPSLA1},
  year = {2022},
  doi = {10.1145/3527316}
}