CS 239 Quantum Programming Winter 2022
Midterm Exam
Feb 10, 2021: 90 minutes. On the first page you submit, write your name and UCLA id. Submit a single pdf file to bruinlearn.
Each of questions 1–10 is worth 5 points, and each of questions 11-15 is worth 10 points.
Copyright By PowCoder代写 加微信 powcoder
1. Suppose A, B are quantum registers that each holds a single qubit. Suppose also that we have no information about the content of A while we know that B holds |0⟩. Show a circuit that sets A to |1⟩; the circuit is allowed to change the content of B. Justify your answer.
2. Suppose f is a function from bitstrings of length 2 to bits, and that f(x) = (11·x)⊕1, where · is the dot product, and ⊕ is addition mod 2. Suppose Uf |x⟩ |b⟩ = |x⟩ |b ⊕ f(x)⟩. Show a circuit that implements Uf . Justify your answer.
3. If f is a function from bitstrings of length 8 to bits, and f(x) = ax + b, where a is a bitstring of length 8, and b is a bit, how many times will we have to run the Bernstein- Vazirani circuit for f to determine whether a = 1 with probability at least 95 percent? Justify your answer.
4. If f is a function from bitstrings of length 32 to bitstrings of length 32, how many times will we have to run Simon’s circuit for f to determine the solution to Simon’s problem with probability at least 95 percent? Justify your answer.
5. If f is a function from bitstrings of length 32 to bits, such that for a single bitstring x1 of length 32, we have f(x1) = 1, while for all other bitstrings x of length 32, we have f(x) = 0. How many times will we have to iterate the loop in Grover’s algorithm to determine x1 with high probability? Justify your answer.
6. Calculate the following tensor product.
( 1 1 ) (0 √1 )
0√√⊗2 2 2 1√1
7. Calculate the following tensor product.
(1 1)(3 4)
√2|0⟩ − √2|1⟩ ⊗ 5|0⟩ − 5|1⟩
8. What state do we get if we apply (Z ⊗ H) CNOT to the following state?
35 |01⟩ − 45 |10⟩
9. For the following state, suppose we measure the left qubit and get 1. Show the
resulting state. Justify your answer. 3411
5√2|00⟩ − 5√2|01⟩ + 2|10⟩ − 2|11⟩ 1
10. Consider the following state. 431
5√2|00⟩ + 5√2|01⟩ + √2|10⟩
Suppose we measure the left qubit. What is the probability of getting 0, and if that happens, what is the state of the other qubit? Also, suppose we measure the right qubit. What is the probability of getting 1, and if that happens, what is the state of the other qubit?
11. Consider the following circuit with three qubits.
Suppose that at the end, we measure all three qubits. What is the probability that we will get 101 ? Justify your answer.
12. Let P = 1 0 . Phrase the following diagram as an equation and prove that it is 0i
correct, or show that it is wrong.
13. Show, step by step, that the Deutsch-Jozsa algorithm works for the case of f, where f(0) = 0 and f(1) = 0.
14. For the case of n = 3 and a function f where
f(000) = f(101) = 001 f(001) = f(100) = 010
f(010) = f(111) = 100 f(011) = f(110) = 111
give two different examples of equations that the first step of Simon’s algorithm may produce. Explain what those equations mean. Show how producing a sufficient number of equations can lead to solving Simon’s problem. Justify your answer. What is the solution to Simon’s problem in this case?
15. Consider a function f from 2 bits to bits, where we have f(00) = f(01) = 0 and f(10) = f(11) = 1. The goal of Grover’s algorithm for this case is to output either 10 or 11. What is better: repeat the main loop of Grover’s algorithm once or twice? Show step-by-step calculations that justify your answer.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com