Microsoft Word – MULT20015 Prac Class 9 small_changes.docx
MULT20015 Practice Class 9, Ó L. Hollenberg et al 2021 1
Copyright By PowCoder代写 加微信 powcoder
MULT20015 Elements of Quantum Computing
Practice Class 9
Welcome to Practice Class 9 of MULT20015 Elements of Quantum Computing.
The purpose of this lab session is to:
• implement quantum counting algorithm
• implement Grover’s algorithm for single solution case
• understand the concepts of QUBO
1 Implement quantum counting algorithm
In the lecture on Grover’s algorithm we saw that the optimal number of Grover iterations
(to maximise the probability of finding a solution) depends on the number of solutions
relative to the size of the search space. In general, the number of solutions is unknown.
Hence, we first need to compute the number of solutions.
Please use the following circuit for a three qubit oracle in this exercise.
Note that though you know the details of the oracle, please take this as a given and do
not count the number of solutions using the oracle.
Recall that a Grover iteration (we will use the term operation instead of iteration) requires
two steps: (i) application of the Oracle, and (ii) inversion around the mean. A circuit for
inversion around the mean is given below.
Oracle circuit
Inversion around mean
MULT20015 Practice Class 9, Ó L. Hollenberg et al 2021 2
To count the number of solutions we combine Grover’s algorithm with Phase estimation.
The operation 𝑈 in the circuit will be Grover’s operation (that is, using the oracle followed
by inversion around the mean). Observe that to encode the controlled-Grover operation we
only need to add an additional control on the Z gate. The circuit below depicts a controlled
Grover operation.
Exercise 1.1 Explain why one does not need controlled operation on the X gates in the
circuit shown above.
Exercise 1.2 Create a phase estimation circuit with 3 measuring qubits where the operation
𝑈 is a Grover’s iteration with the given oracle. The circuit will have two parts:
1. Controlled Grover operations. Since we are using 3 qubits for counting. We will
need in total 4 Grover operations controlled over first qubit, 2 Grover operations
controlled over the second qubit, and 1 Grover operations controlled over the third
qubit. The circuit shown below depicts these operations.
General phase estimation circuit
Controlled Grover operation (control on top qubit)
MULT20015 Practice Class 9, Ó L. Hollenberg et al 2021 3
2. Inverse QFT. After your circuit with controlled Grover’s operations, construct the
Quantum Fourier Transform on the top three qubits. The circuit is shown below for
your reference (it is the same as what you had used in the phase estimation lab).
The angles for the controlled-Z rotations are as follows:
(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 1.3 Take the state with the highest probability and extract the measured value
for the phase estimation. Note that you will see probabilities for the overall state. To
extract the measure value you have to exclude the qubits used for Grover’s operation.
For example, if the state is |001010⟩, you should ignore the last three qubits to get the
measured value of 1 (i.e., 001).
Exercise 1.4 Recall that if 𝑈|𝜓⟩ = 𝑒!”#$|𝜓⟩, the phase estimation circuit measures an
estimate of 2%𝜃. The Eigenvalues for the Grover’s operator are 𝑒±!#$ . Calculate the angle
𝜃 for the Grover’s operator.
Exercise 1.5 Using the obtained estimate of 𝜃, calculate the number of solutions and
optimal number of Grover’s iterations for the given oracle.
Controlled Grover operations for 3 counting qubits
Inverse QFT circuit
MULT20015 Practice Class 9, Ó L. Hollenberg et al 2021 4
2 Grover search
Now we’ll put all that together to implement simple instances of Grover’s search algorithm.
Exercise 2.1 Program a circuit in the QUI that implements Grover’s search for the given
oracle with the optimal number of iterations you calculated in the previous exercise.
Exercise 2.2 Revisit the oracle and verify that the number of solutions and the obtained
3 Understanding QUBO
In this section we will explore the use of quadratic unconstrained binary optimisation
problems. These will be used again next week when we explore how to use a quantum
computer to solve these problems.
As you saw in lectures many optimisation problems over binary numbers can be cast into
the “spin-glass” form where the task is to minimise the energy of a particular function E
over variables {𝑧# = ±1}. The quadratic form (QUBO) involves products xi and xj, which we
can map the problem onto a quantum computer by converting to variables zi and zj.
Exercise 3.1 If a QUBO problem has a term,
write down the corresponding energy term after we make the substitution,
Exercise 3.2
We will work to solve a problem for which the quantum cost function (which we would
like to minimize) has been determined to be:
𝐻 = 𝑍’ + 2𝑍’𝑍! + 𝑍!𝑍(
For each of the eight possible basis states (why eight?), fill in the following table,
evaluating the cost function for each basis state:
State, i Z1 Z2 Z3 Hi
|000⟩ +1 +1 +1 4
|001⟩ +1 +1 -1 2
MULT20015 Practice Class 9, Ó L. Hollenberg et al 2021 5
Exercise 3.3
Which state has the minimum cost?
Finally, let us consider an instance of the number partitioning. The problem is stated as
follows: given a set S of numbers {wi}, is there a partition of this set of numbers into two
disjoint subsets R and S − R, such that the sum of the elements in both sets is the same?
In lectures we saw the solution is equivalent to finding the basis state with the minimum
energy in the system given by the “Hamiltonian” (quantum cost function):
where and each number is assigned a qubit (wi ↔ qi) and the qubit value 0 or 1 indicates
which of the two sets, R and S–R, the numbers are associated with.
Exercise 3.4 Consider S = {1, 2, 3}. Classically solving the problem (i.e. in your head), what
are the solution sets R and S–R?
Exercise 3.5 Convert classical solutions to quantum land. Assigning “R” ↔ “0” and “S–R”
↔ “1”, translate the expected possible solutions from 2.1 into qubit form |𝑞’𝑞!𝑞(⟩ where
that values of each qi = 0, 1 indicates which set the corresponding number wi is assigned
to in the solution. The two solutions are:
_____________ and ______________
Exercise 3.6 The Hamiltonian of this number partitioning problem is
Make sure you understand how to get this from the general expression above. Show that
the energy of this system is zero for the solution basis states |𝑞’𝑞!𝑞(⟩ you found in 3.5,
and non-zero for other states.
2wiwjZiZj +
H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com