The Quantum Key Distribution kata is a series of exercises designed to teach you about a neat quantum technology where you can use qubits to exchange secure cryptographic keys. In particular, you will work through implementing and testing a quantum key distribution protocol called BB84.
What does a key distribution protocol look like in general? Normally there are two parties, commonly referred to as Alice and Bob, who want to share a random, secret string of bits called a key. This key can then be used for a variety of different cryptographic protocols like encryption or authentication. Quantum versions of key exchange protocols look very similar, and utilize qubits as a way to securely transmit the bit string.
You can see in the figure above that Alice and Bob have two connections, one quantum channel and one bidirectional classical channel. In this kata you will simulate what happens on the quantum channel by preparing and measuring a sequence of qubits and then perform classical operations to transform the measurement results to a usable, binary key.
There are a variety of different quantum key distribution protocols, however the most common is called BB84 after the initials of the authors and the year it was published. It is used in many existing commercial quantum key distribution devices that implement BB84 with single photons as the qubits.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
BB84 protocol loops through the two main steps until Alice and Bob have as much key as they want. The first step is to use the quantum channel, where Alice prepares individual qubits and then sends them to Bob to be measured. The second step is entirely classical post-processing and communication that takes the measurement results from the quantum step and extracts a classical, random bit string Alice and Bob can use. Let's start by looking at how Alice will prepare her qubits for sending to Bob as a part of the quantum phase of the BB84 protocol.
Alice has two choices for each qubit, which basis to prepare it in, and what bit value she wants to encode. This leads to four possible states each qubit can be in that Alice sends out. The bases she has to choose from are selected such that if an eavesdropper tries to measure a qubit in transit and chooses the wrong basis, then they just get a 0 or 1 with equal probability.
In the first basis, called the computational basis, Alice prepares the states $|0\rangle$ and $|1\rangle$ where $|0\rangle$ represents the key bit value 0
and $|1\rangle$ represents the key bit value 1
.
The second basis (sometimes called the diagonal or Hadamard basis) uses the states $|+\rangle = \frac{1}{\sqrt2}(|0\rangle + |1\rangle)$ to represent the key bit value 0
, and $|-\rangle = \frac{1}{\sqrt2}(|0\rangle - |1\rangle)$ to represent the key bit value 1
.
Try your hand at converting qubits from the computational basis to the diagonal basis.
Input: $N$ qubits (stored in an array of length $N$). Each qubit is either in $|0\rangle$ or in $|1\rangle$ state.
Goal: Convert the qubits to the diagonal basis:
qs[i]
was in state $|0\rangle$, it should be transformed to $|+\rangle = \frac{1}{\sqrt2}(|0\rangle + |1\rangle)$,qs[i]
was in state $|1\rangle$, it should be transformed to $|-\rangle = \frac{1}{\sqrt2}(|0\rangle - |1\rangle)$.%kata T11_DiagonalBasis
operation DiagonalBasis (qs : Qubit[]) : Unit {
// ...
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Input: A qubit in the $|0\rangle$ state.
Goal: Change the qubit state to a superposition state that has equal probabilities of measuring 0 and 1.
Note that this is not the same as keeping the qubit in the $|0\rangle$ state with 50% probability and converting it to the $|1\rangle$ state with 50% probability!
%kata T12_EqualSuperposition
operation EqualSuperposition (q : Qubit) : Unit {
// ...
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Now that you have seen some of the steps that Alice will use to prepare here qubits, it's time to add in the rest of the steps of the BB84 protocol.
You saw in part I that Alice has to make two random choices per qubit she prepares, one for which basis to prepare in, and the other for what bit value she wants to send. Bob will also need one random bit value to decide what basis he will be measuring each qubit in. To make this easier for later steps, you will need a way of generating random boolean values for both Alice and Bob to use.
Input: An integer $N$.
Output : A Bool
array of length N, where each element is chosen at random.
This will be used by both Alice and Bob to choose either the sequence of bits to send or the sequence of bases (
false
indicates $|0\rangle$ / $|1\rangle$ basis, andtrue
indicates $|+\rangle$ / $|-\rangle$ basis) to use when encoding/measuring the bits.
%kata T21_RandomArray
operation RandomArray (N : Int) : Bool[] {
// ...
return [false, size = N];
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Now that you have a way of generating the random inputs needed for Alice and Bob, it's time for Alice to use the random bits to prepare her sequence of qubits to send to Bob.
Inputs:
qs
: an array of $N$ qubits in the $|0\rangle$ states,bases
: a Bool
array of length $N$;
bases[i]
indicates the basis to prepare the i-th qubit in:false
: use $|0\rangle$ / $|1\rangle$ (computational) basis,true
: use $|+\rangle$ / $|-\rangle$ (Hadamard/diagonal) basis.bits
: a Bool
array of length $N$;
bits[i]
indicates the bit to encode in the i-th qubit: false
= 0, true
= 1.Goal: Prepare the qubits in the described state.
%kata T22_PrepareAlicesQubits
operation PrepareAlicesQubits (qs : Qubit[], bases : Bool[], bits : Bool[]) : Unit {
// ...
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Bob now has an incoming stream of qubits that he needs to measure by randomly choosing a basis to measure in for each qubit.
Inputs:
qs
: an array of $N$ qubits;bases
: a Bool
array of length $N$;
bases[i]
indicates the basis used to prepare the i-th qubit:false
: $|0\rangle$ / $|1\rangle$ (computational) basis,true
: $|+\rangle$ / $|-\rangle$ (Hadamard/diagonal) basis.Output: Measure each qubit in the corresponding basis and return an array of results as boolean values, encoding measurement result Zero
as false
and One
as true
.
The state of the qubits at the end of the operation does not matter.
%kata T23_MeasureBobsQubits
operation MeasureBobsQubits (qs : Qubit[], bases : Bool[]) : Bool[] {
// ...
return [];
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Now, Alice has a list of the bit values she sent as well as what basis she prepared each qubit in, and Bob has a list of bases he used to measure each qubit. To figure out the shared key, they need to figure out when they both used the same basis, and toss the data from qubits where they used different bases. If Alice and Bob did not use the same basis to prepare and measure the qubits in, the measurement results Bob got will be just random with 50% probability for both the Zero
and One
outcomes.
Inputs:
basesAlice
and basesBob
: Bool
arrays of length $N$
describing Alice's and Bobs's choice of bases, respectively;measurementsBob
: a Bool
array of length $N$ describing Bob's measurement results.Output: a Bool
array representing the shared key generated by the protocol.
Note that you don't need to know both Alice's and Bob's bits to figure out the shared key!
%kata T24_GenerateSharedKey
function GenerateSharedKey (basesAlice : Bool[], basesBob : Bool[], measurementsBob : Bool[]) : Bool[] {
// ...
return [];
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
The main trace eavesdroppers can leave on a key exchange is to introduce more errors into the transmission. Alice and Bob should have characterized the error rate of their channel before launching the protocol, and need to make sure when exchanging the key that there were not more errors than they expected. The "errorRate" parameter represents their earlier characterization of their channel.
Inputs:
keyAlice
and keyBob
: Bool
arrays of equal length $N$ describing
the versions of the shared key obtained by Alice and Bob, respectively.errorRate
: an integer between 0 and 50 - the percentage of the bits that did not match in Alice's and Bob's channel characterization.Output: true
if the percentage of errors is less than or equal to the error rate, and false
otherwise.
%kata T25_CheckKeysMatch
function CheckKeysMatch (keyAlice : Bool[], keyBob : Bool[], errorRate : Int) : Bool {
// ...
return false;
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Goal: Implement the entire BB84 protocol using tasks 2.1 - 2.5 and following the comments in the operation template.
This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the
Run_BB84Protocol
operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (%simulate Run_BB84Protocol
).
operation Run_BB84Protocol () : Unit {
// 1. Alice chooses a random set of bits to encode in her qubits
// and a random set of bases to prepare her qubits in.
// ...
// 2. Alice allocates qubits, encodes them using her choices and sends them to Bob.
// (Note that you can not reflect "sending the qubits to Bob" in Q#)
// ...
// 3. Bob chooses a random set of bases to measure Alice's qubits in.
// ...
// 4. Bob measures Alice's qubits in his chosen bases.
// ...
// 5. Alice and Bob compare their chosen bases and use the bits in the matching positions to create a shared key.
// ...
// 6. Alice and Bob check to make sure nobody eavesdropped by comparing a subset of their keys
// and verifying that more than a certain percentage of the bits match.
// For this step, you can check the percentage of matching bits using the entire key
// (in practice only a subset of indices is chosen to minimize the number of discarded bits).
// ...
// If you've done everything correctly, the generated keys will always match, since there is no eavesdropping going on.
// In the next section you will explore the effects introduced by eavesdropping.
}
%simulate Run_BB84Protocol
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
In this task you will try to implement an eavesdropper, Eve.
Eve will intercept a qubit from the quantum channel that Alice and Bob are using. She will measure it in either the $|0\rangle$ / $|1\rangle$ basis or the $|+\rangle$ / $|-\rangle$ basis, and prepare a new qubit in the state she measured. Then she will send the new qubit back to the channel. Eve hopes that if she got lucky with her measurement, that when Bob measures the qubit he doesn't get an error so she won't be caught!
Inputs:
q
: a qubit in one of the following states: $|0\rangle$, $|1\rangle$, $|+\rangle$, $|-\rangle$.basis
: Eve's guess of the basis she should use for measuring.
Recall that false
indicates $|0\rangle$ / $|1\rangle$ basis and true
indicates $|+\rangle$ / $|-\rangle$ basis.Output: the bit encoded in the qubit (false
for $|0\rangle$ / $|+\rangle$ states, true
for $|1\rangle$ / $|-\rangle$ states).
In this task you are guaranteed that the basis you're given matches the one in which the qubit is encoded, that is, if you are given a qubit in state $|0\rangle$ or $|1\rangle$, you will be given
basis = false
, and if you are given a qubit in state $|+\rangle$ or $|-\rangle$, you will be givenbasis = true
. This is different from a real eavesdropping scenario, in which you have to guess the basis yourself.
%kata T31_Eavesdrop
operation Eavesdrop (q : Qubit, basis : Bool) : Bool {
// ...
return false;
}
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.
Add an eavesdropper into the BB84 protocol from task 2.6.
Note that now we should be able to detect Eve and therefore we have to discard our key bits!
Similar to task 2.6, this is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the
Run_BB84ProtocolWithEavesdropper
operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (%simulate Run_BB84ProtocolWithEavesdropper
).
operation Run_BB84ProtocolWithEavesdropper () : Unit {
// ...
}
%simulate Run_BB84ProtocolWithEavesdropper
Can't come up with a solution? See the explained solution in the Key Distribution - BB84 Workbook.