by Benoît Valiron (LRI – CentraleSupelec, Univ. Paris Saclay)
Moving from the textual description of an appealing algorithm to an actual implementation reveals hidden difficulties.
Between 2011 and 2013, I had the opportunity to collaborate on the Pan-American project QCS (Quantum Computer Science) devoted to the implementation and analysis of quantum algorithms. Researchers from different areas, ranging from physicists to theoretical computer scientists, were working on this project; I was at the latter end of this spectrum. We were given a set of seven, state-of-the-art quantum algorithms instantiated on some concrete problems, with the task to implement and estimate the resources necessary to effectively run them, in the event of an actual quantum computer. To this end we developed the quantum programming language Quipper [L1].
Quantum algorithms are not usually designed as practical handles but instead as tools to explore complexity boundaries between classical and quantum computation: for a given problem, as the size of the input parameter grows, can we asymptotically go faster with the use of a quantum memory than with purely classical means? It turns out that many interesting problems have this property: many fields ranging from big-data to chemistry and pharmaceutic could benefit from the use of quantum algorithms. The natural question is how to concretely implement these quantum algorithms, estimate the required resources and validate the implementation.
In the realm of classical computation, implementing an algorithm implies the choice of a programming language to code it, a platform to run the resulting program, and a compiler that can turn the code into a program executable on this platform. The realm of quantum computation is currently less developed: several competing platform co-exists, and in 2011, at the beginning of the QCS project, no scalable quantum programming language even existed.
From a programmer’s perspective, quantum computation is very close to classical computation. The main difference lies in the use of a special kind of memory with exotic properties: in particular, quantum data is non-duplicable and reading quantum data is a probabilistic operation. The interaction with the quantum memory is done by a sequence of elementary operations that are summarised by what is known as a quantum circuit. A quantum algorithm mainly consists of the construction of such circuits, their execution on the quantum memory, and various classical pre- and post-processing.
This hints at the main required design choice: a quantum programming language is primarily a circuit-description language. However, quantum algorithms are not simply fixed, static quantum circuits. Unlike classical circuitry such as FGPAs, quantum algorithms describe families of quantum circuits: the circuit depends on the size and shape of the input data. A quantum programming language therefore has to account for this parametricity. Quipper has been designed from the ground up with these aspects in mind. Following a successful trend in domain specific languages, Quipper is an embedded language within a host language. The chosen host language is Haskell. This modern, functional language features an expressive type system making it easy to define and enforce the specificities of circuit construction and manipulation. Parametricity is naturally obtained with the use of lists and list combinators. The construction of a circuit is modelled as printing on a particular kind of output channel: generating an elementary instruction corresponds to writing it on the channel. Within Haskell, this kind of side-effect can naturally be encapsulated within a type construct known as monad. This automatically outlaws various ill-defined programs, renders their coding less error-prone while easing debugging.
Quipper has been used to code large algorithms and perform logical resource estimation: for a given set of parameters to the problem, what is the size of circuit generated by the algorithm? The size can be counted in the number of elementary, logical operations and in the size of the required quantum memory footprint. The analysis shows that for naive implementations, these numbers can be quite large, yielding unrealistic circuits. This analysis tends to show that producing usable algorithms requires more than concentrating on complexity analysis. Nowadays, it is possible to do so: with the help of programming languages such as Quipper, a quantum algorithm designer can effectively analyse and tune its algorithm for concrete use-cases.
The advent of modern quantum programming languages clears a path towards the design of quantum compilation stacks and tools for certification of quantum programs. Quipper is currently the backbone of two projects aiming at such goals. The European Itea3 project Quantex spanning across France, Netherlands and Germany gathers Atos/Bull, CEA/Leti, LORIA, LRI, TUDelft, KPN, Siemens and Univ. Tübingen. Quantex aims at developing the programming environment around Quipper and focuses on the compilation towards emulation of quantum computation. The recently started French ANR SoftQPro is centered on a formalisation of Quipper’s semantics toward certification, and on the development of a compilation stack based on the graphical calculus ZX, envisioned as a more natural intermediate representation than existing proposals.
Link: [L1] https://kwz.me/hB6
References:
[1] A. S. Green, P. L. Lumsdaine, N. J. Ross et al.: “Quipper: A Scalable Quantum Programming Language”, in Proc. of PLDI 2013, ACM SIGPLAN Notices, Vol. 48 Issue 6, pp. 333-342, 2013.
[2] B. Valiron, N. J. Ross, P. Selinger et al.: “Programming the Quantum Future”, Communications of the ACM, Vol. 58 No. 8, pp. 52-61, 2015.
[3] A. Scherer, et al.: “Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target”, Quantum Information Processing 16:60, 2017.
Please contact:
Benoît Valiron, LRI – CentraleSupelec, Univ. Paris Saclay, France
