1. Sorta-dense coding [16 pts]

1. [8 pts] Alice and Bob share the entangled state $\ket{\psi} = \frac{1}{\sqrt{2}} (\ket{00}-\ket{11})$. Now Alice wants to send two classical bits to Bob by sending him a single qubit.

   Suppose that Alice wants to send $m_1 m_2 \in \{0,1\}^2$. If $m_1=1$, she applies a $\mathsf{NOT}$ gate to her qubit in the EPR pair, else she does nothing. If $m_2=1$, she applies the gate $Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$ to her qubit, else she does nothing.

   Then she sends her half of $\ket{\psi}$ to Bob (who then possesses all of $\ket{\psi}$). Find a basis so that Bob can measure and determine exactly Alice’s messages $m_1 m_2$.

2. [8 pts] Find a circuit that uses only $\mathsf{CNOT}$ gates, arbitrary $1$-qubit gates, and only measuremnts in the standard basis that always outputs Alice’s message as the outcome.

2. The Principle of Deferred Measurement [16 pts]

You will now show that we can always convert quantum circuits with internal measurements into quantum circuits where all measurements occur at the end. This is nice because, as we know, a circuit without measurements just corresponds to multiplication by a unitary matrix.

So suppose you have an $n$-qubit quantum circuit that does some internal measurements, and suppose the first measurement is at step $t$. It measures the state of the $k$th qubit in the standard basis and outputs a classical bit $b \in \{0,1\}$. And the corresponding state collapses to the outcome.

Now introduce an $(n+1)^{\mathrm{st}}$ qubit to the circuit, initialized to the state $\ket{0}$. And replace the measurement on qubit $k$ (at step $t$) by a $\mathsf{CNOT}$ gate whose control bit is the $k^{\mathrm{th}}$ qubit, and whose target bit is the new $(n+1)^{\mathrm{st}}$ qubit. Finally, you immediately apply a measurement to the $(n+1)^{\mathrm{st}}$ qubit, and treat its readout as the result $b$ of the original measurement. Then you ignore the $(n+1)^{\mathrm{st}}$ qubit for the rest of the computation.

1. [10 points] Show that this exactly simulates the original circuit’s operation.

2. [6 points] Explain how this gives a way of taking any quantum circuit and converting it into one where all measurements occur only at the final step. (The idea is that you want to be able to reproduce all the values output by the internal measurements in the circuit, using measurement gates that only happen at the end.)

3. Quantum money attacks [16 pts]

Recall that to create a quantum coin, the bank generates a serial number $s \in \{0,1\}^n$ and a string $q \in \{0,1,+,-\}^n$ and creates the quantum state $\ket{\psi} = \ket{q_1} \ket{q_2} \cdots \ket{q_n}$. The coin is then $(s,\ket{\psi})$, and the bank stores the pair $(s,q)$ in its database.

Now to verify that the coin is valid, the bank measures every qubit of $\ket{\psi}$ in the correct basis, using $\{\ket{0},\ket{1}\}$ if $q_i \in \{0,1\}$ and $\{\ket{+},\ket{-}\}$ if $q_i \in \{+,-\}$, and checks that the measurement outcomes agree with $q$.

Suppose you want to try and create two coins from $(s,\ket{\psi})$ that both pass the bank’s check. By the No-Cloning theorem, we can’t do this exactly, but we saw in class a way to succeed with probability $(5/8)^n$:

• You measure every qubit of $\ket{\psi}$ in the $\{\ket{0},\ket{1}\}$ basis, getting a string of outcomes $r = r_1 r_2 \ldots r_n \in \{0,1\}^n$.

  Now you create two copies of the state $\ket{\phi_1},\ket{\phi_2} = \ket{r_1} \ket{r_2} \cdots \ket{r_n}$, and try to get the bank to verify $(s,\ket{\phi_1})$ and $(s,\ket{\phi_2})$. This requires that every qubit of both states passes the Bank’s test. If $q_i \in \{0,1\}$, then our measurement of $\ket{q_i}$ will give the true value with probability $1$. If $q_i \in \{+,-\}$, then our measurement will give either $0$ or $1$, and when the Bank checks that coordinate, there will be a $1/2$ chance to pass. Since the $i$th qubit gets checked once in $\ket{\phi_1}$ and once in $\ket{\phi_2}$, in this case our chance of passing is $\frac14 = \frac12 \cdot \frac12$. So overall, our chance of passing in a single qubit is

  $$\frac12 \cdot 1 + \frac12 \cdot \frac14 = \frac{5}{8}.$$

  And our chance that both $(s,\ket{\phi_1})$ and $(s,\ket{\phi_2})$ get verified in all $n$ qubits is therefore $(5/8)^n$.

• Now you will try to do better: Create a three qubit state where the first two are initialized to $\ket{0}$, and and the third is one of the qubits from the bank coin. Then apply a $3$-qubit unitary gate whose effect is the following:

  $$\begin{align*} \ket{000} &\mapsto \frac{\sqrt{3}}{2} \ket{000} + \frac{\ket{110}+\ket{101}+\ket{011}}{\sqrt{12}} \\ \ket{001} &\mapsto \frac{\sqrt{3}}{2} \ket{111} + \frac{\ket{001}+\ket{010}+\ket{100}}{\sqrt{12}}. \end{align*}$$

  Finally, you will output the second two qubits. (Recall that you are trying to create two copies, so it’s good that you are getting two qubits from every qubit of the quantum coin.)

  Analyze the probability that you pass the bank’s verification test for both of the (fraudulent) coins you created.

4. A quantum threeway protocol [16 pts]

Suppose that Alice and Bob share an EPR pair $\ket{\psi_{AB}} = \frac{1}{\sqrt{2}} (\ket{00}+\ket{11})$ and Alice and Charlie share a distinct EPR pair $\ket{\psi_{AC}} = \frac{1}{\sqrt{2}} (\ket{00}+\ket{11})$.

Now Alice creates a third EPR pair $\ket{\phi} = \frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ and she uses the quantum teleportation protocol to teleport one half of $\ket{\phi}$ to Bob and one half of $\ket{\phi}$ to Charlie.

Show that now Bob and Charlie share an EPR pair.

5. Bernstein-Vazirani with a noisy oracle [16 pts]

Recall that in the Bernstein-Vazirani problem, there is a hidden string $s \in \{0,1\}^n$ and we have access to a function $f : \{0,1\}^n \to \{0,1\}$ such that

$$f(x) = s \cdot x \bmod 2 = (s_1 x_1 + s_2 x_2 + \cdots + s_n x_n) \bmod 2.$$

The goal is to recover the secret $s$, and the Bernstein-Vazirani algorithm allows us to do this with only a single quantum query to $f$.

Suppose now that the function $f$ is noisy, in the sense that, for some noise parameter $\varepsilon > 0$, we only have the guarantee

$$\frac{\#\! \left\{ x \in \{0,1\}^n : f(x) = s\cdot x\bmod 2\right\}}{2^n} \geq 1-\varepsilon.$$

1. [10 pts] Calculate a lower bound on the probability that a single run of the Bernstein-Vazirani algorithm nevertheless succeeds in recovering $s$ and make sure to justify your calculation.

2. [6 pts] What happens when $\varepsilon = 1/2$? Explain why there is no hope for an algorithm to recover $s$ in this case.