一句话：证明经典条件跳转无法直接提升到叠加态，并给出量子计算机可正确实现控制流的充要条件与量子控制机 ISA。
该文研究量子算法中依赖叠加数据的分支与迭代等控制流抽象为何难以在量子计算机上直接实现。作者首先证明：即使程序计数器本身处于叠加态，将经典条件跳转指令直接提升到量子情形也不能正确实现控制流，因此不能把 λ-演算等一般控制流抽象从经典语言直接搬到量子编程。随后，论文给出控制流在量子计算机上可正确实现的充要条件。基于这些条件，作者提出量子控制机器（Quantum Control Machine），一种带受限条件跳转指令的指令集架构，使开发者能用程序计数器而非硬件逻辑门来表达量子算法中的控制流。
Quantum algorithms for tasks such as factorization, search, and simulation rely on control flow such as branching and iteration that depends on the value of data in superposition. High-level programming abstractions for control flow, such as switches, loops, higher-order functions, and continuations, are ubiquitous in classical languages. By contrast, many quantum languages do not provide high-level abstractions for control flow in superposition, and instead require the use of hardware-level logic gates to implement such control flow. The reason for this gap is that whereas a classical computer supports control flow abstractions using a program counter that can depend on data, the typical architecture of a quantum computer does not analogously provide a program counter that can depend on data in superposition. As a result, the complete set of control flow abstractions that can be correctly realized on a quantum computer has not yet been established. In this work, we provide a complete characterization of the properties of control flow abstractions that are correctly realizable on a quantum computer. First, we prove that even on a quantum computer whose program counter exists in superposition, one cannot correctly realize control flow in quantum algorithms by lifting the classical conditional jump instruction to work in superposition. This theorem denies the ability to directly lift general abstractions for control flow such as the λ-calculus from classical to quantum programming. In response, we present the necessary and sufficient conditions for control flow to be correctly realizable on a quantum computer. We introduce the quantum control machine, an instruction set architecture featuring a conditional jump that is restricted to satisfy these conditions. We show how this design enables a developer to correctly express control flow in quantum algorithms using a program counter in place of logic gates.
@article{paperbot2533,
title = {Quantum Control Machine: The Limits of Control Flow in Quantum Programming},
author = {Charles Yuan and Agnes Villanyi and Michael Carbin},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {OOPSLA1},
year = {2024},
doi = {10.1145/3649811}
}