MULT20015, Elements of Quantum Computing, Lab 7 1
Copyright By PowCoder代写 加微信 powcoder
MULT20015 Elements of Quantum Computing
Practice Class 7
Welcome to Practice Class 7 of MULT20015 Elements of Quantum Computing, covering
exercises relevant to the material presented in lectures in Week 7.
The purpose of this week’s exercises is to:
• Implement and investigation a small version of Shor’s algorithm
• Implement and investigate the BB84 quantum key distribution protocol.
Please note that due to adjustment of the semester timetable, this lab covers quite a lot
of material. The exercises in these notes are to assist your understanding of the subject
and may require time outside of the practice class to complete.
1 Shor’s quantum factoring algorithm
In this exercise we will encode and attempt to understand an instance of Shor’s algorithm,
albeit a specially designed case to make it not too lengthy on the QUI – we’ll call this
“Baby Shor”. The full circuit for Shor’s algorithm including the modular arithmetic is in
general quite complicated. However, with some prior knowledge about the number we are
factoring we can make some simplifications and still convey the same information. The
circuit for Baby Shor is shown in the screenshot and described below (ref: ).
Baby Shor, as one would expect, factors 15 by computing 𝑓(𝑥) = 2! mod 15 (i.e. the
parameter a is set to a = 2), measuring out the |𝑓(𝑥)⟩ register (bottom 4 qubits), and then
performing a QFT on the resulting superposition over the |𝑥⟩ register (top 4 qubits).
Recall from lectures that the more general circuit for Shor’s algorithm has two registers:
an |𝑥⟩ register which is 2L qubits, and an L qubit register – initialised to |1⟩, on which we
MULT20015, Elements of Quantum Computing, Lab 7 2
compute |𝑓(𝑥)⟩ (L is the number of bits in N). The first simplification we make is reducing
the |𝑥⟩ register to L qubits, a move which will be later justified.
We compute the modular exponential through repeated modular multiplication. Writing 𝑥 =
𝑥”𝑥#𝑥$𝑥% = 2$𝑥” + 2#𝑥# + 2″𝑥$ + 2&𝑥%, we do four multiplications on the |𝑓(𝑥)⟩ register,
controlled by each qubit of the |𝑥⟩ register. With each step, we multiply |𝑓(𝑥)⟩ by 2#!,
controlled by the 𝑥%'( qubit. This is the same as multiplying by 2#
!!”#!, since if 𝑥%'( = 0,
then we multiply by 1 – which is the same as doing nothing.
Step-by-step, the |𝑓(𝑥)⟩ register follows the pathway:
|1⟩ → |1 × 2#
$!” mod 153 → |1 × 2#
%!& mod 153 → |1 × 2#
‘!’ mod 153
→ |1 × 2#
&!% mod 153 = |2#
&!%)#’!’)#%!&)#$!” mod 153
= |2! mod 15⟩
Now comes the main hack : general multiplications are difficult to perform on quantum
circuits, but we have chosen a=2 (i.e. 2! mod 15) to make things easy. Consider each
multiplication:
mod 15 = 2
mod 15 = 4
mod 15 = 1
mod 15 = 1
We notice firstly that the last two multiplications are multiplications by 1, which is no
action. So we need only to compute the first two multiplications. We next notice that the
first two are multiplications by powers of 2. There is something special about multiplying
binary numbers by a power of 2. If we write 𝑗 = 2$𝑗” + 2#𝑗# + 2″𝑗$ + 2&𝑗%, then 2* × 𝑗 =
2$)*𝑗” + 2#)*𝑗# + 2″)*𝑗$ + 2&)*𝑗%. That is, we are shifting each of our numbers to the left by
one position. This is not a new concept. Think about how you multiply numbers by 10, or
100 in base 10. This is done by shifting all of your numbers to the left by 1 or 2 positions.
Also, recall that binary numbers are inherently defined modulo 2*.
In terms of gates, shifting our bits is the same as swapping their positions. We start out
at 0001 and have a controlled multiplication of 2, which would give 0010. This is the same
as swapping 𝑥$ and 𝑥%. Similarly, bit-shifting by two positions means taking 𝑥”𝑥#𝑥$𝑥% →
𝑥$𝑥%𝑥”𝑥# – achieved through two SWAPS. Result – our complicated exponentiation circuit
can be reduced to just three controlled SWAP gates for this simple case!
This means now that our circuit for Shor’s algorithm can be summarised by:
1) a controlled shift by 𝑥% of 1 position acting on the |𝑓(𝑥)⟩ register
2) a controlled shift by 𝑥$ of 2 positions acting on the |𝑓(𝑥)⟩ register
3) a measurement of the |𝑓(𝑥)⟩ register to isolate one superposition in the |𝑥⟩ register
4) a QFT on the |𝑥⟩ register
5) Measure the |𝑥⟩ register (or in the QUI just inspect the state)
MULT20015, Elements of Quantum Computing, Lab 7 3
The reason why we can reduce the |𝑥⟩ register down to L qubits is related to the period.
A domain of 2#+ is usually chosen in order to guarantee that we can find the period
through continued fractions, in the case that we do not have exact periodicity. However,
in the simple scenario here the period is 4, which divides 2%, and so we do not need the
extra L qubits.
Finally, note that the X operation on the last qubit is for convenience in reading out the
final measurement when the bottom register is measured as 0001, which after the X
operation becomes 0000.
Exercise 1.1 Code up Baby Shor in the QUI (use a previous instance of QFT4). Save it
and run it several times to understand how it works (you can edit appropriately to verify
the function f(x) evaluation), what the output means (you can add measurements on the x
register, or just interpret the final state), and how to determine the prime factors of 15.
2 Quantum Communication – the BB84 Protocol in the QUI
An important application of qubits is to enable secure communication between two parties.
There are several different quantum communication protocols with varying degrees of
complexity. In this section, we will implement a very simple protocol known as “BB84” which
is based on single qubits and can be implemented in the QUI. BB84 stands for Bennett
and Brassard, the names of the two mathematicians who proposed this protocol in 1984.
Basic idea: Alice wants to send Bob a secret key (string of bits) over a channel that might
be intercepted by an eavesdropper (Eve). Using qubits Alice can encode her bits in randomly
selected instances of either the Z basis (|0⟩, |1⟩) or X basis (|+⟩, |−⟩). By the rules of
quantum superposition, if Alice prepares a bit in one basis and Bob measures in a different
basis he is not guaranteed of measuring the correct bit of information. Only when the
bases agree will Bob measure Alice’s bit with 100% certainty (see below). The trick is that
after measurement Alice and Bob only compare measurement bases, not the actual bits
measured. They then use a certain number of correct bits to test whether an eavesdropper
tried to intercept and re-send the communication – in this case Alice and Bob will see the
percentage of correct bits drop.
MULT20015, Elements of Quantum Computing, Lab 7 4
Exercise 2.1 For a single qubit, code the BB84 protocol for the no-eavesdropper case in
the QUI and repeat for all eight cases of bases choice by Alice and Bob (illustrated below).
In single qubit mode, use the time scrubber to examine the qubit state during the protocol
to make sure you understand how it works.
Before we start encoding BB84 in the QUI, let’s first do a few simple tasks which will allow
us to implement the protocol.
Exercise 2.2 Generate random binary sequences of (10-bit length) using a Hadamard gate
followed by a measurement gate. Recall: a H gate places the state into an equal
superposition of |0⟩ and |1⟩, and the measurement will randomly collapse it to either |0⟩
or |1⟩. Construct the following ten qubit circuit in QUI:
MULT20015, Elements of Quantum Computing, Lab 7 5
Press the COMPUTE button (7 times) to produce the following series of 10-bit random
sequences and record as per below:
No-eavesdropper case:
Sequence 1: (Alice’s bit string)
Sequence 2: (Alice’s basis choice)
Sequence 3: (Bob’s basis choice)
Eavesdropper case:
Sequence 4: (Alice’s bit string)
Sequence 5: (Alice’s basis choice)
Sequence 6: (Bob’s basis choice)
Sequence 7: (Eve’s basis choice)
Exercise 2.3 Implement a 10-qubit circuit in QUI to encode the 10-bit binary “Sequence
1” as per the above, corresponding to Alice’s bit string. Now use Sequence 2 corresponding
to Alice’s random choice of basis encoding: “0” for the Z-basis (no H gate), “1” for the X-
basis (H-gate), As an example, a circuit is shown below for Sequence 1=1011000101 and
Sequence 2=0100110011:
Exercise 2.4 Code the BB84 protocol for the no-eavesdropper case for all 10 qubits
according to your random sequences 1-3 (as per illustration below).
MULT20015, Elements of Quantum Computing, Lab 7 6
Run the no-eavesdropper-case protocol and fill in the following table:
Table 2.1 – No eavesdropper case
Alice-Bob:
correct basis?
Correct bit
Number of correct bits received = ____ (= ____ %)
Exercise 2.5 Now add Eve to your circuit, using the sequences 4-7 as indicated below.
MULT20015, Elements of Quantum Computing, Lab 7 7
Run the eavesdropper-case protocol and fill in the following table:
Table 2.2 – Eavesdropper case
Alice-Bob:
Number of correct bits received = ____ (= ____ %)
3 Putting it all together
In the presence of Eve the number of correct bits sent is reduced due to her interference,
and if there was no other “noise” in the channel that alone would signal an attack. Without
Eve, Alice and Bob would agree in basis choice 50% of the time, and hence 50% of the
bits sent can be used for the key. With Eve attacking, the percentage of correct bits will
be reduced – the presence of Eve can be detected by comparing the percentage of correct
bits for a sub-set of the original string (that will never be used for the key).
Exercise 3.1 Compare the % correct bits received for both the no-Eve and Eve cases.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com