In a digital computer, the basic unit of information is the bit, or binary digit. A bit can only take one of two values: zero or one. On the other hand, in a quantum computer, the basic unit of information is the quantum bit, or qubit. And unlike the classical bit, the value of a qubit can simultaneously be zero and one with a certain probability associated with each value, a phenomenon known as a superposition of states. Although in theory, a quantum computer will not be able to solve problems that cannot be solved in a digital computer, the characteristics of quantum systems, such as overlapping states and action at a distance, promise that quantum computers, when they get built, will be much faster than digital computers.
In addition to the hardware challenges of building a quantum computer, from a software point of view the design of the programming languages that will be used on these computers is an open question; this is the problem approached here. The article begins by describing a hypothetical quantum architecture in which a quantum computer functions as a coprocessor controlled by a classical computer (that is, a traditional digital computer). Then, the authors present the main techniques employed to describe quantum algorithms and the basic requirements of quantum programming languages. Finally, there is a brief overview of other quantum languages. Then Quipper, a functional programming language for quantum computing, is presented. Quipper is a deeply embedded domain-specific language (EDSL) inside the host language Haskell; among the main features of the language are its hardware independence and its extensible data types. The authors describe their experiences using Quipper, claiming they have been able to implement seven quantum algorithms. Finally, they show as an example two subroutines written in Quipper.
In conclusion, thanks to the authors’ approachable writing, this article makes entertaining and instructive reading for those interested in the subject of quantum computing.