CSE 599Q: Homework #3


Due: Fri, Nov 4 @ 11:59pm
Gradescope Link

1. No cloning of non-orthogonal states [6 pts]

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*}\]
  1. [2 pts] Assume these equalities hold and compute the inner product of the left sides with each other.

  2. [2 pts] Use this to conclude something about the possible values of \(\ip{\phi}{\psi}\).

  3. [2 pts] What does this imply about the relationship between \(\ket{\phi}\) and \(\ket{\psi}\)?

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

3. 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.)

4. 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\):

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