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