Quantum Control Machine: The Limits of Control Flow in Quantum Programming

Abstract

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 $\lambda$-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.

24 pages, 10 figures. v5: added funding acknowledgements. v4: camera-ready version. v3: added examples and improved organization of paper. v2: switched LaTeX template, improved descriptive text and added more discussion of implications

References in corpus (31)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• A Quantum Random Walk Search Algorithm
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Toward the first quantum simulation with quantum speedup
• Quantum Data Fitting
• Quantum computations without definite causal structure
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Programmable quantum gate arrays
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• A Lambda Calculus for Quantum Computation
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• A Verified Optimizer for Quantum Circuits
• Fault tolerant resource estimation of quantum random-access memories
• QIRAL: A High Level Language for Lattice QCD Code Generation
• Dynamical phase transitions, temporal orthogonality and the dynamics of observables in one dimensional ultra-cold quantum gases: from the continuum to the lattice
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Twist: Sound Reasoning for Purity and Entanglement in Quantum Programs
• The Vectorial $\lambda$-Calculus
• High Performance Quantum Modular Multipliers
• Tower: Data Structures in Quantum Superposition
• Presheaf models of quantum computation: an outline
• Programming a quantum computer with quantum instructions
• Infinite-Dimensionality in Quantum Foundations: W*-algebras as Presheaves over Matrix Algebras
• Quantum Recursion and Second Quantisation
• Defining Quantum Control Flow
• Quantum CPOs
• Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations

Cited by in corpus (2)

• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Compositional Quantum Control Flow with Efficient Compilation in Qunity