Suppose Alice and Bob hold one qubit each of an arbitrary two-qubit state $|\psi \rangle$ that is possibly entangled. They can apply local operations and are allowed classical communication. Their goal is to apply the CNOT gate to their state $| \psi \rangle$. How can they achieve this using two ebits of communication?

I'm pretty lost on where to start this problem. I would assume that if Alice has the control bit for the CNOT, I would need to follow a protocol something like:

  1. tensor $|\psi\rangle$ with the EPR pairs
  2. Alice applies some local operations and measures the EPR pairs
  3. Alice classically communicates something to Bob
  4. Bob applies some local operations with the information sent classically by Alice
  5. CNOT completed.

However, it is possible that Alice would only use one ebit, and Bob would use one as well to communicate something back. I'm not sure.

Really I just feel like I have no clue where to start this problem. Initially, some guidance on how to approach this would perfect, because right now i'm just poking around at a 6 qubit state.

A second idea I just had: might it be beneficial to instead of looking at the complete state, look at Alice and Bob's local density matrices?

  • 3
    $\begingroup$ Hint: forgot about the problem for a second, and write down some of the tasks you can use an ebit to perform. Are any of them useful in this context? $\endgroup$ Commented Oct 5, 2018 at 4:30
  • $\begingroup$ @CraigGidney Funny enough, teleportation is all I actually know how to do with ebits, so I should have been thinking along those lines already. $\endgroup$
    – Joe
    Commented Oct 5, 2018 at 14:09

1 Answer 1


Here is an idea of how could this be solved. It is based on teleportation.

  • First, Alice teleports her qubit by means of one of the EPR pairs that she shares with Bob. In order to do that, she sends the classical information she obtains by measuring her EPR halve and her qubit.
  • Bob uses the clasical information received in order to reconstruct the qubit in his side. Now teleportation is completed, and Bob posseses the whole qubit system.
  • As local operations are allowed, now Bob performs the CNOT gate on the two qubit system.
  • Now that the operation has been done, Bob uses both the second EPR pair and classical information in order to teleport the first qubit back to Alice.
  • Alice reconstructs the qubit by appying the operations in her halve of the EPR pairs depending on the information classically obtained from Bob. Teleportation is done again.

As a consequence, Alice ercovers the qubit that she teleported back, but in this case after applying the CNOT that was desired. This way, the objective is succesfully done while fulfilling the constraint of using just two ebits (in this case the two EPR pairs for teleportation), and the allowed classical communication.

  • $\begingroup$ Josu That's very clever. Thank you for the outline of the process. As a follow-up, would you say it's fair to say that most problems like this are solved through clever uses of Quantum Teleportation? $\endgroup$
    – Joe
    Commented Oct 5, 2018 at 14:08
  • 1
    $\begingroup$ I would say that if the problem implies a shared quantum state between two parties and some processing of the state which needs to be locally done by a 2-qubit gate, then yes, if EPR pairs and classical communication are avaible. $\endgroup$ Commented Oct 5, 2018 at 15:35
  • 1
    $\begingroup$ Plus: Now that you have a circuit diagram that accomplishes the task in a straightforward way, you can now try to rearrange the operations for optimization. $\endgroup$
    – AHusain
    Commented Oct 5, 2018 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.