SPLASH 2022
Mon 5 - Sat 10 December 2022 Auckland, New Zealand
Fri 9 Dec 2022 14:00 - 14:30 at Lecture Theatre 2 - Quantum Chair(s): Jan Vitek

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.

Fri 9 Dec

Displayed time zone: Auckland, Wellington change

13:30 - 15:00
QuantumOOPSLA at Lecture Theatre 2
Chair(s): Jan Vitek Northeastern University
13:30
30m
Research paper
Bugs in Quantum computing platforms: an empirical study
OOPSLA
Matteo Paltenghi University of Stuttgart, Germany, Michael Pradel University of Stuttgart
DOI
14:00
30m
Talk
Tower: Data Structures in Quantum Superposition
OOPSLA
Charles Yuan Massachusetts Institute of Technology, Michael Carbin Massachusetts Institute of Technology
DOI
14:30
30m
Talk
Verified Compilation of Quantum Oracles
OOPSLA
Liyi Li University of Maryland, Finn Voichick University of Maryland, Kesha Hietala University of Maryland, Yuxiang Peng University of Maryland, Xiaodi Wu University of Maryland, Michael Hicks University of Maryland; Amazon
DOI