Tower: Data Structures in Quantum Superposition

Abstract

Emerging quantum algorithms for problems such as element distinctness, subset sum, and closest pair demonstrate computational advantages by relying on abstract data structures. Practically realizing such an algorithm as a program for a quantum computer requires an efficient implementation of the data structure whose operations correspond to unitary operators that manipulate quantum superpositions of data. To correctly operate in superposition, an implementation must satisfy three properties -- reversibility, history independence, and bounded-time execution. Standard implementations, such as the representation of an abstract set as a hash table, fail these properties, calling for tools to develop specialized implementations. In this work, we present Core Tower, the first language for quantum programming with random-access memory. Core Tower enables the developer to implement data structures as pointer-based, linked data. It features a reversible semantics enabling every valid program to be translated to a unitary quantum circuit. We present Boson, the first memory allocator that supports reversible, history-independent, and constant-time dynamic memory allocation in quantum superposition. We also present Tower, a language for quantum programming with recursively defined data structures. Tower features a type system that bounds all recursion using classical parameters as is necessary for a program to execute on a quantum computer. Using Tower, we implement Ground, the first quantum library of data structures, including lists, stacks, queues, strings, and sets. We provide the first executable implementation of sets that satisfies all three mandated properties of reversibility, history independence, and bounded-time execution.

arXiv comment30 pages, 22 figures. [v2] add discussion of concurrent work in Sec 1.4 and add acknowledgements section. [v3] camera-ready version, incorporates revisions following conference review

References in corpus (25)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum cryptography: Public key distribution and coin tossing
• Quantum algorithm for solving linear systems of equations
• A Quantum Approximate Optimization Algorithm
• Quantum random access memory
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Toward the first quantum simulation with quantum speedup
• Simulating chemistry using quantum computers
• An approximate Fourier transform useful in quantum factoring
• Q#: Enabling scalable quantum computing and development with a high-level domain-specific language
• Addition on a Quantum Computer
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• On the robustness of bucket brigade quantum RAM
• A functional quantum programming language
• Fault tolerant resource estimation of quantum random-access memories
• Quantum Recommendation Systems
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Parallelising the Queries in Bucket Brigade Quantum RAM
• SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation
• Nested Quantum Walks with Quantum Data Structures
• Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory
• Quantum-accelerated constraint programming
• Quantum Lower Bound for Recursive Fourier Sampling
• Memory Compression with Quantum Random-Access Gates
• Quantum Dictionaries without QRAM

Cited by in corpus (5)

• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Compositional Quantum Control Flow with Efficient Compilation in Qunity
• Quantum Data Structure for Range Minimum Query