Why do we need Q#?

Visual Studio Blog

November 15th, 20180 0

You may be familiar with the Microsoft Quantum blog, which shares general news about our quantum computing program and about quantum computing in general. This blog is its developer- and community-focused partner. It will host technical posts, deep dives into the language and libraries, and tutorials. There will also be developer event announcements and recaps, new release information, and the like.

Why We Wrote Q#

tl;dr: Because we want to write algorithms, not circuits.

History and Requirements

Q# grew out of a project to build a follow-on to LIQUi|〉 that would be oriented towards writing, compiling, and executing algorithms on both short-term small-scale “NISQ” and eventual large-scale quantum computers. While supporting simulation is important in the short term as the primary available execution platform, and even in the long term as an aid for debugging, the goal of the project is execution on quantum hardware, not simulation. In addition, we wanted to support scalability of development as well as of execution; that is, the project should allow productive development of large numbers of complex applications, not just one or two simple canned algorithms.

To meet these goals, we came up with the following requirements for the language, compiler, and runtime:

Algorithms must be expressed in terms of abstract qubits, rather than physical qubits. For large numbers of qubits, the compiler and runtime should manage the mapping from program qubits to logical (error-corrected) qubits, and then eventually to physical qubits. Doing this by hand becomes unmanageably complicated for any non-trivial algorithm. The compiler and runtime should also be responsible for selecting and implementing the error correction and fault tolerance approach.
Algorithms need to allow integrated quantum and classical computation. In particular, classical flow control based on quantum measurement outcomes must be supported. This is required to support quantum patterns such as repeat-until-success and adaptive phase estimation.
Higher-order protocols such as phase estimation and oblivious amplitude amplification must be expressible. A common pattern in quantum computing is “meta-algorithms” such as these, which operate on other operations rather than on qubits. It is necessary for development scalability to allow such algorithms to be expressed abstractly and used with the appropriate input algorithms.
Higher-order transformations such as taking the adjoint of an operation must be natively expressible. There are two common ways to derive a new operation from an existing one in quantum computing: taking the adjoint of the operation and controlling the operation with a qubit or multiple qubits. To support writing higher-level protocols cleanly, there should be a way to express that the adjoint or controlled version of an operation should be invoked. It greatly aids development scalability for the compiler to be able to auto-generate the adjoint or controlled version of an operation.
Tasks such as gate synthesis, gate sequence optimization, and ancilla management should be delegated to the compiler. Performing these tasks manually becomes unmanageable rapidly, even for medium-size algorithms. This implies that the compiler must be able to determine a great deal of information statically, so that tasks such as rotation synthesis may be done at compile time rather than during execution.
Algorithms should be required to respect the laws of physics. For instance, copying the state of a qubit should not be possible. Direct access to the qubit state should not be possible, although we allow a certain amount of validation and state examination to facilitate debugging with a simulator.

Our first attempt, not surprising given our LIQUi|〉 heritage, was to use a quantum library embedded in the functional portion of F#. We used the F# quotations feature to examine and process the quantum algorithm code.

As a functional language with rich support for generics and type inference, F# made the first four requirements easy to meet. Meta-operations were easy to express as F# functions that took function arguments. Adjoint and Controlled were implemented as F# functions that were recognized and processed specially by the compiler.

Initially we had a fair amount of success with this approach, when we had only the compiler developers writing quantum algorithms. As more and more people started using the platform, though, we found that the code for compiler features such as generating adjoints and synthesizing gates became more and more complicated. Providing these features depends on being able to comprehend the semantics of an algorithm in order to perform symbolic computation on the algorithm. Unfortunately for this purpose, F# (like any modern general-purpose language) is a rich language with a very rich set of libraries, so that it is difficult for a compiler to look at code and determine what it means. When there were only a few developers writing algorithms, it was possible for our compiler to recognize and handle the specific idioms that those developers used. Every time we got a new user, though, they brought with them a new set of idioms that the compiler had to recognize. This approach was clearly not scalable in terms of platform development.

Q#: A Domain-Specific Language

After a significant effort to make the embedded approach work, we finally decided that moving to a custom domain-specific language for quantum computing would offer significant enough advantages to be worth the development cost of building our own compiler front-end and libraries. In the summer of 2017, we started designing Q#.

Execution Model

One decision we made at the start was that we were going to treat the quantum computer as an accelerator, similar to the way that a GPU is treated. This means that there will be a main application program written in C#, F#, or some other .NET language, and the quantum code will run as a subroutine to the main program. This also means that the quantum routine can be limited to just the accelerated portion of the application; capabilities such as file I/O and user interaction can be safely omitted from Q# and left to the main program.

Design Principles

We knew that designing a new language isn’t quick and easy, and that we were unlikely to get everything right first time. Thus, we decided on a set of core principles to guide our process both initially and as Q# evolves:

Start minimal and evolve carefully based on user experience.
Be quantum first, familiar second.
Use libraries wherever possible, rather than language features.
Keep clear, well-defined semantics to enable rich optimizations and transformations in the compiler back-end.

Starting minimal led us to defer many features that we could have put into Q# at the beginning, and instead to wait and see if they’re needed. For example, the first preview of Q# did not support a C-like ternary operator. We subsequently heard from users that lacking this operator over-complicated the code for a simple situation; specifically, a mutable variable and an `if` statement were required to simply have a conditional return. Thus, in our 0.3 release we will add support for a ternary operator.

An example of quantum first is the repeat-until statement, which directly expresses the quantum repeat-until-success pattern. While it’s possible to express this pattern using a C-like while or do/while loop, doing so requires multiple flags and some awkward logic that obscures the pattern. Having a specialized statement allows this pattern to be apparent in the code, both to the reader and to optimizers and other code transformations.

Some Key Q# Features

Qubit Management

In Q#, qubits are a resource that are requested from the runtime when needed and returned when no longer in use. This is similar to the way that classical languages deal with heap memory.

The Q# language doesn’t specify whether qubits are logical or physical. This can be decided by the runtime when the algorithm is executed. Similarly, the mapping from a qubit variable in a program to an actual logical or physical qubit is decided by the runtime, and that mapping may be deferred until after the topology and other details of the target device is known. The runtime is responsible for determining a mapping that allows the algorithm to execute, including any qubit state transfer and remapping required during execution.

Q# also supports “dirty ancillas”: There are quantum routines that require additional workspace qubits (ancillas) during execution, but that are guaranteed to return the qubits back to their original state by the end of the routine. These ancillae can be qubits that are currently in use but that are not accessed during the routine in question. The Q# compiler and runtime can determine which qubits are safe for use this way, avoiding the need of additional “clean” qubits and reducing the overall space requirements of an algorithm.

First-Class Operations

Operations and functions in Q# are first-class entities; they can be passed to other operations, assigned to variables, and used like any other value. This makes it easy to express protocols such as amplitude amplification, phase estimation, and others in the Q# Canon library.

A related feature, partial application, enhances the power of first-class operations by making it easy to define new operations as specialized versions of existing operations. The Canon implementation of the Trotter-Suzuki expansion demonstrates the power Q# gets from the combination of first-class operations and partial application.

Adjoint and Controlled Derivations

Q# provides two ways of deriving a new operation from an existing one:

The Adjoint of an operation is, mathematically, the complex conjugate transpose of the operation. For the unitary operations common in quantum computing, the adjoint of an operation is its inverse; that is, it undoes the computation that the operation performs.
The Controlled version of an operation takes one or more additional qubits and performs the base operation if and only if the additional “control” qubits are in the computational 1 state. Of course, it does this in superposition, so the result is typically an entangled state of the control qubits and the operated-on qubits.

Both the adjoint and controlled derivations require non-trivial code transformations on the base operation. Q# allows the developer to ask the compiler to generate the derived versions following general rules for unitary operations. In the relatively rare situation that an operation requires special processing, or if there is a more efficient derived version that the developer can provide using special knowledge, the developer can explicitly specify the derived version.

In Q#, the `Adjoint` and `Controlled` modifiers are used with a base operation to refer to the respective derived operations. For instance, if `SomeUnitary` is an operation that has an adjoint, `Adjoint SomeUnitary` is the derived operation that is the adjoint of that operation. The modifiers may be applied to operation-valued variables, as well, which is critical for supporting higher-level operations such as phase estimation.

Beyond Circuits

Q# supports general classical control flow during the execution of an algorithm. For instance, the loop required for probabilistic algorithms such as Grover search can easily be expressed in Q#, rather than having to return to the classical driver to test whether the result satisfies the oracle and rerunning if not.

Q# supports rich classical computation as well as quantum operations. This allows clean expression of adaptive algorithms such as the random walk phase estimation operation in the non-commercial library. Such algorithms are difficult to express directly in the circuit model of a fixed sequence of quantum gates.

These features imply that the execution runtime must be capable of handling significant runtime variation in gate sequences. Ensuring this capability is a key part of Microsoft’s quantum full-stack architecture.

Coming Soon

Some topics we’re planning:

Quantum katas: learning quantum computing with Q#
What’s new in 0.3
Why do we care about quantum computing?
Drill down: Qubits in Q#
Drill down: The new Hamiltonian simulation library
Inside the Q# compiler

Please let us know in comments if there are specific topics you’d like us to cover!

Useful Links

Alan Geller, Software Architect, Quantum Software and Applications @ageller
Alan Geller is a software architect in the Quantum Architectures and Computation group at Microsoft. He is responsible for the overall software architecture for Q# and the Microsoft Quantum Development Kit, as well as other aspects of the Microsoft Quantum software program.