Microsoft Word – MULT20015 Lab 6 LMS.docx
MULT20015, Elements of Quantum Computing, Lab 6 1
Copyright By PowCoder代写 加微信 powcoder
MULT20015 Elements of Quantum Computing
Practice Class 6
Welcome to Practice Class 6 of MULT20015 Elements of Quantum Computing, covering
exercises relevant to the material presented in lectures in Week 6.
The purpose of this week’s exercises is to:
• Implement RSA with small parameters
• Investigate the quantum phase estimation algorithm
1 RSA parameters for small inputs
In this exercise we will work through some RSA key generation examples with small
parameters. Please go through the RSA encryption and decryption function definitions. Your
task is to determine RSA’s public and private key pairs given the two primes required. You
will make use of extended Euclid’s algorithm finding greatest common divisor between two
numbers in the process.
Given N = PQ; where P, Q are primes, and the public and private key pair (e, d) is
computed such that
ed º 1 mod f(N), where f is Euler’s totient function.
To find d given e, we will use the extended Euclid’s algorithm: For any integers a and b,
there exist integers x and y such that:
gcd[a; b] := ax + by.
Given e and f(N), then run the extended Euclid’s algorithm with input (e, f(N)), then you
get gcd[e, f(N)] = e x + f(N) y, which has to be equal to 1, since e is chosen such that it is
relatively prime to f(N). Taking (mod f(N)) on both the sides of the equation gives,
e x = 1 (mod f(N)). Hence x will be inverse of e modulo N, so d = x.
You can compute the steps of the extended Euclid’s algorithm manually following the
algorithm given below:
MULT20015, Elements of Quantum Computing, Lab 6 2
a = q1b + r1
b = q2r1 + r2
r1 = q3r2 + r3
r2 = q4r3 + r4
(1) rn-2 = qnrn-1 + rn
(2) rn-1 = qn+1rn + rn+1, where rn+1 = 1 (GCD
(3) rn = qn+2rn+1 + rn+2, where rn+2 = 0
Now we can perform a back substitution to
get d as follows:
From (2) we get
rn+1 = 1 = rn-1 – qn+1rn
We know rn from (1), so we can substitute
= rn-2 – qn+1(rn-2 – qnrn-1)
We continue this for each r while simplifying
each step until we can represent the rn+1 in
terms of b.
Exercise 1.1 Given the p=13 and q=7, compute the RSA parameters n and f(n). For the
RSA algorithm to work, it requires two coefficients – e and d. Where e represents the
encryption component (generally the public key) and d represents the decryption component
(generally the private key).
Suppose φ(n) = 72, using the extended Euclid’s algorithm given above, calculate the value
of d such that ed = 1 mod φ(n) for
You can use the online Magma calculator to run the extended Euclid’s algorithm. Magma
computation is available online at
http://magma.maths.usyd.edu.au/calc/
Magma Calculator
Magma Calculator Enter your code in the box below. Click on
“Submit” to have it evaluated by Magma. Calculations are restricted
to 120 seconds. Input is limited to 50000 bytes. Running Magma
V2.25-4. Magma is maintained and distributed by the
Computational Algebra Group, School of Mathematics and
Statistics, University of Sydney.
magma.maths.usyd.edu.au
For example:
>XGCD(13,25);
Indicating that gcd = 1 = 13*2 + (-1) * 25;
MULT20015, Elements of Quantum Computing, Lab 6 3
ExtendedGreatestCommonDivisor(m, n) : RngIntElt, RngIntElt -> RngIntElt,
RngIntElt, RngInt (m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt
XGCD(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt
The extended GCD of m and n; returns integers g, x and y such that g
is the greatest common divisor of the integers m and n, and g = x.m
+ y.n. If m and n are both zero, g is zero; otherwise g is always
positive. If m and n are both non-zero, the multipliers x and y are
===============================================================================
Exercise 1.2: Given the encryption and decryption formulas for RSA as follow: 𝐶 = 𝑀𝑒
𝑚𝑜𝑑 𝑛; 𝑀 = 𝐶 𝑑 𝑚𝑜𝑑 𝑛 = (𝑀𝑒 )𝑑 𝑚𝑜𝑑 𝑛 = 𝑀 𝑚𝑜𝑑 𝑛. Perform encryption and decryption
for the given values of p, q, e and M. You can use the online Magma calculator.
a. p =3, q =13, e =5; M =10.
b. p = 5, q =11, e =13; M =12.
c. p = 11, q =7, e = 7; M = 7.
d. P = 31, q=43, e =23, M = 11.
2 Quantum Phase Estimation
In this exercise we will construct the Quantum Phase Estimation (QPE) circuit described in
the lectures, to determine the eigenvalue of the T gate, corresponding to the |1⟩ state.
Recall that if
𝑈|ψ⟩ = exp(𝑖2πθ) |ψ⟩,
then QPE allows us to estimate θ using a quantum computer. In this section we will use
QUI to construct the QPE circuit with U=T and |ψ⟩ = |1⟩.
MULT20015, Elements of Quantum Computing, Lab 6 4
Exercise 2.1 First let us initialize the circuit. Construct the following circuit to initialize the
state |ψ⟩, and apply the controlled-U gates:
Note that there are 1, 2, and 4 controlled-T gates controlled from the 1s, 2s and 4s
binary digits of the upper register. Also, note that the bottom register is initialized (by
applying an x-gate) to the eigenstate.
Exercise 2.2 Having made the circuit above, examine the phase of each of the states. Fill
in the following table showing each populated state and the corresponding phase:
State Phase (Radians)
Exercise 2.3 After your existing circuit construct the Quantum Fourier Transform on the
three qubits in the upper register.
The angles of the controlled-Z rotations shown are:
(a) −𝜋/2 (with a global phase of −π/4)
(b) −𝜋/4 (with a global phase of −π/8)
(c) −𝜋/2 (with a global phase of −π/4)
Exercise 2.4 Finally, measure the three qubits in the upper register. Your circuit should
now look like this:
MULT20015, Elements of Quantum Computing, Lab 6 5
The measured value relates to the original eigenvalue by
where y is the measured value, n is the number of qubits in the upper register and θ is
the angle we would like to find. Verify that your circuit finds:
corresponding to an eigenvalue of the T operator of exp(𝑖2πθ) = exp(𝑖π/4) and the
eigenstate, which we prepared in the bottom register, of |1⟩.
Exercise 2.5 Repeat the Quantum Phase Estimation algorithm (above) to find the eigenvalue
of the S gate, corresponding to the eigenstate |1⟩.
Exercise 2.6 Repeat the Quantum Phase Estimation algorithm (above) to find the eigenvalue
of the Z gate, corresponding to the eigenstate |1⟩.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com