关键词 > CO481/CS467/PHYS467

CO481/CS467/PHYS467 ASSIGNMENT 3

发布时间：2022-03-06

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CO481/CS467/PHYS467 ASSIGNMENT 3

1. 4 marks

For any subspace S of the vector space {0, 1}n (over Z2) define S⊥ = {t ∈ {0, 1}n | s · t = 0 for all s ∈ S}.

Let |x + S⟩ = Py∈S |x ⊕ y⟩ .

(a) Show that for any z ∈ Z, either z ∈ S⊥ or z is perpendicular to exactly half of the elements of S .

Hint: For fixed z S⊥, define a one-to-one correspondence between elements s of S that satisfy s · z = 0 and those that satisfy s · z = 1 .

(b) Show that

H⊗n|x + S⟩ = r X ( − 1)x ·z|z⟩ .

z∈S⊥

Hint: Show that for any z ∈ Z, either z ∈ S⊥ or z is perpendicular to exactly half of the elements of S .

2. 3 marks Consider the cyclic shift operator S on three qubits:

|x⟩|y⟩|z⟩ 7→ |z⟩|x⟩|y⟩

for all x,y,z ∈ {0, 1}.

(a) What are the eigenvalues of S?

(b) Note that |000⟩ , |111⟩ , (|100⟩ + |010⟩ + |001⟩), and (|110⟩ + |011⟩ + |101⟩) are eigenvectors with eigenvalue 1.

For the remaining eigenvalues, write a basis of eigenvectors for the corresponding eigenspace. (Hint: you can find eigenvectors that are superpositions of strings with the same Hamming weight.)

(α|0⟩ + β|1⟩)(α|0⟩ + β|1⟩)(α|0⟩ + β|1⟩)

as a linear combination of the given eigenvectors.

3. 2 marks

Let s ∈ {0, 1}n be a secret string of length n.

Suppose you have a black-box that outputs states of the form |0⟩|x⟩ + |1⟩|x ⊕ s⟩ for random values of x.

Describe an algorithm that will find s with high probability using O(n) calls to the black- box.

(Hint: Use ideas from Simon’s algorithm.)

4. 2 marks

Given the 2-qubit state

( |0⟩ + eiϕ |1⟩)( |0⟩ + eiθ |1⟩)

show how to obtain the 1-qubit state

|0⟩ + ei(ϕ −θ) |1⟩

with probability .

5. 4 marks SWAP test

Suppose you are given two states |ψ⟩|ϕ⟩ .

(a) Suppose ⟨ψ|ϕ⟩ = 0. Express |ψ⟩|ϕ⟩ as a linear combination of eigenvectors of the SWAP gate (which maps |a⟩|b⟩ 7→ |b⟩|a⟩).

(b) Suppose you have the promise that ⟨ψ|ϕ⟩ = 0 or 1. Show how to use a controlled- SWAP gate to decide whether ⟨ψ|ϕ⟩ = 0 or 1 with one-sided error probability 0.5 (i.e. in the case of one answer, the answer is always correct, and in the other case the error probability is at most 0.5).

6. Parallelizing phase-queries 3 marks

Let Uϕ denote the unitary operation that maps |0⟩ 7→ |0⟩ and |1⟩ 7→ eiϕ|1⟩ .

Note that Ukϕ = U. However, if a black-box process for implementing Uϕ takes time t then implementing Ukϕ in this serial way takes time kt.

(a) What is the result of applying Uϕ⊗Uϕ⊗···⊗Uϕ = Uk to |00 ... 0⟩+ |11 ... 1⟩ = |0⟩⊗k + |1⟩⊗k?

(b) Show that it is possible to parallelize the implementation of Ukϕ in such a way that all k of the Uϕ gates are applied in parallel (on different qubits). You may perform standard quantum gates on the qubits before and after the application of the k parallel phase gates.

7. 2 marks Hadamard test

Consider two states |ψ⟩ and |ϕ⟩ with the promise that ⟨ψ|ϕ⟩ = 0 or 1.

Suppose you have the state |0⟩|ψ⟩ + |1⟩|ϕ⟩ .

Show how to guess whether ⟨ψ|ϕ⟩ = 0 or 1 with one-sided error probability 0.5.