Superdense Coding & Quantum Teleportation

Lecture 12: Superdense Coding & Quantum Teleportation Scribed by: Sebastian Bauer Department of Mathematics, MIT October 14, 2003 1 Superdense Coding & Quantum Teleportation 1.1 Repetition 1. EPR pair: √12 (|01� − |10�) , which is in some sense (as we will soon see) equivalent to 2. √1 2 (|00� + |11�) Think of this EPR pair as shared between two people, Alice and Bob. Alice owns the first qubit, Bob the second. Alice can change from 1) to 2) without Bob’s help: � � �� 1 0 i σy = (1) σy (1) · √ (|01� − |10�) −i 0 2 1 = √ (i |11� + i |00�) (2) 2 i (3) = √ (|11� + |00�) 2 Recall the Bell basis: 0 1 1 0 � 0 i −i 0 � � � � 1 0 0 −1 � 1 σx (1) · √ (|01� − |10�) = 2 1 σy (1) · √ (|01� − |10�) = 2 1 σz (1) · √ (|01� − |10�) = 2 1 1 √ (|01� − |10�) 2 1 √ (|11� − |00�) 2 i √ (|11� + |00�) 2 1 √ (|01� + |10�) 2 (4) (5) (6) (7) P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 2 Any pair of the Bell basis states has inner product 0, e.g. 1 1 1 (�01| − �10|) · (|01� + |10�) = (�01|01� − �10|01� + �01|10� − �10|10�) = (1 − 0 + 0 − 1) = 0 2 2 2 ⇒ The 4 Bell states (4)-(7) constitute an orthonormal basis for the space of state for 2 qubits. 1.2 Superdense Coding Theorem 1. The amount of information extractable from one qubit is 1 bit. Theorem 2. An EPR pair cannot carry any information. We won’t prove these theorems now; perhaps in a later lecture. So if Alice sends 1 qubit to Bob, can she only encode 1 bit of information? EPR pair •• Alice Bob •�������� • ����� ����� 2 bits � 1 qubit ����� t Alice and Bob have shared an EPR pair in the past, and now Alice sends a qubit. This can transmit 2 bits of info. � 2 bits Explanation: • Alice and Bob start with an EPR pair the second qubit. √1 2 (|01� − |10�), where Alice owns the first and Bob • Alice applies one of the operations {id, σx , σy , σz } to her qubit and sends it to Bob. Thus she can create one of four orthogonal states, which corresponds to 2 classical bits of information. • Bob can now measure the 2 qubits in the Bell basis and thereby learn which of the 4 operations Alice has used, hence what 2-bit information she wanted to transmit. So it is not really a paradox, as 2 qubits contain 2 bits of information; but when discovered it was quite surprising. Although it might look like we’ve found a way of superluminal communication, this is not possible: Bob cannot tell which operation Alice has performed on her half of the EPR pair by just measuring his half. He needs either Alice’s qubit, or the information about the operation Alice performed, which would have to be transmitted to him classically, i.e. at maximum with the speed of light. P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 1.3 3 Quantum Teleportation EPR pair •• We have the same setup: Alice Bob • •���������� ������ |ψ � ������ ��������� 2 classical bits |ψ� t � Alice and Bob have shared an EPR pair in the past. After receiving two classical bits, Bob can exactly reproduce Alice’s qubit state |ψ�. This seems paradox at first sight, because |ψ� can be in any of the continuous states and therefore it contains in some sense an infinite amount of information, that could not possibly be transmitted in only two classical bits. Explanation: It works exactly like in superdense coding, except that Alice measures her half of the EPR pair and submits the result classically to Bob via 2 classical bits. • Alice has a qubit |ψ � = α |0� + β |1� • Alice and Bob share 2 qubits in state √12 (|00� + |11�). We use this state instead of the usual EPR state, as the Algebra becomes a little bit easier that way. √1 2 (α |0� + β |1�) ⊗ (|00� + |11�) � � • Alice measures her qubits in the Bell basis √12 (|00� ± |11�) , √12 (|01� ± |10�) and gets 1 √ [(α |00� + α |11�) |0� + (α |00� − α |11�) |0� + (α |01� + α |10�) |1� + (α |01� − α |10�) |1� 2 2 + (β |10� + β |01�) |0� + (β |10� − β |01�) |0� + (β |11� + β |00�) |1� + (β |11� − β |00�) |1�] 1 √ [(|00� + |11�) (α |0� + β |1�) + (|00� − |11�) (α |0� − β |1�) = 2 2 + (|01� + |10�) (α |1� + β |0�) + (|01� − |10�) (α |1� − β |0�)] (8) • The product state is • When Bob receives the result of Alice’s measurement, he can apply the corresponding of the 4 Pauli matrices to revert this back into the state α |0� + β |1�. Note by the way, that the teleportation also doesn’t work faster than light: The two classical bits need time to be transmitted from Alice to Bob. 2 Interlude: Communication Complexity Alice x Bob y Alice and Bob want to compute f (x, y). How much communication between them does it require? √ classically: ∝ n If x, y are of length n =⇒ quantum bits: ∝ log n =⇒ ∃ situations where qubits are much better than classical bits. P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 3 4 Models of Quantum Computation • Quantum Turing Machine • Quantum Gate Array • Quantum Cellular Automata • Adiabatic Quantum Computer (see next lecture) • Linear Optics Quantum Computer (beam splitters, phase shifters, mirrors etc.; only a few years ago the devices got sophisticated enough to produce and count single photons efficiently) • Quantum Computation by Anyons (particles that live in two dimensions, e.g. surface of metals) • Modular Functors (Quantum Field Theory) • Measurements on Cluster States (two-dimensional grid; measure qubits one at a time in proper order; the computation should be quite easy, but the hard part is preparing such a cluster state: you have to switch the interaction between neighboring qubits on and off) 3.1 3.1.1 Quantum Turing Machine & Equivalency to Quantum Gate Array Classical Turing Machine Recall the properties of a classical Turing Machine (TM): • infinite tape (with a finite number of non-zero spots) • head at some position on tape • table which maps head state & tape symbol to head action head ··· 0 0 0 0 ··· head state tape symbol head state tape symbol direction a a b b .. . 0 1 0 1 .. . c e f a .. . 0 0 1 0 .. . L R stay stay .. . −→ P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 3.1.2 5 Classical Reversible Turing Machine In order to be reversible, the table has to have the same number of columns on both sides. head state tape symbol direction (from) head state tape symbol direction (to) a a a a a a b .. . 0 0 0 1 1 1 0 .. . L R L R L .. . c 0 L .. . .. . .. . −→ This kind of reversible TM can do any computation that a normal TM can do (proof: simulate a gate array). 3.1.3 Quantum Turing Machine TM is in (a subset of) superpostition of states: |head state� ⊗ |direction� ⊗ |tape position� ⊗ ∞ � i=−∞ |tape symbol at position i� (9) The process of reading the tape, changing the symbol on the tape and moving the head to another position is split into two separate operations that change the state of the TM in the following ways: • Movement transition: |to L� ⊗ |i� −→ |from R� ⊗ |i − 1� |to R� ⊗ |i� −→ |from L� ⊗ |i + 1� |stay� ⊗ |i� −→ |stay� ⊗ |i� (10) • Transition function (corresponding to table in previous TM’s)1 : |head state�⊗|”from” direction�⊗|i�⊗|symbol i� −→ |head state� �⊗|”to” direction� �⊗|i�⊗|symbol i� � (11) =⇒ unitary map U on the vector space Vhead state ⊗ Vdirection ⊗ Vsymbols 1 In this operation no head movement happens. This is taken care of separately by the movement transition; hence here the tape position i stays the same P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 6 How do we know when the TM is finished? There are two possibilities: 1. We have a special stopping state (HALT), which is perpendicular to all other states, so that no collapse of the superposition can occur by measuring projection on HALT state subspace); we measure after each time step to see if the head is in HALT state. 2. Once we compute the answer, we start counting, so the tape looks like |answer� ⊗ |i� −→ |answer� ⊗ |i + 1� � �� � � �� � k cells (12) rest of tape After some time, the probability that the answer is in the first part of the tape hopefully reaches 1. Theorem 3. A quantum gate array with O(n) qubits and O(n2 ) gates can simulate a quantum TM for n steps. Proof: We’re gonna use some registers symbol at i head state at i direction (|0� if head is not here) |0 . . . 0� symbol at i + 1 head state at i + 1 direction work qubits Between time t and t+1 both state and movement transition take place and can change the contents of the registers i and (if the head moves) the neighboring registers. time t time t + 1 i−1 i i−1 i i−1 i i+1 i+1 i+1 ← state transition ← movement transition The state transition is no problem, since only the registers corresponding to position i need to be changed, and the change only depends on the contents of these registers. In the movement transition only the head and direction registers are changed. The two possible head movements to the right and to the left correspond to the following operations: |head� |to R� � �� � position i |0� |0� � �� � position i−1 |0� |0� � �� � −→ |0� |0� |head� |from L� (13) position i+1 |head� |to L� −→ |head� |from R� � �� � position i |0� |0� (14) P. Shor – 18.435/2.111 Quantum Computation – Lecture 12 7 This can be achieved with a unitary transformation on all pairs of registers on positions 2k, 2k + 1, followed by a unitary transformation on all pairs on positions 2k − 1, 2k: to R U1 to R U2 from L The effect of either U operation on the different possible states of the head and direction registers can be seen in the following table. Marked with U1 and U2 is the above example. |head� |to L� ↓ |head� |to L� U2 → |0� |0� |0� |0� |head� |to R� |0� |0� ↓ |0� |0� |head� |from L� |head� |stay � ↓ |head� |stay � |0� |0� |head� |to L� ↓ |head� |from R� |0� |0� |0� |0� |0� |0� |0� |0� |0� |0� |0� |0� |0� |0� |head� |to R� ↓ |head� |to R� |head� |stay� ↓ |head� |stay� ← U1