Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 190/264: Quantum Computation Homework 4
Note: graduate students are not required to do problem 5, but are required to probelm 6. Undergraduates are required to do problems 1-5.
1. The function f : {0, 1} 2 → {0, 1} is defined as follows: f(00) = 0 f(01) = 1 f(10) = 1 f(11) = 0 In this question, you will simulate the Deutsch-Jozsa algorithm for the function f.
(a) The unitary operator Uf maps |xi|yi to |xi|y ⊕ f(x)i, where x is a 2-bit string and y is a single bit. Give the matrix representation of Uf .
(b) Give the current state of the algorithm after each step:
• Start with |00i|0i
• Apply H⊗2 ⊗ I.
• Apply Uf .
• Apply I ⊗2 ⊗ Z.
• Apply Uf . • Apply H⊗2 ⊗ I.
(c) Drop the last qubit from the current register and measure the first two qubits. What are the possible outcomes and what are the probabilities of each outcome? What information tells you whether f is balanced or all 0’s?
2. The function f : {0, 1} 3 → {0, 1} 2 is defined as follows:
f(000) = 11 f(100) = 00 f(001) = 01 f(101) = 10 f(010) = 00 f(110) = 11 f(011) = 10 f(111) = 01
(a) The inputs are paired so that for x 6= x 0 , f(x) = f(x 0 ) if and only if x = x 0 ⊕ a for some fixed a. Can you figure out a by inspection? 1 2
(b) In this question, you will simulate Simons’s algorithm for the function f. The unitary operator Uf maps |xi|yi to |xi|y⊕f(x)i, where x is a 3-bit string and y is a 2-bit string. The operator ⊕ is bit-wise addition, mod 2.
Give the current state of the algorithm after each step. For the first measurement, give each possible outcome, the probability of that outcome, and the state that results from that outcome. You can assume that the result of the first measurement is 01 in order to continue with the rest of the algorithm. For the second measurement, give the possible outcomes and their probabilities.
• Start with |000i|00i
• Apply H⊗3 ⊗ I ⊗2 .
• Apply Uf . • Measure the last two qubits.
• Drop the last two qubits and apply H⊗3 .
• Measure the first three qubits.
(c) Verify that a string x is a possible outcome of the last measurement if and only if x · a = 0.
3. There is a 5-bit string a such that for each row x in the matrix below, x·a = 0. Use Gaussian elimination to derive the string a. 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1
4. Use one or more Fredken gate to simulate the OR (or disjunction) operation. The disjunction operation takes two bits as input and outputs 1 if and only if at least one of the two input bits is 1.
5. Consider the small circuit shown below. 3 Suppose that U|00i = α0|00i + α1|01i + α2|10i + α3|11i U|01i = β0|00i + β1|01i + β2|10i + β3|11i
(a) If the third qubit is measued at the end of the circuit, what are the probabilities of each outcome and the resulting state after each outcome?
(b) Suppose that the third qubit is measured and then the first two qubits are measured. What are the probabilities of the outcomes of the measurement of the first two qubits. (You will need to consider the probabilities of the outcome of measuring the third qubit and then determine the probabilities for the first two qubits conditioned on the outcome from the measurement of the third qubit.)
(c) Suppose that at the end of the circuit, just the first two qubits are measured. What is the probabilityof each outcome?
For graduate students: skip problem 5, and do the following problem:
6. Prove the principle of deferred measurement: suppose a unitary operator V ⊗ I acts on a state |φi of n + m qubits, where V acts on the first n qubits. Consider the distribution D that results from measuring the first n qubits after V ⊗ I is applied. Prove that this is the same distribution that results from first measuring the last m qubits, applying V ⊗I and then measuring the first n qubits.