paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Targeting Classical Code to a Quantum Annealer

将经典代码编译到量子退火器
ASPLOS Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems2019匹配度 2/10 · 论文主题是将经典代码编译为量子退火器可求解的二次伪布尔最小化问题,属于量子编译与优化方向;与用户关注的 LLM/Agent、静态分析、浮点程序分析及贝叶斯程序分析(尤其与 LLM 的交叉)没有直接关联。引用 7 inbox
Scott Pakin
crossref: 2026-09-12

AI 速览

一句话:提出将经典代码编译为二次伪布尔最小化问题,从而可在量子退火器上前向或反向执行。

量子退火器是一种利用量子效应启发式求解二次伪布尔函数最小化(NP 难)问题的专用计算机,其原生编程仅涉及提供函数系数向量并接收使函数最小的布尔向量,与 CPU/GPU 等冯·诺依曼架构截然不同。本文研究如何将常规代码编译到这一新硬件目标上:把经典代码转换为量子退火器可求解的最小化问题,并使生成代码既可前向执行(从输入到输出),也可反向执行(从输出到输入)。作者进一步展示如何利用这种双向执行能力来简化 NP 复杂度类中问题的表达与求解,从而为在量子退火器上运行经典代码提供了编译途径。

问题
量子退火器与冯·诺依曼架构差异显著,其原生编程要求以二次伪布尔函数系数向量为输入,常规代码无法直接运行。
方法
将经典代码编译为量子退火器可求解的二次伪布尔最小化问题,并让生成代码支持前向(输入到输出)与反向(输出到输入)两种执行方式。
评估
通过展示该双向执行能力如何简化 NP 复杂度类问题的表达与求解,作者论证了该编译路径的可行性。
原文摘要(Abstract)

From a compiler's perspective, a quantum annealer represents a fundamentally different hardware target from a CPU, GPU, or other von Neumann architecture. Quantum annealers are special-purpose computers that use quantum effects to heuristically determine the set of Boolean variables that minimize a quadratic pseudo-Boolean function (an NP-hard problem). Natively programming such systems involves supplying them with a vector of function coefficients and receiving a vector of function-minimizing Booleans in return. The contribution of this work is to demonstrate how to compile conventional code into a minimization problem for solution on a quantum annealer. The resulting code can run either forward (from inputs to outputs) or backward (from outputs to inputs). We show how this capability can be exploited to simplify the expression and solution of problems in the NP complexity class.

链接与引用

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

BibTeX
@inproceedings{paperbot4920,
  title = {Targeting Classical Code to a Quantum Annealer},
  author = {Scott Pakin},
  booktitle = {ASPLOS},
  year = {2019},
  doi = {10.1145/3297858.3304071}
}