CSE 599Q: Homework #3

Due: Wed, Feb 16 @ 11:59pm
Gradescope Link

1. Sorta-dense coding [16 pts]

  1. [8 pts] Alice and Bob share the entangled state . Now Alice wants to send two classical bits to Bob by sending him a single qubit.

    Suppose that Alice wants to send . If , she applies a gate to her qubit in the EPR pair, else she does nothing. If , she applies the gate to her qubit, else she does nothing.

    Then she sends her half of to Bob (who then possesses all of ). Find a basis so that Bob can measure and determine exactly Alice’s messages .

  2. [8 pts] Find a circuit that uses only gates, arbitrary -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 -qubit quantum circuit that does some internal measurements, and suppose the first measurement is at step . It measures the state of the th qubit in the standard basis and outputs a classical bit . And the corresponding state collapses to the outcome.

Now introduce an qubit to the circuit, initialized to the state . And replace the measurement on qubit (at step ) by a gate whose control bit is the qubit, and whose target bit is the new qubit. Finally, you immediately apply a measurement to the qubit, and treat its readout as the result of the original measurement. Then you ignore the 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 and a string and creates the quantum state . The coin is then , and the bank stores the pair in its database.

Now to verify that the coin is valid, the bank measures every qubit of in the correct basis, using if and if , and checks that the measurement outcomes agree with .

Suppose you want to try and create two coins from 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 :

4. A quantum threeway protocol [16 pts]

Suppose that Alice and Bob share an EPR pair and Alice and Charlie share a distinct EPR pair .

Now Alice creates a third EPR pair and she uses the quantum teleportation protocol to teleport one half of to Bob and one half of 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 and we have access to a function such that

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

Suppose now that the function is noisy, in the sense that, for some noise parameter , we only have the guarantee

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

  2. [6 pts] What happens when ? Explain why there is no hope for an algorithm to recover in this case.