Programming quantum computers presents a host of problems. Consider the role of entanglement, the idea that qubits can be inextricably linked; it’s the basis for much of quantum computing’s advantage over classical computing. Writing programs to work on entangled qubits and maintaining accuracy is tricky indeed, particularly since these entangled states are notoriously fickle and short-lived.
A group of MIT researchers have developed a new quantum programming language – Twist – that adds techniques for accounting for entanglement in provable ways that they say will reduce errors. At least that’s the promise. The researchers’ paper (Twist: Sound Reasoning for Purity and Entanglement in Quantum Programs) was published by ACM last month.
There are a few accounts of the work around; this short explanatory excerpt from an article written by Rina Diane Caballar in IEEE Spectrum does one of the better jobs of clarifying the idea:
“Twist’s foundations lie in identifying entanglement, a phenomenon wherein the states of two pieces of data inside a quantum computer are linked to each other. “Whenever you perform an action on one piece of an entangled piece of data, it may affect the other one. You can implement powerful quantum algorithms with it, but it also makes it unintuitive to reason about the programs you write and easy to introduce subtle bugs,” says Charles Yuan, a Ph.D. student in computer science at MIT CSAIL and lead author on the paper about Twist, published in the journal Proceedings of the ACM on Programming Languages.
“What Twist does is it provides features that allow a developer to say which pieces of data are entangled and which ones aren’t,” Yuan says. “By including information about entanglement inside a program, you can check that a quantum algorithm is implemented correctly.”
That’s perhaps easier said, than understood. ‘Purity’ is a central concept here. In their paper, the researchers write, “In this work, we formalize purity as a central tool for automating reasoning about entanglement in quantum programs. A pure expression is one whose evaluation is unaffected by the measurement outcomes of qubits that it does not own, implying freedom from entanglement with any other expression in the computation.”
Pardon the extensive excerpting but it’s probably also worthwhile to include this brief description of quantum programming and program execution from the paper; it is a good reminder that the quantum computing requires classical computing as part of the process:
“Quantum programming languages allow programmers to utilize the computational primitives enabled by the quantum computers of today and tomorrow. Algorithms for quantum computers offer computational breakthroughs in integer, cryptographic and communication protocols, computational physics and chemistry, and machine learning.
“Quantum computation relies on the manipulation of quantum states consisting of qubits, the quantum analogs of classical data and bits. A quantum state exists in a superposition, a weighted sum over classical states. Measurement causes a superposition to assume a classical state, with probability derived mathematically from the weight ascribed to that state in the sum. In the standard QRAM model [quantum random access machine model, Knill, 1996] computations execute on a classical computer with access to a quantum device that supports initializing and operating on quantum states.”
One of the language’s features, noted the IEEE Spectrum article, is a system that enables developers to specify which expressions and pieces of data within their programs are pure – “A pure piece of data, according to Yuan, is free from entanglement, and thereby free from possible bugs and unintuitive effects caused by entanglement. Twist also has purity assertion operators to affirm that an expression lacks entanglement with any other piece of data, as well as static analyses and run-time checks to verify these assertions.”
The researchers wrote programs in Twist for several quantum algorithms and ran them on a quantum simulator. Yuan is quoted in the IEEE Spectrum article, “We performed experiments that showed the overhead of running these runtime checks is no more than 3.5 percent over running the base program, which we believe is fairly low and a good trade-off for the safety guarantees the language gives you.”
The paper is best read directly and the IEEE Spectrum piece is a good primer. Bulleted below is a list from the paper of what the authors say are their “contributions:”
- Purity. We present the novel definition of pure expressions in a quantum program, those that are unaffected by measurement outcomes of the remainder of the program. We formulate purity within the operational and denotational semantics of a functional quantum language.
- Purity Types. We present a type system that identifies pure expressions, and prove that in it, expressions of pure type are in fact pure.
- Purity Assertions. We present two types of purity assertions that state the absence of entanglement in the output of quantum gates: one stating that an expression is pure, and one stating that the two components of a pure entangled pair are individually pure.
- Purity Assertion Verification. We present a static analysis and runtime verifications for the purity assertions, such that programs passing verification satisfy their purity specifications.
- Evaluation. We implement Twist, a language featuring purity types and assertions, in quantum simulation. We show that Twist can express quantum algorithms and reject programming errors in them, that its runtime verification executes with overhead less than 3.5%, and that it can express semantically valid programs that existing languages disallow.
Link to IEEE Spectrum article: https://spectrum.ieee.org/quantum-programming-language-twist
Link to MIT News article: https://news.mit.edu/2022/new-language-quantum-computing-twist-0124
Link to the paper: https://dl.acm.org/doi/pdf/10.1145/3498691