December 2nd, 2020

Inside the Quantum Katas, part 1

Mariia Mykhailova
Principal Software Engineer

This post is part of the Q# Advent Calendar 2020. Check out the calendar for more great posts!

If you’re reading this blog post, you probably have heard of the Quantum Katas – our collection of tutorials and programming exercises that help one learn quantum computing via quantum programming. (If you haven’t, check them out – I’ve heard great feedback about them 😊)

The Katas are about two and a half years old, and I’ve written about them before once or twice – from the first overview of the project and the summary of its first year in public to its part in this year’s Hacktoberfest celebration (we got 23 pull requests from 11 different folks, 8 of them first-time contributors!)

Oddly enough, I’ve never written about the internal workings of the katas or their most important component – the testing harnesses that provide the learner immediate feedback on their solutions. Testing quantum programs is an interesting topic, very different from testing classical code in some respects and quite similar to it in others. Let’s see how we build the Quantum Katas and how we test them.

Anatomy of a task

Each kata is a sequence of individual tasks, and each task consists of several pieces working in concert.

  • The task.
    This is the “frontend” of the task, the part where the user spends most of their time. It includes the description of the task (what needs to be accomplished, the format of inputs and outputs, examples and any restrictions imposed on the solution) and the signature of the Q# operation that the learner needs to implement.
    A typical kata will have two “frontends” – in the Tasks.qs file (used when solving the kata in Visual Studio or VS Code) and in the Jupyter Notebook. The task description and, most importantly, the operation signature of the task should always match in both cases, though the Jupyter Notebook “frontend” certainly looks much fancier!
  • The reference solution.
    ReferenceImplementation.qs file contains the “reference” solutions to all tasks – correct solutions to the tasks that will pass the tests. Sometimes these solutions play a significant role in the testing of the learner’s code, and one can always turn to them to get an idea about the expected approach to the task. That last goal, though, is often better served by the workbooks – the worked-out explanations of the tasks and their implementation in code that are included in many katas.
  • The testing harness.
    Finally, Tests.qs file contains the code that verifies whether the learner’s code is correct. It is implemented as a collection of unit tests, one per task, that pass if the learner filled in the right code to solve the task and fail otherwise. (This means that when you start solving the kata in VS or VS Code, all tests are failing – a somewhat scary set up!)
    The Jupyter Notebook “frontend” doesn’t support unit tests, so the testing harness is invoked using the %kata magic command included in the code cell that contains the task operation.

Testing the solutions: what, not how

The most important part of developing a new task is creating the testing harness for it. When we consider the ways to test a solution, we follow one main principle:

test what the solution does, not how it does it.

In other words, we test whether the solution accomplishes the given task, not the exact path it takes to do that.

Consider, for example, the following task: given a pair of qubits in the |00⟩ state, prepare one of the Bell states |Φ⁻⟩ = 1/√2 (|00⟩ – |11⟩). There are a lot of ways to do this – start by preparing a different Bell state |Φ⁺⟩ = 1/√2 (|00⟩ + |11⟩) and then adjust the relative phase of the second term by applying the Z gate to one of the qubits, or apply an X gate to one of the qubits before applying the Hadamard gate to it and using it as a control in CNOT gate – the possibilities are endless! At the same time we don’t really care which path to the solution the learner takes – the idea of the task is to practice using Pauli gates and the CNOT gate to prepare entangled states, and if the end result is the right superposition state, the task achieved its goal.

Of course, sometimes the goals of the task are more sophisticated than this. The first time we hosted a workshop using the prototype of the DeutschJozsaAlgorithm kata, one of the attendees went ahead and implemented the classical solution to the problem solved by the Deutsch-Jozsa algorithm (figuring out whether the given function is constant or balanced), applying the quantum oracle to basis states to evaluate the classical function. This is a valid classical approach (and later we added it as a separate task to the ExploringDeutschJozsaAlgorithm tutorial), but not the quantum algorithm we’re looking for! We had to add an extra check to count the number of times the given oracle is applied in the learner’s solution, and if it is more than once, fail the test.

Over the years we have accumulated quite a box of tricks for testing different kinds of programming tasks, and I’ll share some of them in the second part of this post. For now, let’s take a look at the simplest example (that is also historically the first type of tasks developed for the Katas) – testing a state preparation task.

Example: preparing a quantum state

Let’s use our Bell state preparation task again: given a pair of qubits in the |00⟩ state, prepare the state |Φ⁻⟩ = 1/√2 (|00⟩ – |11⟩).

The task

First, how does the task signature look like? We want the task to take a pair of qubits as a parameter and have no return – the result of the task is the change in the qubits’ state. The Q# signature that matches this is

operation PrepareBellStatePhiMinus (qs : Qubit[]) : Unit {
    // ...
}

This is it! In the task we leave the operation body blank and mark the part that needs to be filled by the learner with a // ... comment.

The reference solution

To get the reference solution, we just copy the task signature, rename the operation and fill in the code that solves the task.

operation PrepareBellStatePhiMinus_Reference (qs : Qubit[]) : Unit {
    H(qs[0]);
    CNOT(qs[0], qs[1]);
    Z(qs[0]);
}

The testing harness

Now, how can we test this kind of a task?

Remember that Q# doesn’t give us direct programmatic access to the amplitudes of the quantum state vector, since that doesn’t match the physical reality of a quantum-mechanical system. Instead, it offers a variety of operations in the Microsoft.Quantum.Diagnostics namespace that can only be applied when running the code on a simulator – which is the case for the Katas – and allow to provide diagnostics on the simulator and to check various assertions about its state. In our case we’ll run the test on the full state simulator and use AssertAllZero operation which passes if all qubits of the given array are in the |0⟩ state and fails otherwise.

At this point an attentive reader should ask “Wait, we are given the |00⟩ state, we’re not trying to prepare it, are we?” We’ll need to do one more step before we can use this assertion to implement our test, and this step involves the reference solution for the task and the very convenient ability of Q# compiler to generate adjoints of quantum operations automatically.

More specifically, we have the learner’s solution that implements a transformation U, and we need to check whether it transforms the initial |00⟩ state to the required state |Φ⁻⟩:

U|00⟩ =|Φ⁻⟩

We also know that our reference solution R performs this transformation correctly:

R|00⟩ =|Φ⁻⟩

Let’s apply adjoint of our reference solution R† to both parts of the check we want to do:

R†U|00⟩ = R†|Φ⁻⟩ = R†R|00⟩ = |00⟩

We see that if we start with the |00⟩ state and apply first the learner’s solution and then the adjoint of the reference solution, we’ll end up with the |00⟩ state again if and only if the learner’s solution did indeed prepare the |Φ⁻⟩ state. Importantly, the results of this check don’t depend on the path the solution took to arrive to the required state.

The code implementation of this test ends up being shorter than the explanation of the logic behind it: once we add “is Adj” to the signature of the reference implementation to enable automatic adjoint generation,

@Test("QuantumSimulator")
operation TestPrepareBellStatePhiMinus () : Unit {
    use qs = Qubit[2];
    PrepareBellStatePhiMinus(qs);
    Adjoint PrepareBellStatePhiMinus_Reference(qs);
    AssertAllZero(qs);
}

This testing harness can be improved further. For example, the error message it produces, “Qubit in invalid state.”, is not very helpful for the learner. The Superposition kata makes an extra effort to output the desired superposition state and the state prepared by the learner’s solution (using another convenient diagnostic operation DumpMachine) before comparing these states.

In the next episode

In part 2 of this blog post we’ll take a look at other types of programming tasks offered in the Quantum Katas and the tools we use to test them. Stay tuned!

Category
Q#Tutorials

Author

Mariia Mykhailova
Principal Software Engineer

Mariia Mykhailova is a principal software engineer at the Advanced Quantum Development team at Microsoft. She works on developing software for fault-tolerant quantum computation. Mariia is also a part-time lecturer at Northeastern University, teaching Introduction to Quantum Computing since 2020, and the author of O’Reilly book “Q# Pocket Guide”. In her spare time, she writes problems for programming competitions and creates puzzles.

2 comments

Discussion is closed. Login to edit/delete existing comments.

  • Jay Lauriano

    Can someone explain the point of devoting themselves to learning Q# or X++ when quantum computers aren’t even in the public mainstream and won’t be for many years? Why bother? Where’s the money in it?

    • Mariia MykhailovaMicrosoft employee Author

      If someone is looking for quick payoff, devoting themselves to learning quantum computing is indeed not the most certain way to get it. I think of it as a long-term part-time investment instead.

      On one hand, there is a growing number of jobs in the domain - both in research and in accompanying software development (a lot of the latter didn't exist four years ago when I joined the field). If you'd like to work...

      Read more