Quantum Control Machine: The Limits of Control Flow in Quantum Programming
Proceedings of the ACM on Programming Languages(2023)
摘要
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, and higher-order functions, 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 using a program counter that can depend on data, the typical architecture
of a quantum computer does not 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.
更多查看译文
关键词
quantum instruction set architectures,quantum programming languages
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要