Inside the Quantum Katas, part 2: testing quantum programs

Mariia Mykhailova

In the previous blog post we looked at the structure of the Quantum Katas – programming exercises for learning quantum computing – using a state preparation task as an example. We have seen that developing the testing harness that provides immediate feedback for the learner’s solution is an essential part of creating a task, sometimes even more challenging than developing the task itself.

In this blog post we will continue the deep dive into testing different types of quantum programming tasks.

Example 1: Implementing a unitary transformation

Tasks that ask the learner to implement a given unitary transformation – an operation on qubits that changes their state – are frequently seen in the katas. Quantum oracles and more complicated operations such as quantum Fourier transform or quantum arithmetic are just a few examples that justify their popularity.

Verifying that the learner’s solution is correct can be done by comparing it to the reference implementation using the AssertOperationsEqualReferenced library operation. This operation relies on the Choi–Jamiołkowski isomorphism to reduce the comparison of two unitaries to a comparison of a quantum state to the all-zeros state. Let’s take a quick look at how it works for the small case of single-qubit unitaries (for unitaries acting on multiple qubits the principle is the same but the math is bulkier).

1. We will start by preparing an entangled state |Φ⁺⟩ = 1/√2 (|00⟩ + |11⟩).
2. Apply the learner’s solution that implements the unitary U to the second qubit:
1/√2 (|0⟩ ⊗ U|0⟩ + |1⟩ ⊗ U|1⟩)
This state carries all information about the effects of the unitary on all basis states, and thus, all the information about the unitary itself (up to a global phase).
3. Now apply the adjoint of the reference implementation R to the second qubit:
1/√2 (|0⟩ ⊗ R†U|0⟩ + |1⟩ ⊗ R†U|1⟩)
The trick turns out to be similar to the one we’ve seen when testing the state preparation tasks. If the unitaries R and U are the same, their effects on the state are going to cancel out, and we’ll get the state |Φ⁺⟩ with which we started. If the unitaries are different, their effects either on the |0⟩ state or on the |1⟩ state will not cancel out, and we’ll end up with a different state.
4. To check whether we ended up with the original state |Φ⁺⟩, we can use the same trick again: apply the adjoint of the routine used to prepare it from the |0⟩ state and compare the result to the |0⟩ state.

With all these steps hidden away in the library operation, the actual test code ends up very short. Here is the testing harness from the first task of the MultiQubitGates tutorial:

```@Test("QuantumSimulator")
operation TestCompoundGate () : Unit {
AssertOperationsEqualReferenced(3, CompoundGate, CompoundGate_Reference);
}```

Example 2: Identifying a quantum state

The Measurements kata offers tasks which give the learner qubits in one of two or more possible orthogonal states (for example, |0⟩ or |1⟩) and ask to figure out which state it was. This type of task can be tested as follows:

1. Pick one of the possible input states randomly.
2. Prepare the qubits in this state and pass them to the solution.
3. Compare the solution’s answer with the state we picked to see if it’s a match.
4. Repeat the steps 1-3 several times to reduce the probability that the solution guessed the state accidentally. This also allows us to gather statistics on the incorrect guesses to help the learner identify their mistakes, such as confusing the indices of states returned or making randomized guesses instead of deterministic.

The testing harness complete with error tracking can get somewhat lengthy; you can find the complete example from the Measurements kata here.

This testing approach can be used for other types of tasks as well. The second part of the Measurements kata offers tasks in which the solution has to identify the state with a certain probability or without errors but with some “unknown state” verdicts allowed. A more recent DistinguishUnitaries kata asks the learner to figure out which of the two unitaries they are given by designing the right experiment.

Sometimes we care not only about the results produced by the solution but also about the operations used by it. Here are several examples of such tasks:

Some of these needs can be addressed by the library operation AllowAtMostNCallsCA. However, the Quantum Katas use a more sophisticated and more flexible approach: the CounterSimulator. It is a custom simulator built as an extension to the full state simulator provided with the QDK, and it counts various resources used during the “normal” program simulation. Developing a simulator with resource counting capabilities is out of scope for this blog post, but since it exists (and is shipped as part of the Microsoft.Quantum.Katas NuGet package), the testing harnesses can use its methods to get the necessary resource counts.

Here is the testing harness for the Deutsch-Jozsa algorithm which runs the algorithm on the given oracle, checks that its result is correct and then checks that the solution doesn’t overuse the oracle calls:

```operation TestDJAlgorithm (N : Int, oracle : (Qubit[], Qubit) => Unit, expected : Bool, msg : String) : Unit {
EqualityFactB(DJ_Algorithm(N, oracle), expected, msg);
let nu = GetOracleCallsCount(oracle);
Fact(nu <= 1, \$"You are allowed to call the oracle at most once, and you called it {nu} times");
}```

Similarly, sometimes we care about the number of auxiliary qubits allocated by the solution. The simplest examples are tasks that ask the learner to implement a phase oracle for a certain function. If the task aims to teach phase manipulation, it might prohibit the solution allocating extra qubits to render implementing a marking oracle and then using the phase kickback trick impossible.

What will the testing harness look like in this case? We can validate that the solution implements the right unitary using the AssertOperationsEqualReferenced operation from the example 1. On top of that, we can use another library operation, AllowAtMostNQubits, to check that AssertOperationsEqualReferenced allocates exactly 2N qubits, where N is the number of qubits on which the oracle acts. (Why 2N? Remember that AssertOperationsEqualReferenced uses 2N qubits to compare the unitaries that act on N qubits. If the reference solution does not allocate extra qubits, any qubits allocated on top of 2N must come from the learner’s solution!)

Here is the testing harness used for the task:

```@Test("QuantumSimulator")
operation TestPhaseOracle () : Unit {
let N = 3;
within {
AllowAtMostNQubits(2*N, "You are not allowed to allocate extra qubits");
} apply {
AssertOperationsEqualReferenced(N, PhaseOracle, PhaseOracle_Reference);
}
}```

Conclusion

These testing patterns are the ones most frequently used in the Quantum Katas. There are plenty of one-off tasks that require more elaborate testing logic (the whole counting multi-qubit gates functionality of the CounterSimulator is only used in one task!), but these should help you get started with testing your own quantum code.

If you’re looking for more advanced scenarios of code verification, see the paper “A Resource Estimation and Verification Workflow in Q#” by Mathias Soeken et al.