[SOLVED] Quantum computing (cs5100) : problem set 1

1. (a) Prove that there doesn’t exist a 2-qubit unitary U that maps |ϕ⟩|0⟩ → |ϕ⟩|ϕ⟩ for
every qubit |ϕ⟩. (8 marks)
(b) Prove that there doesn’t exist a 2-qubit unitary U that maps |0⟩|0⟩ → |0⟩|0⟩ and
|+⟩|0⟩ → |+⟩|+⟩. (15 marks)
2. Alice and Bob prepare an EPR pair, that is, two qubits in the state √
1
2
(|00⟩ + |11⟩).
They each take one qubit home. Suddenly, Alice decides she wishes to convey one of
4 messages to Bob; in other words, she wants to convey a classical string ab ∈ {0, 1}
2
to Bob. Alice does the following in the privacy of her own home: First, if a = 1 she
applies a NOT gate to her qubit (else if a = 0 she does nothing here). Next, if b = 1,
she applies a Z (phaseflip) gate, 
1 0
0 −1

, to her qubit (else if b = 0 she does nothing
here).
(a) Write the resulting 2-qubit state for the four different cases that ab could take.
(8 marks)
(b) Suppose Alice sends her half of the state to Bob, who now has two qubits. Show
that Bob can determine both a and b from his state. (14 marks)
3. Let θ ∈ [0, 2π), Uθ =

cos θ − sin θ
sin θ cos θ

, |ϕ⟩ = Uθ|0⟩ and |ϕ
⊥⟩ = Uθ|1⟩.
1
(a) Show that ZX|ϕ
⊥⟩ = |ϕ⟩. Recall, X is the NOT gate. (5 marks)
(b) Show that an EPR-pair, √
1
2
(|00⟩ + |11⟩), can also be written as √
1
2
(|ϕ⟩|ϕ⟩ +
|ϕ
⊥⟩|ϕ
⊥⟩). (10 marks)
(c) Suppose Alice and Bob start with an EPR-pair. Alice applies U
−1
θ
to her qubit
and then measures it in the standard computational basis. What (pure) state
does Bob have if her outcome was 0, and what (pure) state does he have if her
outcome was 1? (8 marks)
(d) Suppose Alice knows the number θ but Bob does not. Give a protocol that uses
one EPR-pair and 1 classical bit of communication where Bob ends up with the
qubit |ϕ⟩ (in contrast to general teleportation of an unknown qubit, which uses 1
EPR-pair and 2 bits of communication). (10 marks)
4. Recall the CHSH game we saw in class:
• Alice gets x ∈ {0, 1} and Bob gets y ∈ {0, 1}
• Alice outputs a ∈ {0, 1} and Bob outputs b ∈ {0, 1} (recall they can’t communicate)
• the success condition for the game is a ⊕ b = x ∧ y.
• their goal is to succeed with high probability when the inputs are given uniformly
at random.
Now suppose that Alice and Bob can build magic “non-local boxes” that would allow
them to succeed at the CHSH game with 100% probability. That is, a non-local box is
an imaginary device that has an input-output port at Alice’s and another one at Bob’s,
even though they are spatially distant; furthermore, Alice can put a bit x ∈ {0, 1} into
the box and get back a bit a ∈ {0, 1}, Bob can put a bit y ∈ {0, 1} into the box and
get back a bit b ∈ {0, 1}, and these bits will always satisfy a⊕b = x∧y. Also, inspired
by entanglement, we assume that a non-local box is a one-shot device, that is, one box
can only be used once.
(a) Assume that Alice and Bob are spatially distant, but they have access to n of these
magical non-local boxes. Assume also that Alice knows n bits x1, . . . , xn ∈ {0, 1},
Bob knows n bits y1, . . . , yn ∈ {0, 1}, and they wish to compute the “inner product
mod 2” function of their bits,
IP2(x1, . . . xn, y1, . . . , yn) = x1 · y1 + · · · + xn · yn (mod 2).
Show that by using the non-local boxes, and then allowing one classical bit of communication from Alice to Bob, Bob can learn the value IP2(x1, . . . , xn, y1, . . . , yn).
(10 marks)
(b) Show that every Boolean function f : {0, 1}
n → {0, 1} can also be computed by a
polynomial over F2. Recall F2 is the field with two elements {0, 1} with addition
and multiplication being performed (mod 2). (8 marks)
2
(c) Let f(x1, . . . , xn, y1, . . . , yn): {0, 1}
2n → {0, 1} be a Boolean function over 2n
variables. Now suppose Alice knows x1, . . . , xn, Bob knows y1, . . . , yn, and they
wish to compute f applied to their two inputs: f(x1, . . . , xn, y1, . . . , yn). Show
that by using as many non-local boxes as they want, and then using two classical
bits of communication, both of them can learn the value f(x1, . . . , xn, y1, . . . , yn).
(Quantify the number of non-local boxes used in your protocol.) (14 marks)
5. We had seen one-qubit teleportation in class. In fact, entangled states can also be
teleported. Suppose Alice has prepared a two-qubit entangled state |ϕ⟩ := α|00⟩ +
β|11⟩. She wishes to teleport one half of |ϕ⟩ to Bob and another half to Charlie, so
that in the end Bob and Charlie will hold halves of the entangled state |ϕ⟩ despite
never physically interacting. Give a protocol to achieve this. (10 marks)
6. Alice and Bob prepare the following 2-qubit state:
|ψ⟩ = H ⊗ H

1
√
3
|00⟩ +
1
√
3
|01⟩ +
1
√
3
|10⟩

.
Alice now takes control of the first qubit and Bob takes control of the second qubit.
Each of Alice and Bob now flips a coin and does the following: If they flip Tails, they
directly measure their qubit; if they flip Heads, they first apply a Hadamard to their
qubit and then they measure.
(a) Prove the following statements: (10 marks)
If Alice flips T and Bob flips T, it’s possible A & B will measure 1, 1 respectively.
If Alice flips T and Bob flips H, it’s impossible A & B will measure 1, 0 respectively.
If Alice flips H and Bob flips T, it’s impossible A & B will measure 0, 1 respectively.
If Alice flips H and Bob flips H, it’s impossible A & B will measure 1, 1 respectively.
The next two questions carry zero marks and needn’t be turned in. But it would
be good if you spend some time thinking about them.
(b) Lucien says the following: “Let’s consider the situation before any coin flips or
measurement happens, and try to decide what outcomes the qubits are capable
of producing when measured.
• Consider the first statement in (a). Since it’s possible that Alice will flip Tails
and Bob will flip Tails, we conclude that prior to any coin flips/measuring,
it’s possible for Alice’s qubit to register 1 after being directly measured.
• Now consider the second statement in (a). Since Alice’s qubit is capable of
generating a 1 when she flips Tails, it must be impossible for Bob’s qubit
to produce a 0 when he flips Heads, and consequently Hadamards-thenmeasures.
• Let’s repeat the previous two bullet points, interchanging ‘Alice’ and ‘Bob’.
By the first statement in (a), we conclude that prior to any coin flips/measuring,
it’s possible for Bob’s qubit to register a 1 when directly measured. Hence
3
by the third statement in (a), since Bob’s qubit is capable of generating a 1
when directly measured, we conclude that it must be impossible for Alice’s
qubit to produce a 0 when she Hadamards-then-measures.
• We’ve concluded that in case of flipping Heads, for both Alice and Bob it’s
impossible for them to register a 0 when they Hadamard-and-measure; i.e.,
they must both register a 1 in this case. But this contradicts the fourth
statement in (a).”
Critique the four bullet points above. Do you agree or disagree with Lucien?
(c) Read Scott Aaronson’s blog post from Sept. 25, 2018, It’s hard to think when
someone Hadamards your brain. Critique his argument. Do you agree or disagree
with him?
4