Quantum Programming with Data Structures
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 representing an abstract set as a hash table, fail these properties, calling for tools to develop specialized implementations.
In this extended abstract, we introduce Tower, a language for quantum programming with data structures in random-access memory. We also present Boson, the first allocator enabling reversible, history-independent, and constant-time dynamic memory allocation in quantum superposition.
Thu 15 SepDisplayed time zone: Belgrade, Bratislava, Budapest, Ljubljana, Prague change
09:00 - 10:30
Quantum programming languages and paradigmsPLanQC at E3
Chair(s): Robert Rand University of Chicago
|Quantum relational Hoare logic, towards a formalization|
Dominique Unruh University of Tartu
|Type-safe (Variational) Quantum Programming in IdrisVirtual|
Liliane-Joy Dandy EPFL, Ecole Polytechnique, Emmanuel Jeandel LORIA, University of Lorraine, Vladimir Zamdzhiev Inria, LORIA, Université de LorraineFile Attached
|Quantum Programming with Data Structures|
Charles Yuan MIT CSAIL, Michael Carbin MIT CSAILFile Attached