  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.
