Suppose that \(\ket{\phi}\) and \(\ket{\psi}\) are two different but non-orthogonal quantum states, i.e., \(\ip{\phi}{\psi} \neq 0\) and \(\ip{\phi}{\psi} \neq 1\). In this problem, your goal is to show that there is no unitary operation \(U\) with the behavior:
\[\begin{align*} U \left(\ket{\phi} \otimes \ket{0}\right) &= \ket{\phi} \otimes \ket{\phi} \\ U \left(\ket{\psi} \otimes \ket{0}\right) &= \ket{\psi} \otimes \ket{\psi} \\ \end{align*}\][2 pts] Assume these equalities hold and compute the inner product of the left sides with each other.
[2 pts] Use this to conclude something about the possible values of \(\ip{\phi}{\psi}\).
[2 pts] What does this imply about the relationship between \(\ket{\phi}\) and \(\ket{\psi}\)?
[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\).
[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.
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.
[10 points] Show that this exactly simulates the original circuit’s operation.
[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.)
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.
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.