Tower: Data Structures in Quantum Superposition
summary
Language Tower provides a reversible semantics that compiles every program to a unitary circuit and enforces reversible operations, a type system that bounds recursion with classical parameters for bounded-time execution, and a history-independent allocator Boson that does an O(n log n) one-time permutation so subsequent allocations are constant time. The Ground library implements lists, stacks, queues, strings, and the first executable sets that satisfy reversibility, history independence, and bounded-time execution and reports concrete qubit and gate counts.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:19Quantum Algorithmic Advantage
- 3:28Superposition of Data Structures
- 4:17Linked Data Structures
- 4:59Three Requirements
- 7:26Requirement 1: Reversibility
- 8:59Tower: Reversible Programming
- 12:25Requirement 2: History Independence
- 14:43Failure: Distinct Structures
- 15:31Failure: Distinct Physical Representations
- 18:04Ground: Data Structure Library
- 21:36Boson: History-Independent Allocation
related talks
26mTower: Data Structures in Quantum Superposition
15mToward A Quantum Programming Language for Higher Level Formal Verification
30mQuantum Computing for Programming Languages Researchers
01h 01mWhat Is "Quantum" About Quantum Computing?
39mBuilding a Compiler for Quantum Computers
01h 20mA Quantum Data Structure For Classical Computers
24mQunity: A Unified Language for Quantum and Classical Computing
14mDenotational semantics for stabiliser quantum programs