CS 239 Quantum Programming Spring 2019
Midterm Exam
May 1, 2019: 100 minutes. Write your name and UCLA id on the first page you submit;
staple the pages you submit.
Each of questions 1–10 is worth 7 points, and each of questions 11-13 is worth 10 points.
1. Describe briefly the four postulates about quantum mechanics upon which quantum
computing is based.
2. What is a qubit in mathematical terms?
3. Is the following matrix is unitary? Justify your answer.
4. Calculate the following tensor product.
5. Calculate the following tensor product.
6. What state do we get if we apply (H ⊗ I) CNOT to the following state?
7. For the following state, suppose we measure the second qubit in the standard basis
and get 0. Show the resulting state. Justify your answer.
8. Suppose we apply H⊗3 to three qubits in the state |111⟩, after which we measure the
first two qubits in the standard basis. What is the probability that we will get 11 ?
9. Consider the following circuit with three qubits.
Suppose that at the end, we measure all three qubits in the standard basis. What is the
probability that we will get 000 ? Justify your answer.
10. Consider the following state.
Suppose we measure the first qubit in the standard basis. What is the probability of getting
0, and if that happens, what is the state of the second qubit? Also, suppose we measure
the second qubit in the standard basis. What is the probability of getting 1, and if that
happens, what is the state of the first qubit?
11. Show, step by step, that the Deutsch-Jozsa algorithm works for the case of f(x) = x.
12. For the case of n = 3 and a function f where
f(000) = f(011) = 010 f(100) = f(111) = 110
f(001) = f(010) = 101 f(101) = f(110) = 001
give two different examples of equations that the first step of Simon’s algorithm may produce.
Explain what those equations mean.
13. Show, step-by-step, that Grover’s algorithm works for the case of 2 qubits and a
function f where f(10) = 1 and f(00) = f(01) = f(11) = 0.