When MIT professor and now Computer Science and Artificial Intelligence Laboratory (CSAIL) member Peter Shor first demonstrated the potential of quantum computers to solve problems faster than classical ones, he inspired scientists to imagine countless possibilities for the emerging technology. Thirty years later, though, the quantum edge remains a peak not yet reached.
Unfortunately, the technology of quantum computing isn't fully operational yet. One major challenge lies in translating quantum algorithms from abstract mathematical concepts into concrete code that can run on a quantum computer. Whereas programmers for regular computers have access to myriad languages such as Python and C++ with constructs that align with standard classical computing abstractions, quantum programmers have no such luxury; few quantum programming languages exist today, and they are comparatively difficult to use because quantum computing abstractions are still in flux. In their recent work, MIT researchers highlight that this disparity exists because quantum computers don't follow the same rules for how to complete each step of a program in order - an essential process for all computers called control flow - and present a new abstract model for a quantum computer that could be easier to program.
In a paper soon to be presented at the ACM Conference on Object-oriented Programming, Systems, Languages, and Applications, the group outlines a new conceptual model for a quantum computer, called a quantum control machine, that could bring us closer to making programs as easy to write as those for regular classical computers. Such an achievement would help turbocharge tasks that are impossible for regular computers to efficiently complete, like factoring large numbers, retrieving information in databases, and simulating how molecules interact for drug discoveries.
"Our work presents the principles that govern how you can and cannot correctly program a quantum computer," says lead author and CSAIL PhD student Charles Yuan SM '22. "One of these laws implies that if you try to program a quantum computer using the same basic instructions as a regular classical computer, you'll end up turning that quantum computer into a classical computer and lose its performance advantage. These laws explain why quantum programming languages are tricky to design and point us to a way to make them better."
Old school vs. new school computing
One reason why classical computers are relatively easier to program today is that their control flow is fairly straightforward. The basic ingredients of a classical computer are simple: binary digits or bits, a simple collection of zeros and ones. These ingredients assemble into the instructions and components of the computer's architecture. One important component is the program counter, which locates the next instruction in a program much like a chef following a recipe, by recalling the next direction from memory. As the algorithm sequentially navigates through the program, a control flow instruction called a conditional jump updates the program counter to make the computer either advance forward to the next instruction or deviate from its current steps.
By contrast, the basic ingredient of a quantum computer is a qubit, which is a quantum version of a bit. This quantum data exists in a state of zero and one at the same time, known as a superposition. Building on this idea, a quantum algorithm can choose to execute a superposition of two instructions at the same time - a concept called quantum control flow.
The problem is that existing designs of quantum computers don't include an equivalent of the program counter or a conditional jump. In practice, that means programmers typically implement control flow by manually arranging logical gates that describe the computer's hardware, which is a tedious and error-prone procedure. To provide these features and close the gap with classical computers, Yuan and his coauthors created the quantum control machine - an instruction set for a quantum computer that works like the classical idea of a virtual machine. In their paper, the researchers envision how programmers could use this instruction set to implement quantum algorithms for problems such as factoring numbers and simulating chemical interactions.
As the technical crux of this work, the researchers prove that a quantum computer cannot support the same conditional jump instruction as a classical computer, and show how to modify it to work correctly on a quantum computer. Specifically, the quantum control machine features instructions that are all reversible - they can run both forward and backward in time. A quantum algorithm needs all instructions, including those for control flow, to be reversible so that it can process quantum information without accidentally destroying its superposition and producing a wrong answer.
The hidden simplicity of quantum computers
According to Yuan, you don't need to be a physicist or mathematician to understand how this futuristic technology works. Quantum computers don't necessarily have to be arcane machines, he says, that require scary equations to understand. With the quantum control machine, the CSAIL team aims to lower the barrier to entry for people to interact with a quantum computer by raising the unfamiliar concept of quantum control flow to a level that mirrors the familiar concept of control flow in classical computers. By highlighting the dos and don'ts of building and programming quantum computers, they hope to educate people outside of the field about the power of quantum technology and its ultimate limits.
Still, the researchers caution that as is the case for many other designs, it's not yet possible to directly turn their work into a practical hardware quantum computer due to the limitations of today's qubit technology. Their goal is to develop ways of implementing more kinds of quantum algorithms as programs that make efficient use of a limited number of qubits and logic gates. Doing so would bring us closer to running these algorithms on the quantum computers that could come online in the near future.
"The fundamental capabilities of models of quantum computation has been a central discussion in quantum computation theory since its inception," says MIT-IBM Watson AI Lab researcher Patrick Rall, who was not involved in the paper. "Among the earliest of these models are quantum Turing machines which are capable of quantum control flow. However, the field has largely moved on to the simpler and more convenient circuit model, for which quantum lacks control flow. Yuan, Villanyi, and Carbin successfully capture the underlying reason for this transition using the perspective of programming languages. While control flow is central to our understanding of classical computation, quantum is completely different! I expect this observation to be critical for the design of modern quantum software frameworks as hardware platforms become more mature."
The paper lists two additional CSAIL members as authors: PhD student Ági Villányi '21 and Associate Professor Michael Carbin. Their work was supported, in part, by the National Science Foundation and the Sloan Foundation.
