microsoft/quantumkatas

Tutorials and programming exercises for learning Q# and quantum computing

DEPRECATION NOTICE

We are modernizing the quantum katas experience. Please visit https://quantum.microsoft.com/experience/quantum-katas to try the new online Azure Quantum katas experience, with integrated assistance from Copilot in Azure Quantum.

For the Modern QDK repository, please visit Microsoft/qsharp.

For more information about the Modern QDK and Azure Quantum, visit https://aka.ms/AQ/Documentation.

Introduction

The Quantum Katas are a collection of self-paced tutorials and programming exercises to help you learn quantum computing and Q# programming.

Each kata is a separate set of exercises that includes:

• A sequence of tasks progressing from easy to hard. Each task requires you to fill in some code. The first task might require just one line, and the last one might require rather complicated code.
• A testing framework that sets up, runs, and validates your solutions. Each task is covered by a unit test which initially fails. Once you write the code to make the test pass, you can move on to the next task.
• Links to quantum computing and Q# reference material you might need to solve the tasks.
• Hints, reference solutions and detailed explanations to help you if you're stuck.

The Quantum Katas also include tutorials that introduce the learner to the basic concepts and algorithms used in quantum computing, starting with the necessary math (complex numbers and linear algebra). They follow the same pattern of supplementing the theory with Q# demos and hands-on programming exercises.

Table of contents

• Learning path
• Run the katas and tutorials online
• Run the katas locally
  • Quantum Development Kit installation
  • Download the Quantum Katas
  • Run a kata as a Jupyter Notebook
  • Run a kata as a Q# project
  • Run kata tests
  • Run katas locally with Docker
• Contributing
• Code of Conduct

Learning path

Here is the learning path we suggest you to follow if you are starting to learn quantum computing and quantum programming. Once you're comfortable with the basics, you're welcome to jump ahead to the topics that pique your interest!

Quantum Computing Concepts: Qubits and Gates

• Complex arithmetic (tutorial). Learn about complex numbers and the mathematics required to work with quantum computing.
• Linear algebra (tutorial). Learn about vectors and matrices used to represent quantum states and quantum operations.
• The qubit (tutorial). Learn what a qubit is.
• Single-qubit gates (tutorial). Learn what a quantum gate is and about the most common single-qubit gates.
• Basic quantum computing gates. Learn to apply the most common gates used in quantum computing.
• Multi-qubit systems (tutorial). Learn to represent multi-qubit systems.
• Multi-qubit gates (tutorial). Learn about the most common multi-qubit gates.
• Superposition. Learn to prepare superposition states.

Quantum Computing Concepts: Measurements

• Single-qubit measurements (tutorial). Learn what quantum measurement is and how to use it for single-qubit systems.
• Multi-qubit measurements (tutorial). Learn to use measurements for multi-qubit systems.
• Measurements. Learn to distinguish quantum states using measurements.
• Distinguish unitaries. Learn to distinguish unitaries by designing and performing experiments with them.
• Joint measurements. Learn about using joint (parity) measurements to distinguish quantum states and to perform state transformations.

Q# and Microsoft Quantum Development Kit Tools

• Visualization tools (tutorial). Learn to use the various tools for visualizing elements of Q# programs.

Simple Algorithms

• Random number generation (tutorial). Learn to generate random numbers using the principles of quantum computing.
• Teleportation. Implement standard teleportation protocol and its variations.
• Superdense coding. Implement the superdense coding protocol.

Quantum Oracles and Simple Oracle Algorithms

• Quantum oracles (tutorial). Learn to implement classical functions as equivalent quantum oracles.
• Marking oracles. Practice implementing marking oracles for a variety of classical functions.
• Exploring Deutsch and Deutsch–Jozsa algorithms (tutorial). Learn to implement classical functions and equivalent quantum oracles, and compare the quantum solution to the Deutsch–Jozsa problem to a classical one.
• Deutsch–Jozsa algorithm. Learn about quantum oracles which implement classical functions, and implement Bernstein–Vazirani and Deutsch–Jozsa algorithms.
• Simon's algorithm. Learn about Simon's algorithm.

Grover's Search Algorithm

• Implementing Grover's algorithm. Learn about Grover's search algorithm and how to write quantum oracles to use with it.
• Exploring Grover's search algorithm (tutorial). Learn more about Grover's search algorithm, picking up where the Grover's algorithm kata left off.
• Solving SAT problems using Grover's algorithm. Explore Grover's search algorithm, using SAT problems as an example. Learn to implement quantum oracles based on the problem description instead of a hard-coded answer. Use Grover's algorithm to solve problems with an unknown number of solutions.
• Solving graph coloring problems using Grover's algorithm. Continue the exploration of Grover's search algorithm, using graph coloring problems as an example.
• Solving bounded knapsack problem using Grover's algorithm. Learn how solve the variants of knapsack problem with Grover's search.

Tools and Libraries/Building up to Shor's Algorithm

• Quantum Fourier transform. Learn to implement quantum Fourier transform and to use it to perform simple state transformations.
• Phase estimation. Learn about phase estimation algorithms.

Entanglement Games

• CHSH game.
• GHZ game.
• Mermin-Peres magic square game.

Reversible Computing

• Truth tables. Learn to represent and manipulate Boolean functions as truth tables and to implement them as quantum operations.
• Ripple-carry adder. Build a ripple-carry adder on a quantum computer.

Miscellaneous

• BB84 protocol. Implement the BB84 key distribution algorithm.
• Bit-flip error correcting code. Learn about a 3-qubit error correcting code for protecting against bit-flip errors.
• Unitary patterns. Learn to implement unitaries with matrices that follow certain patterns of zero and non-zero elements.
• Quantum classification (tutorial). Learn about circuit-centric classifiers and the quantum machine learning library included in the QDK.

For a Q# programming language quick reference sheet, see Q# Language Quick Reference.

Run the katas and tutorials online

The Quantum Katas are now available as Jupyter Notebooks online! See index.ipynb for the list of all katas and tutorials, and instructions for running them online.

Note that mybinder.org is running with reduced capacity, so getting a virtual machine and launching the notebooks on it might take several attempts. While running the Katas online is the easiest option to get started, if you want to save your progress and enjoy better performance, we recommend you to choose the local setup option.

Run the katas locally

Quantum Development Kit Installation

To use the Quantum Katas locally, you'll need the Quantum Development Kit, available for Windows 10, macOS, and Linux. If you don't already have the Quantum Development Kit installed, see the install guide for the Quantum Development Kit.

If you want to run the katas and tutorials locally as Jupyter Notebooks:

1. Follow the steps in the QDK install guide for Python and the QDK install guide for Jupyter Notebooks.
2. Several tutorials require installing additional Python packages:
   • "Complex arithmetic" and "Linear algebra" require the pytest package.
   • "Exploring Grover's search algorithm" requires the matplotlib package.
   • "Quantum classification" requires matplotlib and numpy packages.

Refer to Updating IQ# kernel for updating IQ# kernel to a new version with monthly QDK releases.

If you want to run the katas and tutorials locally as Q# projects:

Follow the steps in the QDK install guide for Visual Studio, Visual Studio Code or other editors.

Running the Q# projects of the Katas locally requires downloading and installing the .NET 6.0 SDK. You can do this even if you have another .NET version installed, since multiple versions are supported side-by-side.

Since Visual Studio 2019 does not support .NET 6.0 projects, you will need to upgrade to Visual Studio 2022 and install the corresponding Microsoft Quantum Development Kit extension.

Download the Quantum Katas

If you have Git installed, clone the Microsoft/QuantumKatas repository:

$ git clone https://github.com/Microsoft/QuantumKatas.git

TIP
Both Visual Studio 2022 and Visual Studio Code make it easy to clone repositories from within your development environment. For details, see the Visual Studio and Visual Studio Code documentation.

If you don't have Git installed, download the katas from https://github.com/Microsoft/QuantumKatas/archive/main.zip.

Run a kata as a Jupyter Notebook

The best way to run the katas as Jupyter Notebooks is to navigate to the root folder of the repository and to open index.ipynb using Jupyter:

$ cd QuantumKatas/
$ jupyter notebook index.ipynb

This will open the notebook that contains a list of all katas and tutorials, and you will be able to navigate to the one you want using links.

NOTE: This will start Jupyter Notebooks server in the same command line window you used to run the command. If you want to keep using that window for navigation, you can launch Jupyter Notebooks server in a new window using the following commands:

For Windows:

$ cd QuantumKatas/
$ start jupyter notebook index.ipynb

For Ubuntu:

$ cd QuantumKatas/
$ gnome-terminal -- start jupyter notebook index.ipynb

You can also open an individual notebook directly, but this might render internal links invalid:

$ cd QuantumKatas/tutorials/ComplexArithmetic
$ jupyter notebook ComplexArithmetic.ipynb

Run a kata as a Q# project

Each kata is in its own directory as a self-contained Q# project, solution and Jupyter Notebook triplet. For instance, the BasicGates directory structure is:

QuantumKatas/
  BasicGates/
    README.md                  # Instructions specific to this kata.
    .vscode/                   # Metadata used by Visual Studio Code.
    BasicGates.sln             # Visual Studio solution file.
    BasicGates.csproj          # Project file used to build both classical and quantum code.

    BasicGates.ipynb           # Jupyter Notebook front-end for this kata.
    Workbook_BasicGates.ipynb  # Jupyter Notebook workbook for this kata.

    Tasks.qs                   # Q# source code that you will fill as you solve each task.
    Tests.qs                   # Q# tests that verify your solutions.
    ReferenceImplementation.qs # Q# source code containing solutions to the tasks.

To open the BasicGates kata in Visual Studio 2022, open the QuantumKatas/BasicGates/BasicGates.sln solution file.

To open the BasicGates kata in Visual Studio Code, open the QuantumKatas/BasicGates/ folder. Press Ctrl + Shift + P (or ⌘ + Shift + P on macOS) to open the Command Palette. Type Open Folder on Windows 10 or Linux or Open on macOS.

TIP
Almost all commands available in Visual Studio Code are in the Command Palette. If you get stuck, press Ctrl + Shift + P (or ⌘ + Shift + P on macOS) and start typing to search through all available commands.

You can also launch Visual Studio Code from the command line:

$ code QuantumKatas/BasicGates/

Run kata tests

Once you have a kata open, it's time to run the tests using the following instructions. Initially all tests will fail. Don't panic! Open Tasks.qs and start filling in the code to complete the tasks. Each task is covered by a unit test. Once you fill in the correct code for a task, rebuild the project and re-run the tests, and the corresponding unit test will pass.

Visual Studio 2022

1. Build the solution.
2. From the main menu, open Test Explorer (Test > Windows) and select Run All to run all unit tests at once.
3. Work on the tasks in the Tasks.qs file.
4. To test your code changes for a task, rebuild the solution and re-run all unit tests using Run All, or run just the test for that task by right-clicking the test and selecting Run Selected Tests.

Visual Studio Code

1. Press Ctrl + ` (or ⌘ + ` on macOS) to open the integrated terminal. The terminal should open to the kata directory. If it doesn't, navigate to the folder containing the *.csproj file for the kata using cd command.
2. Run dotnet test in the integrated terminal. This should build the kata project and run all of the unit tests. All of the unit tests should fail.
3. Work on the tasks in the Tasks.qs file.
4. To test your code changes for a task, from the integrated terminal run dotnet test again.

For convenience, a tasks.json configuration file exists for each kata. It allows Visual Studio Code to run the build and test steps from the Command Palette. Press Ctrl + Shift + P (or ⌘ + Shift + P on macOS) to open the Palette and type Run Build Task or Run Test Task and press Enter.

Run katas locally with Docker

You can use the included Dockerfile to create a docker image with all the necessary tools to run the katas from the command line or Jupyter.

1. Install Docker.
2. Build the docker image and tag it katas:

docker build -t katas .

3. Run the image in the container named katas-container with interactive command-line and redirect container port 8888 to local port 8888 (needed to run Jupyter):

docker run -it --name katas-container -p 8888:8888 katas /bin/bash

4. From the same command line that you used to run the container, run the C# version of the BasicGates kata:

cd ~/BasicGates/
dotnet test

5. Start a Jupyter Notebook within the image for the BasicGates kata:

cd ~/BasicGates/ && jupyter notebook --ip=0.0.0.0 --no-browser

6. Once Jupyter has started, use your browser to open the kata in notebook format. You will need a token generated by Jupyter when it started on the previous step:

http://localhost:8888/notebooks/BasicGates.ipynb

To exit a docker container without killing it (daemon mode), press Ctrl+P, Ctrl+Q

To re-enter the existing katas-container (in daemon mode):

docker attach katas-container

Once you're done, remove the katas-container:

docker rm --force katas-container

Contributing

This project welcomes contributions and suggestions. See How Can I Contribute? for details.

Code of Conduct

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

quantumkatas's Issues

Question about Task 2.11 (Superposition of two bit strings)

Hi,

I've come up with a solution alternative to the one suggested in the reference, which - if it worked - would probably be conceptually simpler. The idea is that, given the qubit register and two boolean registers from the outside (in this case, from the test), I attach one additional qubit, in a way extending my quantum register by one. I then apply Hadamard gate to that qubit, essentially obtaining the following superposition:

1/sqrt(2) (|0>|0>...|0> + |1>|0>...|0>)

where I assume that the first qubit is my additional one. I then iterate through the first classical register and whenever its item is true I apply a CNOT between the 0th and ith qubits, thus setting one half of the superposition. I then negate the first qubit with X and repeat the procedure for the second classical register. I finally discard my additional qubit and I'm left with my resultant qubit register.

Below is my take on implementing an operation according to the description above:

operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Unit {
        // ...
        using (q = Qubit()) {
            H(q);
            for (i in 0..Length(qs)-1) {
                if (bits2[i]) {
                    CNOT(q, qs[i]);
                }
            }
            X(q);
            for (i in 0..Length(qs)-1) {
                if (bits1[i]) {
                    CNOT(q, qs[i]);
                }
            }
            Reset(q);
        }
    }

The thing that puzzles me is that the test suite in QuantumKatas fails to pass. But I moved ahead and tried to simulate a simplified scenario, in which I specify the desired parameters of the superposition and then measure multiple repetitions. If I do it that way, the mechanism seems to work. Below is a test operator, which calls the one above in a for loop and gathers statistics:

operation TestTwoBitstringSuperposition (count: Int) : Int[] {
        mutable arr = new Int[4];
        using (q = Qubit[2]) {
            for (i in 1..count) {
                Set(Zero, q[0]);
                Set(Zero, q[1]);
                TwoBitstringSuperposition(q, [true,true], [false,false]);
                let res = [M(q[0]), M(q[1])];
                if (res[0] == Zero && res[1] == Zero) {
                    set arr[0] = arr[0] + 1;
                } elif (res[0] == Zero && res[1] == One) {
                    set arr[1] = arr[1] + 1;
                } elif (res[0] == One && res[1] == Zero) {
                    set arr[2] = arr[2] + 1;
                } elif (res[0] == One && res[1] == One) {
                    set arr[3] = arr[3] + 1;
                }
            }
            Set(Zero, q[0]);
            Set(Zero, q[1]);
        }
        return arr;
    }

It gives me sensible output, differing according to how I specify the boolean registers. I'm having trouble debugging the provided tests, so I'd like to ask you for help either making it work, or pointing out how my approach is wrong. Thanks!

Improve Simon's algorithm kata

Simon's algorithm kata differs from the others in that Simon's algorithm has non-trivial classical processing involved, but the tasks of the kata cover only the (relatively simple) quantum part of the algorithm. This makes it less useful than it could be.

If we want to keep it as a C# project, there will be several steps to improving it:

• Add C# tasks to cover classical processing in Simon's algorithm.
  They can be part of the same Q# project, it will just have several Tasksfiles.
• Convert Q# tasks to Q# Notebook.
  This includes investigating whether %kata magic command can invoke C# tests with the updated Q# code.
• Convert C# tasks to C# Notebook.
  There are several implementations of C# kernel for Jupyter, we need to pick one and use it.

It also could be that the best way to improve this kata is to convert it into Python.

I won't get to this in the next several months; if anybody is interested in picking this up, please let me know!

Possible bug in LinearAlgebra testing module

I had trouble with LinearAlgebra Exercise 8 after submitting my code

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-17-ec126a7665cf> in <module>
      2 
      3 @exercise
----> 4 def is_matrix_unitary(a : Matrix) -> bool:
      5     n = len(a)
      6     print(n)

~/Projects/QuantumKatas/tutorials/LinearAlgebra/testing.py in exercise(fun)
      7 # Exercise decorator, specifying that this function needs to be tested
      8 def exercise(fun):
----> 9     tests[fun.__name__](fun)
     10     return fun
     11 

~/Projects/QuantumKatas/tutorials/LinearAlgebra/testing.py in is_matrix_unitary_test(fun)
    425         if i > 0:
    426             --i
--> 427             a = edge_unitary_matrices[i]
    428         elif result:
    429             a = gen_unitary_matrix()

IndexError: list index out of range

Notice line 426 --i does not decrement the value of i in Python:

$ python3
Python 3.7.4 (default, Sep  7 2019, 18:27:02)
[Clang 10.0.1 (clang-1001.0.46.4)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> i = 2
>>> --i
2
>>> i
2
>>>

edge_unitary_matrices has 2 elements https://github.com/microsoft/QuantumKatas/blob/master/tutorials/LinearAlgebra/testing.py#L405.

Math.ArcSin returns NaN

I am trying to solve the Measurement Task 1.8 AllZerosOrWState. As far as I can tell, I solved correctly, but the test fails. (Actually pasting the solution from referenceImplementation.qs still results in a failing test)

Debugging the test, I noticed a ArgumentOutOfRange exception for the angle returned by ArcSin(). It returns NaN. I tried some more ratios and this is the result:

I expected a double in all cases.

Issue with task 1.6* Phase change of the "Basic.Gates" kata

Hello,
Pertaining to task 1.6* Phase change of the "Basic.Gates" kata:

// Task 1.6*. Phase change
    // Inputs: 
    //     1) A qubit in state β|0⟩ + γ|1⟩.
    //     2) Angle alpha, in radians, represented as Double
    // Goal:  Change the state of the qubit as follows:
    //        If the qubit is in state |0⟩, don't change its state.
    //        If the qubit is in state |1⟩, change its state to exp(i*alpha)|1⟩.
    //        If the qubit is in superposition, change its state according to the effect on basis vectors.

The reference solution Rz(alpha, q); doesn't seem to be correct, since:
Rz(alpha) |0> = exp(-i * alpha/2) |0>
Rz(alpha) |1> = exp(i * alpha/2) |1>
Please check.

Convert the Katas to Jupyter Notebook format

The first batch of the katas is converted to Notebook format. We'll need to convert the rest of the katas, so that all of them are available both as Notebooks and as regular projects.

This is going to take some work, so I'd appreciate some help!

• Basic Gates
• Superposition
• Measurements
• Joint Measurements
• Teleportation
• Superdense Coding
• Deutsch-Jozsa Alrorithm
• CHSH Game
• GHZ Game
• Mermin-Peres magic square game
• Grover's Algorithm
• Solving SAT problems using Grover's algorithm
• Solving graph coloring problems using Grover's algorithm
• BB84 protocol
• Phase Estimation
• Bit-flip error correction code
• Ripple-carry adder
• Unitary patterns

Failing Tests

All Tests fail for any Katas in a system that runs fine with the erstwhile Quantum repository.

Add addition/subtraction modulo 2ᴺ tasks to RippleCarryAdder kata

RippleCarryAdder offers great coverage of traditional addition/subtraction operations; operations modulo 2ᴺ are rather similar, reusing a lot of the same primitives, so it makes sense to add a section covering modular operations. Addition modulo some other number would probably be out of scope for this change - if we want to develop that direction, we should branch it off to a separate kata.

Wrong test name in Teleportation.ipynb

To get Teleportation.ipynb to work, change ‘%kata T14_StandardTeleport_Test’ to ‘%kata T14_Teleport_Test’

Cryptography Kata

Hi.

I'd like to create a kata on quantum cryptography, is it alright to get that put on the roadmap? Intend to introduce the coder to a quantum key distribution scheme, show how it could be used to create a one-time pad, and have them test whether the line is being eavesdropped on when generating the key.

Thanks,
Daniel

DeutschJozsaAlgorithm tutorial: improve messaging for code samples

In this tutorial the code cells alternate: some of them are kata-style tasks (are covered with tests and output "Success!" if solved correctly) and some of them (examples of oracles) are demo-style (define some Q# operations without running them, so output the names of the defined operations).

This difference can be confusing for some learners, especially if they tried some katas before that tutorial and got used to the "Success!" output. It would be nice to do one of the two things:

1. either have some wording before the samples saying something like "these are just code samples, you don't have to modify the code and they are not covered by tests"
2. or add some tests to cover them, so that they output "Success!" as well (this will also require splitting the cell with classical oracles into several). We could have tests for classical functions that actually print the outputs for all inputs, so that it's more visual.

DeutschJozsaAlgorithm: Description of task 4.1

Where it says: Σᵢ (rᵢ xᵢ + (1 - rᵢ)(1 - rᵢ)) should be Σᵢ (rᵢ xᵢ + (1 - rᵢ)(1 - xᵢ))

Intellisense support is disabled when using the .code-workspace file

In order for intellisense to be fully activated, the workspace folder needs to be the top level katas folder. Maybe this can be configured in the file?

Possible incorrect test data in kata SuperpositionOneMeasurement

I've been playing around, trying to simplify my solution to kata SuperpositionOneMeasurement in the Measurements section. The essential part of the reference implementation is the function FindFirstSuperpositionDiff_Reference, which detects at which position in the bit arrays occurs a "total difference", i.e. one has only true values and the other false or vice versa. Building on the assumption that bits1 and bits2 are isomorphic (M ⨯ N, as per the description) I came up with a simplified version of the function:

function findDiscrepancy(bits1: Bool[][], bits2: Bool[][], qs: Qubit[]) : Int {
        for (q in 0..Length(qs)-1) {
            mutable n1 = 0;
            mutable n2 = 0;
            for (s in 0..Length(bits1)-1) {
                if (bits1[s][q]) {
                    set n1 += 1;
                }
                if (bits2[s][q]) {
                    set n2 += 1;
                }
            }
            if (MyAbs(n1-n2) == Length(bits1)) {
                return q;
            }
         }
         return -1;
}

When using this function tests started to fail. I investigated this by inserting Message statements and inspecting the lengths of bits1 and bits2 and noticed that there are many cases in which they are different. The original function FindFirstSuperpositionDiff_Reference deals with it by comparing to two different lengths, but with the isomorphism assumption in force, the lengths should be the same, i.e. both functions should be equivalent. Am I missing something?

Create workbooks for the katas/tutorials, part 1

The katas offer a set of programming exercises on quantum computing and reference solutions to them, but we often hear that it would be helpful to have the solutions explained, with the logic steps necessary to arrive from the problem description to the code spelled out. It is especially important for people who go through the katas on their own, without a study group to support them.

To address this, we came up with the idea of "workbooks" - explanations of the solutions to the tasks offered in the katas/tutorials, written in Jupyter Notebook format. You can see the workbook for Superposition kata here - it is still a work in progress, but it already shows the idea of the workbook, the kind of the content it should have and the way it accompanies the kata.

There are several other katas/tutorials that are a great fit for this kind of learning material:

• Complex arithmetic (classical)
• Linear algebra (classical)
• Single-qubit gates
• Multi-qubit systems
• Multi-qubit gates
• Superposition
• Measurements
• Joint measurements
• SolveSATWithGrover
• GraphColoring
• CHSH game
• GHZ game
• Unitary patterns

Other katas might fit this scheme a bit worse - for example, Superdense Coding kata follows the structure of superdense coding algorithm, so a tutorial on the end-to-end algorithm would work better than independent explanations of individual tasks.

Unicode nit

At least BasicGates/Tasks.qs, but probably all of the code files, use a mix of two different Unicode characters to represent the ">"-looking symbol:

+++
⟩ U+27E9 MATHEMATICAL RIGHT ANGLE BRACKET
〉 U+232A RIGHT-POINTING ANGLE BRACKET
+++

At least in my browser, U+232A isn't even the same width as the other characters in the monospace font, which makes the discrepancy really obvious and distracting.
It would be nice to go through and find all instances of U+232A and replace them with U+27E9.

Running jupyter notebook tutorials locally requires installing pytest

Hi thanks for putting together the tutorials!

I got started following https://github.com/microsoft/QuantumKatas#running-the-katas-locally-, the jupyter notebook tutorials use pytest for evaluation but it was not mentioned in the set up process. It was in the Dockerfile though.

Update the katas to use most recent Q# features

Q# evolution introduced some new language features in the past half a year:

• within... apply... statement
• ranges in array slicing
• features introduced in Q# 0.6 listed in this blog post

It makes sense to go through the code and check for places where using the new features would improve code readability. Here is the list of all the katas, with ones that have already gone through the update marked as completed.

• Deutsch–Jozsa algorithm (Notebook Tutorial)
• Exploring Grover's search algorithm (Notebook Tutorial)
• Basic quantum computing gates
• Superposition
• Measurements
• Joint measurements
• Teleportation
• Superdense coding
• Deutsch–Jozsa algorithm
• Simon's algorithm
• Grover's algorithm
• Solving SAT problems using Grover's algorithm
• Solving graph coloring problems using Grover's algorithm
• CHSH game
• GHZ game
• Mermin-Peres magic square game
• BB84 protocol
• Phase estimation
• Bit-flip error correcting code
• Truth tables
• Ripple-carry adder
• Unitary Patterns
• QFT
• Distinguishing Unitaries

Link in GroversAlgorithm to git database sample in readme file needs to include src to work

In this readme file for GroversAlgorithm:
https://github.com/Microsoft/QuantumKatas/tree/master/GroversAlgorithm

The link to the Q#
Q# Samples repository has an implementation of Grover's search.
https://github.com/Microsoft/Quantum/tree/master/Samples/DatabaseSearch
Returns a 404.

I believe it needs to include the src directory.
https://github.com/Microsoft/Quantum/tree/master/Samples/src/DatabaseSearch

Thank you for this great set of sample code.

Update Katas to Be Consistent with Style Guide

It would be nice to update the Katas to follow the style guide and make use of the standard libraries.

Does this plan to grow for a long time

i hope it nice

Issue with task 9 of the "superposition" kata

The output of the reference function TwoBitstringSuperposition_Reference doesn't seem to be correct: For the bit string input b1=(false,true); b2=(true, false), calling DumpRegister on the qubit state returns:
Ids: [1;0;] Wavefunction: 0: 1 0 1: 0 0 2: 0 0 3: 0 0
The way I understand the problem, I would expect an output such as:
Ids: [2;1;] Wavefunction: 0: 0 0 1: 0.707107 0 2: 0.707107 0 3: 0 0
I'd welcome feedback on this issue.

Improve error messaging for the katas that allow it

Several katas could have better error messaging:

• Superposition : the test harness could log the actual state of the system after prep vs the expected state before asserting that they are the same (the change would add state prep and logging using DumpMachine to AssertEqualOnZeroState)
• BasicGates : a similar improvement, but a bit more extra code to write a unified test wrapper (since all tests in it just use AssertOperationsEqualReferenced). Since the actual test compares the unitaries, we might want to add a DumpDiffOnOneInput that would:
  • prepare some nice state like 0.8 |0⟩ + 0.6 |1⟩,
  • apply the reference solution on it,
  • dump the state to get expected state,
  • repeat the sequence for the user's solution.
  • the overall output should look similar to the style used in Superposition kata (as done in #214)
• Measurements : the test harness already reports the number of incorrect classifications; in addition, it can print the states which were misclassified in human-readable format, taking an array of string representations of states as an extra parameter to operations like DistinguishTwoStates_OneQubit and logging the mismatches. We'd have to be careful not to log 50 lines of mismatches, though... Maybe keep track of different kinds of mismatches and report aggregates in the end of the test (e.g., "Classified |0⟩ as |1⟩ 15 times, classified |1⟩ as |0⟩ 21 times")?
• JointMeasurements : same as in Measurements
• DeutschJozsaAlgorithm
• SolveSATWithGrover
• and GraphColoring : use logging approach similar to RippleCarryAdder to produce more readable results for testing oracles on basis states (so that the solver knows which input state is processed incorrectly, not just that there is an error).

There are probably other katas that allow similar improvements - please share the ideas in the comments!

%kata magic doesn't recognize C# tests

PhaseEstimation kata has a test that covers Q# code but is written in C# due to the need to catch and process exceptions thrown by the task. When the kata is approached as Q# project, the test is recognized and executed together with Q# tests just fine. However, when the kata is converted to Jupyter Notebook format, the %kata magic command does not recognize the C# test. This is not unexpected, but ideally we need to come up with a way to execute C# tests from Q# notebooks.

This is related to one of the work items in #138.

Issue with task 1.4

Hello,
I'm confused by the solution of task 1.4 for which all tests seem to be passing: Ry(2.0 * alpha, q);

This article states that Ry(a) = S.H.Rz(a).H.S^T where:

• S=S^T={{1,0},{0,i}}
• H=1/sqrt(2)×{{1,1},{1,-1}}
• Rz(a)={{e^(-i×a/2),0},{0,e^(i×a/2),0}}

The result of such multiplication is Ry(a) = {{cos(a/2),sin(a/2)},{sin(a/2),-cos(a/2)}} (after simplification using Euler's formula) as shown in Wolfram|Alpha.

However, multiplication of the matrix with a qubit doesn't produce the required result.
The expected result is:

• |0〉 » cos(a)×|0〉 + sin(a)×|1〉
• |1〉 » -sin(a)×|0〉 + cos(a)×|1〉
  ... but the actual result of the multiplication is as follows:
• |0〉 » Ry(a×2).{1,0} = {cos(a),sin(a)} = cos(a)×|0〉 + sin(a)×|1〉
• |1〉 » Ry(a×2).{0,1} = {sin(a),-cos(a)} = sin(a)×|0〉 - cos(a)×|1〉

The expectation and actual result differ for input |1) in both signs, yet the tests pass. What am I missing?

Are Q# matrices transposed?

There is a discrepancy between what I see in Q# documentation / QuantumKatas tasks, and all the other documentation all over the Internet. In particular, the gates Y and Ry seem to me to be transposed.

Let's take Y for example. All docs, including Microsoft ones, tell that

Y = [(0, -i); (i, 0)]

(I'm using the line-by-line notation)
Therefore, when you apply it to the base states you get:

Y|0> = 0*|0> - i*|1> = -i*|1>
Y|1> = i*|0> + 0*|1> =  i*|0>

And this is confirmed by other sources. However, in the Q# Quick Language Reference we see:

Y :
|0⟩ →  i|1⟩
|1⟩ → −i|0⟩

which could only happen if you multiply not line by column (as matrix multiplication really works), but column by column.

The same situation with Ry. I could write off that glitch with Y as a typo, but now we have the Katas, particularly — BasicGates, Task 1.4 where we are expected to use the Ry gate. According to all docs I could find,

Ry(α) = [(cos(α/2), -sin(α/2)); (sin(α/2), cos(α/2))]

So if you apply this gate you get:

Ry(2*α)|0> = cos(α)|0> - sin(α)|1>
Ry(2*α)|1> = sin(α)|0> + cos(α)|1>

which is different to what Task 1.4 requires: the sines have inverted sign, again, as if multiplication was performed by columns instead of by lines. Or, as if it used transposed matrix for some reason. And yes, I did check, and the test really accepted the solution Ry(alpha * 2.0, q) and did not accept (Adjoint(Ry))(alpha * 2.0, q) or Ry(- alpha * 2.0, q) which should have given the requested result according to the rules above, instead of Ry.

I'm at a loss here. I admit I'm pretty new to this area, and I have not read that many docs on Q# yet, but what I've read so far never gave me a hint at such a big difference from the common approach. Is it a bug, or have I missed something here?

JointMeasurements: Possibly Incorrect task 2 description

There is literally the same description for Task 1 and Task 2 in the topic of Joint measurements.
At the same time, the solutions in ReferenceImplementation.qs are different and they are not interchangeable for these tasks.

I guess, the incorrect description is for ParityMeasurement, Task 2.

Branch: master
File: \JointMeasurements\Tasks.qs
Line: 43.
See: https://github.com/Microsoft/QuantumKatas/blob/master/JointMeasurements/Tasks.qs#L43

    // Task 2. Parity measurement
    // Input: Two qubits (stored in an array) which are guaranteed to be
    //        either in superposition of states |00⟩ and |11⟩
    //        or in superposition of states |01⟩ and |10⟩.
    // Output: 0 if qubits were in the first superposition,
    //         1 if they were in the second superposition.
    // The state of the qubits at the end of the operation should be the same as the starting state.
    operation ParityMeasurement (qs : Qubit[]) : Int {
        // ...
        return -1;
    }

Expected:

    // Output: 0 if qubits were in the same superposition,
    //         1 if they were in different superposition states.

Actual:

    // Output: 0 if qubits were in the first superposition,
    //         1 if they were in the second superposition.

If this is correct suggestion, I can create a PR for fixing it from my fork or whatever other way.

JointMeasurements - Task 7 - invalid code passes

// Task 7**. Controlled X gate with arbitrary target
// Input: Two qubits (stored in an array of length 2) in an arbitrary
//        two-qubit state α|00⟩ + β|01⟩ + γ|10⟩ + δ|11⟩.
// Goal:  Change the two-qubit state to α|00⟩ + β|01⟩ + δ|10⟩ + γ|11⟩ using only single-qubit gates and joint measurements.
//        Do not use two-qubit gates.
operation ControlledX_General (qs : Qubit[]) : Unit {

    body (...) {
        CNOT(qs[0], qs[1]);
    }

    adjoint self;
}

The above code passes, even though it is written in the docstring that "Do not use two-qubit gates".

Exception Microsoft.Quantum.Simulator.Runtime.dll

Hi,

I followed the instructions here
https://www.microsoft.com/net/download/linux-package-manager/ubuntu18-04/sdk-current
https://docs.microsoft.com/en-us/quantum/install-guide/command-line?view=qsharp-preview

but had issue on various linux versions (you can reproduce with ubuntu:18.04 or centos:7 from dockerhub) with the following error

Unhandled Exception: System.DllNotFoundException: Unable to load shared library 'Microsoft.Quantum.Simulator.Runtime.dll' or one of its dependencies. In order to help diagnose loading problems, consider setting the LD_DEBUG environment variable: libMicrosoft.Quan
tum.Simulator.Runtime.dll: cannot open shared object file: No such file or directory
   at Microsoft.Quantum.Simulation.Simulators.QuantumSimulator.Init()
   at Microsoft.Quantum.Simulation.Simulators.QuantumSimulator..ctor(Boolean throwOnReleasingQubitsNotInZeroState, Nullable`1 randomNumberGeneratorSeed, Boolean disableBorrowing)
   at Microsoft.Quantum.Examples.Teleportation.Program.Main(String[] args) in /Quantum/Samples/Teleportation/Program.cs:line 13

The following SO issue help me fixing it (https://stackoverflow.com/questions/49579153/unable-to-load-dll-microsoft-quantum-simulator-runtime-dll) by installing libgomp1

Maybe there is a way to improve the framework or mention this dependency somewhere in the doc.

Typo in URL of Quirk

In tutorials/SingleQubitGates, the link to Quirk is incorrect https://github.com/microsoft/QuantumKatas/blob/master/tutorials/SingleQubitGates/SingleQubitGates.ipynb?short_path=511e2f8#L262, should be https://algassert.com/quirk.

Update Q# language quick reference to latest syntax

This is a great first issue for somebody familiar with LaTeX but not very familiar with Q#!

The quick reference has last been updated for Q# 0.3, which is almost a year old now. We need to update it to the latest version (currently 0.9) following the Q# language documentation. Some of the things that need to be added/updated, at a glance:

• Add syntax for array element assignment
• Add while loop
• Add syntax for allocating a single qubit and several qubits/qubit registers at once
• Separate a section on user-defined types and add more entries on it
• Add apply-and-reassign statements
• Add conjugation statements (within ... apply ...)
• Shorthand syntax is Adj+Ctl

There are probably other things I'm missing - this is just a list to start with.

Also, the list of resources needs to be reconsidered - for example, we have a lot more Q# repositories now compared to a year ago.

Shor's algorithm kata

Hi,

I've started work on creating a kata for Shor's algorithm. Is it possible to update the corresponding item on the roadmap to show that it's being currently developed?

Thank you!

Explore more graph coloring problems

The latest GraphColoring kata covers one type of graph coloring problems - vertex coloring (assigning colors to graph vertices so that no two vertices connected with an edge are assigned the same color).

There exists a variety of other graph coloring problems (see Wikipedia for a list). For some of them the problem encoding can be made small enough to make it possible to simulate the Grover's algorithm and to solve small but non-trivial problem instances. It would be great to add chapters on solving these problems. Here are several that look the most promising:

• Weak coloring - vertex coloring where every non-isolated vertex has at least one neighbor with a different color.
• Sum coloring - vertex coloring that minimizes the sum of colors used on vertices. This opens the way for using Grover's algorithm for solving minimization problems, which is a separate interesting topic.

Let me know if you want to try and implement one of these topics!

Improve testing harness in RippleCarryAdder kata, task 1.7

Most tasks in this kata take inputs in an arbitrary superposition state and require implementing the right unitary transformation on them; to verify the solutions, the tests compare the learner's solution to the reference one as unitaries using AssertOperationsEqualReferenced. (Sometimes one or several inputs are in |0⟩ state, but this does not affect the expected solution, so we still can use the assert.)

In task 1.7, however, one of the inputs is guaranteed to be in |0...0⟩ state, and the "challenge" solution relies on that fact to reuse these qubits instead of allocating new ones. This means that the main solution and the reference ones perform different transformations, even though they are the same on the basis vectors. The test harness for this task uses only AssertOperationImplementsBinaryFunction to verify the solution instead of both it and AssertOperationsEqualReferenced.

We need to figure out a way to add verification of the solution as a unitary in this task. I think it should be possible to implement a wrapper operation which is a unitary on inputs a and b and allocates qubits in |0...0⟩ state for target qubits before calling the adder. Both solutions, when wrapped in such an adder, should implement the same unitary, and can be compared using AssertOperationsEqualReferenced.

• We can probably do the same for other tasks of this kata in which some of the inputs are in |0⟩ state, but it makes sense to start with this one. Afterwards we can either modify the testing harnesses for them similarly or modify the task descriptions to remove the promise of |0⟩ state in inputs.

Notebooks on Binder lose connection

I was doing the katas online on Binder but each time I leave the notebook inactive for some minutes (maybe 10 (?)) Binder loses the connection and it is impossible to reconnect without restarting the whole Notebook and losing what was written. I tried with Edge and Chrome and in both occurs the same issue. Also with different connections.

This can get frustrating when you're advanced in the notebook and after being thinking about the solution of an exercise you have to make a copy of everything and reset the notebook again because Binder lost the connection. Especially when you have to repeat this process several times per notebook.

I don't know if this is a problem with Binder or can be solved here. If it cannot be solved please close the issue. For now, I'll run the notebooks locally.

SolveSATWithGrover - Task 2.2 - infinite loop

    // Task 2.2. Universal implementation of Grover's algorithm
    operation GroversAlgorithm_Reference (N : Int, oracle : ((Qubit[], Qubit) => Unit : Adjoint)) : Bool[] {
        mutable answer = new Bool[N];
        using ((register, output) = (Qubit[N], Qubit())) {
            mutable correct = false;
            mutable iter = 1;
            repeat {
                Message($"Trying search with {iter} iterations");
                GroversAlgorithm_Loop(register, oracle, iter);
                let res = MultiM(register);
                // to check whether the result is correct, apply the oracle to the register plus ancilla after measurement
                oracle(register, output);
                if (MResetZ(output) == One) {
                    set correct = true;
                    set answer = BoolArrFromResultArr(res);
                }
                ResetAll(register);
            } until (correct) 
            fixup {
                set iter = iter * 2;
            }

It looks like the reference code never stops when we face unlucky case. The Grover's algorithm is not deterministic algorithm and the lower bound of possibility where we can obtain correct answer for unknown number of solutions is 0.5 when we increase k = 1,2,...,n for 2^k iterations.

Do we need to add upper bound for the loop? Or, do we need add description on the task such as "the given problem can be solved 100% with 2^k grover iterations" ?

If my understanding is not correct, please close the issue.

Write PowerShell script to update QDK to the new version

Updating QDK to the next version requires doing a fixed set of changes to an ever-growing set of files (see recent #179 and the most recent #235 for a list of files and changes).

Currently we're using a generic Bash script to automate most of the change (see attached updateQDKVersion.txt), but it would be nice to have a PowerShell script tailored to the Katas project.

DumpUnitary: fix the tool to parse new DumpMachine output format

DumpUnitary tool (a companion to UnitaryPatterns kata) still assumes pre-0.6 output format of DumpMachine, with just 3 tab-separated entries per basis state. Current output is more sophisticated, so the tool doesn't work. Here is an example of the current output format:

# wave function for qubits with ids (least to most significant): 0;1;2
∣0❭:	 1.000000 +  0.000000 i	 == 	******************** [ 1.000000 ]     --- [  0.00000 rad ]
∣1❭:	 0.000000 +  0.000000 i	 == 	                     [ 0.000000 ]                   

The complex number that represents the amplitude is tab-separated from the rest of the fields, and the real and imaginary components within are separated with spaces.

It would be nice to update the logic of parsing DumpMachine output (Driver.cs, lines 32-40) to parse the new format instead of the old one.

Link to "Linear Algebra" notebook from Complex Arithmetic notebook is broken

Link to "Linear Algebra" notebook from Complex Arithmetic notebook is broken

There is an additional LinearAlgebra in the path which might the cause.

Should we use 'α' as variable name?

I am using Jupyter Notebook. In the BasicGates python notebook I saw few parameters as 'α'. One has to copy and paste this variable everywhere they wish to use.

Should we continue using variables like 'α' or should we rename them to 'alpha'?

build error

https://mybinder.org/v2/gh/Microsoft/QuantumKatas/master?filepath=BasicGates%2FBasicGates.ipynb

Q#

Can someone explain me Superposition of 4 bit strings solution code.

operation FourBitstringSuperposition_Reference (qs : Qubit[], bits : Bool[][]) : Unit is Adj {
    let N = Length(qs);

    using (anc = Qubit[2]) {
        // Put two ancillas into equal superposition of 2-qubit basis states
        ApplyToEachA(H, anc);

        // Set up the right pattern on the main qubits with control on ancillas
        for (i in 0 .. 3) {
            for (j in 0 .. N - 1) {
                if ((bits[i])[j]) {
                    (ControlledOnInt(i, X))(anc, qs[j]);
                }
            }
        }

        // Uncompute the ancillas, using patterns on main qubits as control
        for (i in 0 .. 3) {
            if (i % 2 == 1) {
                (ControlledOnBitString(bits[i], X))(qs, anc[0]);
            }
            if (i / 2 == 1) {
                (ControlledOnBitString(bits[i], X))(qs, anc[1]);
            }
        }
    }
}

This is the code given in the Microsoft quantum katas github.
Also I do not come from a physics background , so please provide reading references if any.Thanks in advance.

Minor typo in function description in DJAlgorithm

Hi, there is any solutions to the Katas?

Thanks!

Measurement Task 1.7 - code passes even with more than one measurement

The comment description for that task reads:

// You can use exactly one measurement.

The following code passes:

operation TwoBitstringsMeasurement (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Int {
    let n = Length(qs);

    for(i in 0..n-1){
        if(M(qs[i]) == One){
            if(bits1[i] && bits2[i]){
            }elif(bits1[i]){
                return 0;
            }else{
                return 1;
            }
        }else{
            if(not bits1[i] && not bits2[i]){
            }elif(not bits1[i]){
                return 0;
            }else{
                return 1;
            }
        }
    }

    return -1;
}

AFAICT, the above code makes n-1 measurements, if both the boolean bit arrays have different value only at the last bit.

Quantum counting

Dear all,
I wrote a quantum counting kata but I'm encountering problems, it works for some functions and doesn't for others, should I submit a pull request?

Best
Fabrizio

Invalid kata name errors

I installed IQ# as described here, cloned this repository and tried to run the BasicGates Jupyter notebook. However, when trying to run any task I get the following error:

Invalid kata name: T11_StateFlip_Test

Some information:

• Ubuntu 16.04
• Python 3.7.1
• Jupyter Notebook 4.4.0

$ dotnet iqsharp --version
Language kernel: 0.5.1904.1302
Jupyter core: 1.1.13141.0

Removing the %kata lines at the top of each block fixes this issue.

dotnet test have error at BasicGates folder

Precision issue with LinearAlgebra Exercise 14 validation

Following is my answer to linear algebra exercise 14, it never passes validation, possibly due to a precision issue:

@exercise
def find_eigenvector(a : Matrix, x : float) -> Matrix:
    m, n = a[0]
    p, q = a[1]
    print("input matrix", m, n, p, q)
    
    if (m - x) == 0:
        if n == 0:
            if p == 0 and (q - x) == 0:
                return [[1], [1]]
            elif p == 0:
                return [[1], [0]]
            elif (q - x) == 0:
                return [[0], [1]]
        else:
            return [[1], [0]]
    if p == 0:
        if (q - x) == 0:
            if (m - x) == 0 and n == 0:
                return [[1], [1]]
            elif (m - x) == 0:
                return [[1], [0]]
            elif n == 0:
                return [[0], [1]]
        else:
            return [[1], [0]]
    
    res = [[n], [x - m]]
    print("=> matrix_mult", matrix_mult(a, res))
    print("=> scalar_mult", scalar_mult(x, res))
    
    return res

Output

input matrix 2 0 0 0
input matrix 0 0 0 2
input matrix 3 -2 -3 2
=> matrix_mult [[0], [0]]
=> scalar_mult [[0], [0]]
input matrix (1.410044130618676+3.4335219182928984j) (3.754740821442419-3.844639920338417j) (-1.3835599382959733-3.9144870184937854j) (-3.6290973002432683+3.692620479238418j)
=> matrix_mult [[(-0.8412196457268912-2.04680458238229j)], [(-1.6445865370993324-0.1502656593596896j)]]
=> scalar_mult [[(-0.841219645726889-2.046804582382289j)], [(-1.6445865370993324-0.15026565935968822j)]]
Wrong eigenvector!
Eigenvalue: 0.163-0.378j

   |  1.410+3.434i  3.755-3.845i |
A: | -1.384-3.914i -3.629+3.693i |

              |  3.755-3.845i |
You returned: | -1.247-3.812i |

Try again!

matrix_mult output and scaler_mult outputs are very close, but the testing module would rule it wrong (https://github.com/microsoft/QuantumKatas/blob/master/tutorials/LinearAlgebra/testing.py#L157). The precision issue seems to only occur with complex value inputs.