1. Measuring to defeat corruption [8 pts]

Consider a qubit $\ket{\psi}$. Suppose that at every time step, corruption from the environment applies the unitary rotation operator $R_{\epsilon} = \begin{bmatrix} \cos (\epsilon) & - \sin(\epsilon) \\ \sin(\epsilon) & \cos(\epsilon) \end{bmatrix}$ to $\ket{\psi}$, where $\epsilon = \pi/2N$, and $N \geq 1$ is some integer parameter.

1. [2 pts] If $\ket{\psi} = \ket{0}$ and you don’t do any measurements, what is the state after $N$ corruption steps? In other words, what is $R_{\epsilon}^N \ket{0}$?

2. [2 pts] Suppose you know that $\ket{\psi}$ is initially in state $\ket{0}$ or $\ket{1}$. Describe a way to measure the state $\ket{\psi}$ after the corruption is applied at every step so that $\ket{\psi}$ is very likely to remain in state $\ket{0}$ or $\ket{1}$.

3. [4 pts] Under this scheme, analyze the probability that, despite the corruption, $\ket{\psi}$ is equal to its initial state (which was either $\ket{0}$ or $\ket{1}$) after every one of the $N$ measurements.

2. A quantum circuit [12 pts]

Consider the following quantum circuit that takes 3 input qubits:

Note that each $H$ represents a Hadamard gate, and $\oplus$ represents a controlled not (CNOT) gate.

1. [6 pts] Determine (with proof) the state of the three qubits at the end of the circuit’s operation.

2. [6 pts] Suppose the top two qubits are mesured in the standard basis. Determine the probabilities of the possible outcomes, and what state the third qubit collpases to in each of the four cases.

3. Quantum architecture [8 pts]

Show how to use only CNOT gates to build a SWAP gate. Recall that SWAP is a 2-qubit gate that takes $\ket{b_0 b_1}$ to $\ket{b_1 b_0}$ for all $b_0,b_1 \in \{0,1\}$.

4. Hardy's Paradox [14 pts]

Suppose that Alice and Bob prepare the $2$-qubit state:

$$\ket{\psi} = (H \otimes H) \left(\frac{1}{\sqrt{3}} \ket{00} + \frac{1}{\sqrt{3}} \ket{01} + \frac{1}{\sqrt{3}} \ket{10}\right)$$

Alice takes control of the first qubit, and Bob takes control of the second.

Each of them flips an (independent) 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 measure.

1. [4 pts] Show the following four implications based on the outcomes of Alice and Bob’s coin flips:

   • $A: T, B: T \implies$ It’s possible that they will measure outcome $A: 1, B: 1$.

   • $A: T, B: H \implies$ It’s impossible that they will measure outcome $A : 1, B: 0$.

   • $A: H, B: T \implies$ It’s impossible that they will measure outcome $A: 0, B:1$.

   • $A: H, B: H \implies$ It’s impossible that they will measure outcome $A:1, B:1$.

2. [10 pts] Contemplate the following argument.

   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."

   • One one hand, 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-then-measures.
   • 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 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 the argument?

5. An unknown Pauli operator [18 pts]

The following four matrices are the single qubit Pauli operators:

$$I = \begin{bmatrix} 1 & 0 \\ 0 &1 \end{bmatrix} \quad X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \quad Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \quad Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \quad$$

Suppose you are given a single-qubit gate $U$ and you are allowed to apply it only once. All you know is that $U \in \{I,X,Y,Z\}$.

1. [6 pts] Suppose you are allowed to evaluate $U$ on an arbitrary single qubit state $\ket{\psi} = \alpha_0 \ket{0} + \alpha_1 \ket{1}$ of your choice, and then measure in any orthonormal basis of your choice. Prove that it is impossible to choose a measurement and an input state $\ket{\psi}$ such that you can determine which Pauli operator $U$ is with certainty.

2. [4 pts] Show that the four states $(U \otimes I) \frac{1}{\sqrt{2}} \left(\ket{00} + \ket{11}\right)$ are pairwise orthogonal as $U$ ranges over $\{I,X,Y,Z\}$.

3. [8 pts] Suppose that you are allowed to evaluate $U \otimes I$ once on a 2-qubit state

   $$\ket{\psi} = \alpha_{00} \ket{00} + \alpha_{01} \ket{01} + \alpha_{10} \ket{10} + \alpha_{11}\ket{11},$$

   and then you can measure $(U \otimes I) \ket{\psi}$ in an arbitrary orthonormal basis of $\C^4$.

   Show that by choosing $\ket{\psi}$ and a measurement basis appropriately, you can determine with certainty which Pauli operator is implemented by $U$.

Remark: Suppose you send a photon through two polarization filters that are each oriented either horizontally or vertically (so there are four possibilities). Then the Pauli operators represent the action of those four configurations on a photon, and the first part of the problem asks you to show that there is no measurement that can determine the configuration from passing a single photon through the filters.

The second part of the problem asks you to show that if you first entangle two photons and then second one photon through the pair of filters, then by measuring the joint pair of photons, you can actually figure out the configuration with certainty.