CS 238 Quantum computing Homework
Individual homework
Prove that all the matrices in the catalog above are unitary. Show that if U is unitary, then U† is unitary.
Copyright By PowCoder代写 加微信 powcoder
Show that the product of two unitary matrices is unitary.
For any complex N × N matrix U , we can uniquely write U = R + iQ, where R and Q have real entries. Show that if U is unitary, then so is the 2N × 2N matrix U′ given in block form by
the result of applying this construction to the Pauli matrix Y .
Question 5. Show that the four Pauli matrices X,Y,Z,I form an orthonormal basis for the space of 2×2 matrices. Thus, we can regard the space of 2×2 matrices as a 4-dimensional complex Hilbert space.
Unitary matrices
Question 1. Question 2. Question 3.
Question 4.
Thus, by doubling the dimension, we can remove the need for complex-number entries. Show
Simulate quantum circuits
Try the quantum circuit simulator called Quirk, linked here: https://algassert.com/ quirk. Submit three files, as follows.
Question 1. Submit a screenshot of a circuit that involves at least one single-qubit gate and at least one 2-qubit gate.
Question 2. Submit a screenshot of an extension of the circuit in (1), where all the new gates are to the right of (1), and where the end result is that the entire circuit is the identity function on the input.
Question 3. Submit an explanation of how you reversed the computation performed by (1), in the sense that first (1) took the qubits from input to output, and then the second half of (2) took that output back to the input.
Individual homework
Hilbert spaces Question 1. Define
H2 =C2 ={α|0⟩+β|1⟩ | α,β∈C} The inner product in H2 is defined by
⟨ α1|0⟩ + β1|1⟩ | α2|0⟩ + β2|1⟩ ⟩ = α1†α2 + β1†β2
for all α1, α2, β1, β2 ∈ C. Show that the inner product satisfies the following four properties:
1. ⟨φ|φ⟩≥0
2. ⟨φ|φ⟩=0ifandonlyif|φ⟩=0.
3. ⟨φ|ψ⟩=⟨ψ|φ⟩†.
4. ⟨φ|λ1ψ1+λ2ψ2⟩=λ1⟨φ|ψ1⟩+λ2⟨φ|ψ2⟩
for any |φ⟩, |ψ⟩, |ψ1⟩, |ψ2⟩ ∈ H2 and for any λ1, λ2 ∈ C.
Question 2. Suppose f, g are Boolean functions on n inputs. Define h(x) = f (x) ⊕ g(x), where ⊕ denotes “exclusive or”. Prove that h is always false (also written 0) if and only if f and g are the same function.
Question 3. For a Boolean string x = x1 . . . xn, define (−1)x = (−1)(x1 +…+xn )
XOR(x) = x1 ⊕…⊕xn Show that (−1)x = 1 if and only if XOR(x) = 0.
Individual homework
Individual homework
Deutsch-Jozsa and Bernstein-Vazirani, classically
The Deutsch-Jozsa problem:
Input: a function f : {0, 1}n → {0, 1}.
Assumption: f is either constant or balanced.
Output: 0 if f is constant; 1 if f is balanced.
Notation: {0, 1} is the set of bits, and {0, 1}n is the set of bit strings of length n. Terminology:
Constant: f is constant if either f always outputs 0 or f always outputs 1. Balanced: f is balanced if f outputs 0 on exactly half of the inputs.
The Bernstein-Vazirani problem:
Input: a function f : {0, 1}n → {0, 1}.
Assumption: f(x) = a × x + b.
Output: a,b.
Notation: {0, 1}n is the set of bit strings of length n, a is an unknown bit string of length n, × is inner product mod 2, + is addition mod 2, and b is an unknown single bit.
The assignment: On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), program solutions to the Deutsch-Jozsa problem and to the Bernstein- Vazirani problem. In each case, treat the input function f as black box that you can call but cannot inspect in any way at all. Each solution will be code that includes one or more calls of f.
Submit two files, one for each problem. Write detailed comments in the code about why it works.
Circuit identities
Let U be a 2×2 unitary matrix. The controlled-U is a two-qubit gate, written C(U), which when applied to qubit registers q1,q2, is defined by:
C(U)[q1,q2] |k1⟩…|kq1⟩…|kq2⟩…|kn⟩ = |k1⟩…|kq1⟩…(Ukq1 |kq2⟩)…|kn⟩
where q1 is the control qubit and q2 is the target qubit, and where every ki ∈ {0, 1}. The
matrix representation of C(U) for application to two qubits is: ()
where I is the 2×2 identity matrix and 0 is the 2×2 matrix in which every entry is 0. Notice that CNOT = C(X), where X is one of the Pauli matrices.
Define SWAP to be the two-qubit gate that swaps the states of two qubit registers: SWAP[q1,q2] |k1 …kq1 …kq2 …kn⟩ = |k1 …kq2 …kq1 …kn⟩
where every ki ∈ {0, 1}.
The assignment: Prove the following properties of controlled gates: 1. SWAP[q1, q2] = C(X)[q1, q2] C(X)[q2, q1] C(X)[q1, q2].
2. C(X)[p, q] = H[q] C(Z)[p, q] H[q].
3. C(Z)[p,q]=C(Z)[q,p].
4. H[p] H[q] C(X)[p, q] H[p] H[q] = C(X)[q, p]. 5. C(X)[p, q] X[p] C(X)[p, q] = X[p] X[q].
6. C(X)[p, q] Y [p] C(X)[p, q] = Y [p] X[q].
7. C(X)[p, q] Z[p] C(X)[p, q] = Z[p].
8. C(X)[p, q] X[q] C(X)[p, q] = X[q].
9. C(X)[p, q] Y [q] C(X)[p, q] = Z[p] X[q]. 10. C(X)[p, q] Z[q] C(X)[p, q] = Z[p] Z[q].
Individual homework
Simon and Grover, classically
Individual homework
Simon’s problem:
Input: a function f : {0, 1}n → {0, 1}n. Assumption: there exists s ∈ {0, 1}n such that
∀x,y : [f(x) = f(y)] iff [(x + y) ∈ {0n,s}].
Output: s.
Notation: {0, 1}n is the set of bit strings of length n, s is an unknown bit string of length n, = is comparison of bit strings of length n, + is pointwise addition mod 2 of bit strings of length n, and 0n is a bit string of length n with all 0.
Grover’s problem:
Input: a function f : {0, 1}n → {0, 1}.
Output: 1 if there exists x ∈ {0, 1}n such that f (x) = 1, and 0 otherwise. Notation: {0, 1}n is the set of bit strings of length n.
The assignment: On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), program a solution to Simon’s problem and to Grover’s problem. Treat the input function f as black box that you can call but cannot inspect in any way at all. Each solution will be code that includes one or more calls of f.
Submit two files, one for each problem. Write detailed comments in the code about why it works.
Quantum states
For a ket |k1 . . . kn⟩, we index the qubits from left to right, starting with index 1.
Question 1. For the following state, suppose we measure the qubit with index 2 in the standard basis and get 0. Show the resulting state. Justify your answer.
√ 12|00⟩ − 12|01⟩ + 14|10⟩ − 47|11⟩
Question 2. Suppose we apply H⊗3 to the state |101⟩, after which we measure the two qubits with indexes 1,2 in the standard basis. What is the probability that we get 11 ?
Question 3. Consider the following circuit with three qubits.
Here H is the Hadamard gate, while each 2-qubit connection is CZ = C(Z).
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. Question 4. Consider the following state.
12|01⟩−12|10⟩+√1 |11⟩ 2
Suppose we measure the qubit with index 1 in the standard basis. What is the probability of getting 0, and if that happens, what is the state of the other qubit? Also, suppose we measure the qubit with index 2 in the standard basis. What is the probability of getting 1, and if that happens, what is the state of the other qubit?
Individual homework
Deutsch-Jozsa in a simulator
The homework called Deutsch-Jozsa and Bernstein-Vazirani, classically defined the Deutsch- Jozsa problem.
Implement four cases of the Deutsch-Jozsa algorithm and run the implementations on the quantum circuit simulator called Quirk, linked here: https://algassert.com/quirk. The first two implementations should be for n = 1, with one implementation using an oracle for a constant function and the other implementation using an oracle for a balanced function. The next two implementations should be for n = 2, with one implementation using an oracle for a constant function and the other implementation using an oracle for a balanced function.
Submit screenshots that show your implementations and illustrate that they work, and submit a file with an explanation of how it works.
Individual homework
Individual homework
Quantum algorithms
Question 1. Show, step by step, that the Deutsch-Jozsa algorithm works for the case of f,
where f(0) = f(1) = 1.
Question 2. For the case of n = 3 and a function f where
f(000) = f(010) = 110 f(100) = f(110) = 011 f(001) = f(011) = 101 f(111) = f(101) = 111
give two different examples of equations that the first step of Simon’s algorithm may produce. Explain what those equations mean.
Question 3. Show, step-by-step, that Grover’s algorithm works for the case of 2 qubits and a function f where f(01) = 1 and f(00) = f(10) = f(11) = 0.
Grover in a simulator
The homework called Simon and Grover, classically defined Grover’s problem.
Implement three cases of Grover’s algorithm and run the implementations on the quantum circuit simulator called Quirk, linked here: https://algassert.com/quirk. The first two implementations should be for n = 2, with one implementations using an oracle for the case where f(00) = 1, and the other implementation using an oracle for the case where f(11) = 1. The third implementation should be for n = 3, using an oracle for the case where f(101) = 1. Submit screenshots that show your implementations and illustrate that they work, and
submit a file with an explanation of how it works.
Individual homework
Four algorithms in Cirq
In Cirq, implement the Deutsch-Jozsa algorithm, the Bernstein-Vazirani algorithm, Simon’s algorithm, and Grover’s algorithm. Write detailed comments in the code about why it works. Run the programs on the simulator. Write a report that covers the following three points.
1. Design and evaluation
• Present the design of how you implemented the black-box function Uf. Assess how easy to read it is.
• Present the design of how you parameterized the solution in n.
• Discuss the number of lines and percentage of code that your four programs share.
Assess how well you succeeded in reusing code from one program to the next.
• Discuss your effort to test the four programs and present results from the testing.
Report on the execution times for different choices of Uf and discuss what you find.
• What is your experience with scalability as n grows? Present a diagram that maps n
to execution time.
2. Instructions
• Present a README file that describes how to input the function f, how to run the program, and how to understand the output.
• List three aspects of quantum programming in Cirq that turned out to be easy to learn and list three aspects that were difficult to learn.
• List three positives and three negatives of the documentation of Cirq. Submit five files, one for each program and one with the report.
Group homework
QAOA and Shor in Cirq
In Cirq, implement QAOA and Shor’s algorithm. Write detailed comments in the code about why it works. Run the programs on the simulator. Write a report that covers the following two points.
1. Design and evaluation
• Present the design of how you parameterized the solution in n.
• Discuss your effort to test the two programs and present results from the testing.
• What is your experience with scalability as n grows? Present a diagram that maps n to execution time.
2. Instructions
• Present a README file that describes how to provide input, how to run the program, and how to understand the output.
Submit three files, one for each program and one with the report.
Group homework
Implement a quantum circuit simulator
On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), implement a quantum circuit simulator for a subset of QASM programs. The subset of QASM is defined by the grammar given on the course webpage, under Modules, in the section Quantum Assembly Language (QASM).
Write a report that covers the following two points.
1. Design and evaluation
• Present the design of how you parameterized the solution in n.
• Discuss your effort to test your simulator and present results from the testing.
• What is your experience with scalability as n grows? Present a diagram that maps n to execution time.
2. Instructions
• Present a README file that describes how to provide input, how to run the program, and how to understand the output.
Submit two files, one with your program and one with the report.
Individual homework
Run on a quantum computer
Port your Cirq implementations of Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, QAOA and Shor’s algorithm to Qiskit. Run your implementations on the IBM quantum computer. Modify the programs as needed to meet the restrictions of the quantum computer.
Write a report that covers the following three points.
1. Evaluation
• Discuss your effort to test the programs and present results from the testing. Run each program multiple times and present statistics of the results.
• What is your experience with scalability as n grows? Present a diagram that maps n to execution time.
• Compare your results from running Cirq programs on the IBM quantum computer with your results from running those same Cirq programs on the simulator.
2. Instructions
• Present a README file that describes how to provide input, how to run the program, and how to understand the output.
3. Experience
• Which modifications of the programs did you have to make when moving from the simulator to the quantum computer?
Submit seven files, one for each program and one with the report.
Group homework
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com