Quantum Information and Computation

The Basic Quantum Protocols

Hao-Chung Cheng (鄭皓中)

haochung@[Link]

Department of Electrical Engineering

National Taiwan University

March 10, 2021

Outline
1. Motivation – One-Time Pad

2. Three Quantum Protocols

– Entanglement Distribution – Dense Coding – Quantum Teleportation

3. Optimality of The Protocols

4. Quantum Key Distribution

5. Concluding Remarks and References

Motivations
Prologue – A Secure Communication (1/2)
1. Bob randomly sends a green or red paper to Alice.
2. Alice sends ‘0’ by returning the paper with the same color;
sends ‘1’ by sending the paper with the opposite color.
3. Bob check the received paper to see whether the color was the same as before.

Can Eavesdropper learn anything from wiretapping Alice’s message?

• ‘0’: same color

• ‘1’: opposite color

50%

50%
Prologue – A Secure Communication (2/2)
• In 1926 Vernam proposed the first provably secure cryptographic protocol,
known as the one-time pad , or Vernam cipher.
• The key is represented by a random string of bits, which is used to lock and
unlock the confidential message.
• The message itself is another string of bits. Binary addition is used for ciphering.
0⊕0＝1⊕1=0; 0⊕1＝1⊕0＝1

Ciphertext: b⊕k=11101010
Source text: b=01101100 Deciphered text: b⊕k⊕k=01101100
Key: k=10000110 Key: k=10000110
Remarks on The One-Time Pad
• Classical communication is used and assumed to be noiseless.
• If the key is a random string then the transmitted ciphertext is a random string too.
→ No one intercepting the ciphertext has access to any meaningful information
except the length of the message (any message of this length is equally probable).
• Note that the key shouldn’t be reused; it has be random; that’s why “one-time”.
• The shared key forms an ensemble of pairs of classical bits described by a joint
probability 𝑝𝑝00 = 𝑝𝑝11 = 1/2 and 𝑝𝑝01 = 𝑝𝑝10 = 0.
→ Classically maximally correlated state, shared randomness, or denoted as [cc].
• Encoded bit string (nor the key) contains no information of the original messages
(Shannon, 1949). → It is the correlation between the source & key that does!
• Can we replace any of the source, channel, and key by its quantum counterpart?
• The protocol is secure only if the key distribution is secure and hidden from others.
Non-Local Resources
Communication
• What is communication? (We consider noiseless communication for now.)
→ Simply put, the state in system A ends up in system B.

🀅🀅 🀅🀅 🀅🀅 Communication 🀅🀅 🀅🀅 🀅🀅
System A System B
• Noiseless cbit channel: 0 ↦ 0; 1 ↦ 1.
Measure the state w.r.t. to { 0 , |1⟩} and send the post-measurement state.
We call this ability “1 cbit”, or represent it as [𝑐𝑐 → 𝑐𝑐].
• Noiseless qbit channel: 𝑥𝑥 𝐴𝐴 ↦ 𝑥𝑥 𝐵𝐵 for all basis states
This implies to 𝜓𝜓 𝐴𝐴 ↦ 𝜓𝜓 𝐵𝐵 for all 𝜓𝜓 𝐴𝐴 ∈ ℋ.
We call this ability “1 qubit”, or [𝑞𝑞 → 𝑞𝑞]. A qubit channel sends a “system”.
Non-Local Resources
• Quantum correlation (Entanglement):
“1 ebit”, or 𝑞𝑞𝑞𝑞 is an EPR pair 12 0 𝐴𝐴 0 𝐵𝐵 + 1 𝐴𝐴 1 𝐵𝐵 shared between the systems A & B.
• Non-local resources: If two spatially separated parties share it or if one party uses it to
communicate to another; e.g. 1 cbit, 1 qubit, 1 ebit.
• Resource inequality: this ≥ that
The resources enumerated in “this” can be used to do any task that can be
performed using “that” .
∃At least one protocol that uses the resource on the left to give resource on the right.
• For example, 1 qubit ≥ 1 cbit , or 𝑞𝑞 → 𝑞𝑞 ≥ 𝑐𝑐 → 𝑐𝑐 :
‒ Alice has a classical bit 𝑏𝑏 ∈ {0,1} and creates a qubit state vector 𝑏𝑏 𝐴𝐴 .
‒ She uses a qubit channel to transfer this to Bob. Can we send more
‒ Bob measures the received 𝑏𝑏 𝐵𝐵 w.r.t. { 0 , |1⟩} to readout 𝑏𝑏. cbits via 1 qubit?
Basis Resources Inequalities (1/2)
• A qubit can deliver a cbit: 1 qubit ≥ 1 cbit

• A 𝑑𝑑-dimensional state can never be used to perfectly send more than 𝑑𝑑 messages.
It is even impossible to communicate at an asymptotic rate higher than
the trivial one cbit per qubit sent (Holevo bound, 1973).
1 qubit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1

• Finite cbits cannot perfectly represent a qubit.

(Otherwise would violate the no-cloning or the no-perfect discrimination).

𝑁𝑁 cbits ≩ 1 qubit ∀𝑁𝑁 ≥ 1

Basis Resources Inequalities (2/2)
• Entanglement along cannot be used for communication (by no-signaling).

𝑁𝑁 ebits ≩ 1 cbit ∀𝑁𝑁 ≥ 1 𝑁𝑁 ebits ≩ 1 qubit ∀𝑁𝑁 ≥ 1

• Communication (bandwidth) & entanglement are assumed to be perfect but not free.
1 cbit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1 𝑀𝑀 cbits + 1 qubit ≩ 𝑁𝑁 qubits ∀𝑁𝑁 > 1, 𝑀𝑀 ≥ 1

1 ebit ≩ 𝑁𝑁 ebits ∀𝑁𝑁 > 1

• Classical communication cannot be used to generate entanglement. [§12.5, N&C]
(The rigorous proof would be given later in this semester.)

𝑁𝑁 cbit ≩ 1 ebit ∀𝑁𝑁 ≥ 1

Entanglement Distribution
Entanglement Distribution 1 qubit ≥ 1 ebit
1. Alice locally prepares an EPR pair on her systems 𝐴𝐴 and 𝐴𝐴𝐴.
‒ Hadamard gate 𝐻𝐻 creates superposition on 𝐴𝐴 (it is self-inverse, hence unitary).

‒ Controlled-NOT gate entangles systems 𝐴𝐴 and 𝐴𝐴𝐴.

2. Alice sends system 𝐴𝐴𝐴 to Bob:

(via 1 qubit channel)
Remarks on Entanglement Distribution
• Protocol: 𝐴𝐴 𝐻𝐻 ●

𝐴𝐴𝐴 ⨁ ebit
𝐵𝐵
• Can a qubit be used to generate more ebits? No!
• Experimental implementation
Quantum Dense Coding
Quantum Dense Coding 1 qubit + 1 ebit ≥ 2 cbits

• Recall that 1 qubit can perfectly communicate at most 1 cbit.

• In 1992, Bennett and Wiesner proposed a dense coding protocol to perfectly
communicate 2 cbits with 1 qubit and 1 ebit; later experimentally verified by
Zeilinger in 1995/1996.
• Recall the one-time pad: 1 cbit + [cc] ≥ 1 private cbit.
• In the quantum dense coding scenario:
‒ The secrete key (1 maximally correlated classical state) was replaced with 1 maximally
entangled state (1 ebit).
‒ The classical communication (1 cbit) was replaced with quantum communication (1 qubit).
• Encode cbits into qubits (with the assistance of ebits).
• Question: Is the quantum dense coding secure?
Protocol of Dense Coding
1. Alice shares a Bell state (EPR pair) Φ+ 𝐴𝐴𝐵𝐵 (say, prepared by a third party Charlie).
2. If Alice’s message is 𝑚𝑚 ∈ 0,1,2,3 (or 𝑖𝑖𝑖𝑖 ∈ {00,01,10,11}), she applies to her qubit:

3. Alice sends her part to Bob via 1 qubit channel.

4. Bob applies the Bell measurement Φ± , Ψ ± on both qubits to obtain 2 cbits.

𝐴𝐴 𝜎𝜎𝑚𝑚
Alice’s side
Bob’s side
ebit 𝑚𝑚 2 cbits
𝐵𝐵
Bell measurement
The Bell Measurement
• The four Bell states (the EPR states or the Bell basis) comprise an orthonormal basis
for ℂ2 ⊗ ℂ2 of two qubits.

• They characterize two classical bits:

• 𝑈𝑈 = C-NOT 𝐻𝐻 ⊗ 𝐼𝐼 changes the computational basis

{ 00 , 01 , 10 , |11⟩} to the Bell basis.
→ To measure w.r.t. the Bell basis, apply 𝑈𝑈 −1 and then
measure w.r.t. the computational basis.
Rotate the Bell basis back to the computational basis measurement = Bell measurement
Proof of Dense Coding
If Alice wants to send Alice applies
00
01
10
11

After Alice action and communication Bob’s end → C-NOT gate → 𝐻𝐻 gate

Bell states □
Remarks on Dense Coding
• We have seen 1 qubit + 1 ebit ≥ 2 cbits, but why not 1 qubit + 1 qubit ≥ 2 cbits?
The shared entanglement is independent of the messages that will be set!
(Hence the ebit is treated as a resource in practice.)
• One might think that 1 qubit can carry 2 cbits.
However, if Eve intercept the transmitted 1 qubit, she will learn nothing from it!
→ The dense coding protocol is secure (just like the one-time pad).
→ The information of 2 cbits is not hidden in the 1 qubit.
→ It is the correlation between the 2 systems (the four Bell states) that contain 2 cbits.
• It belongs to the research of “entanglement-assisted classical communication”.
• Question: Can we consume less 1 qubit & 1 ebit (asymptotic average cost)?
→ No! The dense coding protocol is optimal.
Quantum Teleportation
Quantum Teleportation 2 cbits + 1 ebit ≥ 1 qubit
• Suppose Alice wants to communicate an unknown qubit state |𝜓𝜓⟩ to Bob (i.e. a
quantum message), but is only able to send a classical bit strings.
Can she do it? (Encoding qubits into cbits)
classical
bit string 𝑥𝑥 Arbitrary preparation
|𝜓𝜓⟩ 𝜓𝜓 ?
procedure

• This is not possible because of the resource inequality 𝑁𝑁 cbits ≩ 1 qubit ∀𝑁𝑁 ≥ 1
• In 1993, Bennett et al. invented the quantum teleportation that transmits 1 qubit
(i.e. an arbitrary qubit state) to Bob with 2 cbits and 1 ebit.
The protocol was later experimentally verified in 1998.
Protocol of Teleportation
1. Alice shares a Bell state (EPR pair) Φ+ 𝐴𝐴𝐴𝐵𝐵 (say, prepared by a third party Charlie).
2. Alice applies the Bell measurement on her state 𝜓𝜓 𝐴𝐴 and system 𝐴𝐴𝐴.
3. Alice sends the 2-cbit outcome 𝑚𝑚 ∈ 0,1,2,3 to Bob.
4. Bob applies 𝜎𝜎𝑚𝑚 on his system B according to the received 𝑚𝑚, getting 𝜓𝜓 𝐵𝐵 .

𝐴𝐴

𝐴𝐴𝐴
Bell measurement

ebit
qubit
𝐵𝐵 𝜎𝜎𝑚𝑚
Proof of Teleportation (1/2)

Bell measurement
Proof of Teleportation (2/2)

• Alice performs measurements on her 2-qubits to get ‘00’, ‘01’, ‘10’, ‘11’ equally likely

Measurement outcome Post-measurement state ⇒ Once Alice received her bits,

00
tell Bob how to correct the state
01
10
11
□
Remarks on Teleportation
• Each Bell measurement outcome occurs with 25%. → Alice learn nothing of |𝜓𝜓⟩.
• The qubit information is teleported over any given distance in a way that is secure.
(though it does not teleport any physical object).
→ Eves learns nothing from the intercepted 2 cbits (so does Bob!).
• The system embodying |𝜓𝜓⟩ is not transferred from Alice to Bob.
There is no any physical objects that was teleported!
Only the “information” of the state’s identity is transferred.
• Quantum teleportation does not violate the no-cloning or no-signaling theorems.
• It belongs to the research of “entanglement-assisted quantum communication”.
• Question: Can we consume less than 2 cbits & 1 ebit (asymptotic average cost)?
→ No! The quantum teleportation protocol is optimal.
The Intuition Behind the Scenes
• Dense coding:
Local operations can transform one of the Bell states to others in the Bell basis.
Choose 𝜎𝜎𝑚𝑚 𝑚𝑚 as
Pauli matrices

• Teleportation:

XZ

The choice of the transform 𝜓𝜓 ↦ 𝜎𝜎𝑚𝑚 𝜓𝜓 depends

only on the measurement, not on the identity of |𝜓𝜓⟩
Optimality of The Protocols
Optimality of Entanglement Distribution
• 1 qubit cannot generate more ebits: 1 qubit ≩ 𝑁𝑁 ebits ∀𝑁𝑁 > 1
• Assuming it was possible, use the generated 𝑁𝑁 ebits for teleportation:
Assumed: 1 qubit ≥ 𝑁𝑁 ebits ∃𝑁𝑁 > 1 The math is valid if
𝑁𝑁 Teleportations: 2𝑁𝑁 cbits + 𝑁𝑁 ebits ≥ 𝑁𝑁 qubits the composition is
⇒ 2𝑁𝑁 cbits + 1 qubit ≥ 𝑁𝑁 qubits, 𝑁𝑁 > 1
Contradicts with: 𝑀𝑀 cbits + 1 qubit ≩ 𝑁𝑁 qubit ∀𝑁𝑁 > 1, 𝑀𝑀 ≥ 1 →←

𝐻𝐻 ●
𝑁𝑁 ebits
⨁
𝑁𝑁 qubits
𝜎𝜎𝑚𝑚
Optimality of Dense Coding (1/2)
ebits
• One cannot use less qubits and cbits: 𝛼𝛼 qubit + 𝛽𝛽 ebit ≩ 2 cbits ∀𝛼𝛼 < 1 or ∀𝛽𝛽 < 1
1. Assuming 𝛼𝛼 < 1, use the generated 2 cbits to supply the teleportation:
Assumed: 𝛼𝛼 qubit + 𝛽𝛽 ebit ≥ 2 cbits ∃𝛼𝛼 < 1
Teleportation: 2 cbits + 1 ebit ≥ 1 qubit
⇒ 𝛼𝛼 qubit + 1 + 𝛽𝛽 ebits ≥ 1 qubit, 𝛼𝛼 < 1
Contradicts with: 1 qubit ≩ 𝑁𝑁 qubits ∀𝑁𝑁 > 1 & 𝑁𝑁 ebits ≩ 1 qubit ∀𝑁𝑁 ≥ 1 →←

𝜎𝜎𝑚𝑚

2 cbits
𝛽𝛽 ebit
1 ebit 1 qubit
𝜎𝜎𝑚𝑚
Optimality of Dense Coding (2/2)
ebits
• One cannot use less qubits and cbits: 𝛼𝛼 qubit + 𝛽𝛽 ebit ≩ 2 cbits ∀𝛼𝛼 < 1 or ∀𝛽𝛽 < 1
1. Assuming 𝛼𝛼 = 1 and 𝛽𝛽 < 1, relate it to the entanglement distribution:
Assumed: 1 qubit + 𝛽𝛽 ebit ≥ 2 cbits ∃𝛽𝛽 < 1
Entanglement distribution: 𝛽𝛽 qubit ≥ 𝛽𝛽 ebit
⇒ (1 + 𝛽𝛽) qubit ≥ 2 cbits, 𝛽𝛽 < 1
Contradicts with: 1 qubit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1 →←

𝜎𝜎𝑚𝑚
Bob essentially
gets 2 qubits
𝛽𝛽 ebit 2 cbits
Optimality of Teleportation (1/2)
cbits and ebits
• One cannot use less qubits and cbits: 𝛼𝛼 cbits + 𝛽𝛽 ebit ≩ 1 qubit ∀𝛼𝛼 < 2 or ∀𝛽𝛽 < 1
1. Assuming 𝛼𝛼 < 2, use the generated 1 qubit to supply the dense coding:
Assumed: 𝛼𝛼 cbits + 𝛽𝛽 ebit ≥ 1 qubit ∃𝛼𝛼 < 2
Dense coding: 1 qubit + 1 ebit ≥ 2 cbits
⇒ 𝛼𝛼 cbits + 1 + 𝛽𝛽 ebit ≥ 2 cbits, 𝛼𝛼 < 2
Contradicts with: 1 cbit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1 & 𝑁𝑁 ebits ≩ 1 cbit ∀𝑁𝑁 ≥ 1 →←

𝜎𝜎𝑚𝑚

1 qubit
𝛽𝛽 ebit 𝜎𝜎𝑚𝑚

ebit 2 cbits
Optimality of Teleportation (2/2)
cbits and ebits
• One cannot use less qubits and cbits: 𝛼𝛼 cbits + 𝛽𝛽 ebit ≩ 1 qubit ∀𝛼𝛼 < 2 or ∀𝛽𝛽 < 1
2. Assuming 𝛽𝛽 < 1, use the generated 1 qubit to supply entanglement distribution:
Assumed: 𝛼𝛼 cbits + 𝛽𝛽 ebit ≥ 1 qubit ∃𝛽𝛽 < 1
Entanglement distribution: 1 qubit ≥ 1 ebit
⇒ 𝛼𝛼 cbits + 𝛽𝛽 ebit ≥ 1 ebit, 𝛽𝛽 < 1
1 N
Contradicts with: 1 cbit ≩ 𝑁𝑁 ebits ∀𝑁𝑁 ≥ 1 & 𝑁𝑁 ebits ≩ 1 ebit ∀𝑁𝑁 > 1 →←

𝐻𝐻 ●

1 qubit
𝛽𝛽 ebit 𝜎𝜎𝑚𝑚 ebit
Quantum Key Distribution
Key Distribution
• The one-time pad protocol is secure only if the key distribution is secure and hidden
from others, but how to do it in a secure way?
• Some public key crypto systems (such as RSA) relies on the computational hardness
of the integer factorization.
• Quantum key distribution (QKD) provides a method for Alice and Bob to generate a
shared secret key over public classical and quantum channels without the need to
meet or to use a trusted intermediary party.
Moreover, it is provably secure against eavesdropping.
‒ BB84 (C. Bennett and G. Brassard 1984) uses four qubit non-orthogonal states;
‒ B92 (C. Bennett 1992) uses only two non-orthogonal qubit states;
‒ E91 (A. Ekert 1991) uses an entangled pair of qubits and the Bell theorem.
‒ Etc. [Gisin et al., 2002] & [Pirandola, 2020]
Mutually Unbiased Bases
• Mutually unbiased bases (MUB): ℬ0 = 𝜓𝜓00 , 𝜓𝜓10 and ℬ1 = 𝜓𝜓01 , 𝜓𝜓11 .

𝜓𝜓00 = |0⟩
𝜓𝜓10 = |1⟩
1
𝜓𝜓01 = + = 0 − 1
2
1
𝜓𝜓11 = − = 2
0 − 1

• ℬ0 = 𝜓𝜓00 , 𝜓𝜓10 is the computational basis (or the Pauli 𝑍𝑍 eigenbasis);

ℬ1 = 𝜓𝜓01 , 𝜓𝜓11 is the conjugate basis (or the Pauli 𝑋𝑋 eigenbasis).

• These bases are called mutually unbiased if any state of one basis is measured in the
other basis, the outcomes are always equally likely.
Protocol of BB84 (1/3)
1. Alice generates two uniformly random binary strings:
𝒙𝒙 = 𝑥𝑥1 𝑥𝑥2 ⋯ 𝑥𝑥𝑚𝑚 (𝑥𝑥𝑖𝑖 represents the bit value of key she’s trying to send);
𝒚𝒚 = 𝑦𝑦1 𝑦𝑦2 ⋯ 𝑦𝑦𝑚𝑚 (𝑦𝑦𝑖𝑖 is her choice of the basis for that bit),
and she prepares the 𝑚𝑚 qubits in the states 𝜓𝜓𝑥𝑥1 𝑦𝑦1 𝜓𝜓𝑥𝑥2 𝑦𝑦2 ⋯ 𝜓𝜓𝑥𝑥𝑚𝑚𝑦𝑦𝑚𝑚 sending to Bob.

Using such a random choice of MUB for encoding each bit value is sometimes called conjugate coding.
Alice 沒有告訴Bob他⽤哪個basis，所以Bob得到的result是他猜的

2. Bob receives the 𝑚𝑚 qubits but they may no longer be in the states 𝜓𝜓𝑥𝑥𝑖𝑖𝑦𝑦𝑖𝑖 due to the
noise of the quantum channel or eavesdropping, but let’s assume they are perfect.
Bob chooses a uniformly random bit string 𝒚𝒚𝐴 = 𝑦𝑦1′ 𝑦𝑦2′ ⋯ 𝑦𝑦𝑚𝑚 ′
and measures the 𝑖𝑖 th
received qubit in basis ℬ𝑦𝑦𝑖𝑖′ to get a result 𝑥𝑥𝑖𝑖′ ; let 𝒙𝒙′ = 𝑥𝑥1′ 𝑥𝑥2′ ⋯ 𝑥𝑥𝑚𝑚
′
be Bob’s outcomes.
If 𝑦𝑦𝑖𝑖′ = 𝑦𝑦𝑖𝑖 , then 𝑥𝑥𝑖𝑖′ = 𝑥𝑥𝑖𝑖 . Otherwise, 𝑥𝑥𝑖𝑖′ is completely uncorrelated with 𝑥𝑥𝑖𝑖 .
Protocol of BB84 (2/3)
3. Alice and Bob publicly reveal and compare their choice of bases, i.e. 𝒚𝒚 and 𝒚𝒚′
(but they do NOT reveal the strings 𝒙𝒙 and 𝒙𝒙′ ).
They discard all bits 𝑥𝑥𝑖𝑖 and 𝑥𝑥𝑖𝑖′ for which 𝑦𝑦𝑖𝑖′ = 𝑦𝑦𝑖𝑖 leaving shorter strings of expected
length 𝑚𝑚/2. Call these strings 𝒙𝒙 � and 𝒙𝒙�′ .
Under our assumptions of no noise and no eavesdropping in the quantum channel,
� = 𝒙𝒙�′ (as the key).
we would have the perfectly correlated bits 𝒙𝒙

• The ‘quantum’ part has done. In reality there always be noise and eavesdropping in
the transmission. To address these issues, the BB84 protocol concludes with the
following Steps 4 & 5 from techniques in classical cryptography.
• The key distribution (Steps 1~3) can be done easily without quantum tricks.
→ What’s matter is the security of the protocol (i.e. Eavesdropper isn’t be recognized).
Protocol of BB84 (3/3)
4. (Information reconciliation) Alice and Bob publicly compare a random sample of
their strings (say half of them) to estimate the bit error rate (BER), the proportion of
bits in 𝒙𝒙�′ that are not equal to those in 𝒙𝒙
�, and discard all the announced bits.
Assume the remaining bits have the same proportion of errors as those checked.
They can correct these remaining errors (albeit at unknown positions) to obtain
two strings that agree in a high percentage of positions with high probability
Otherwise, abort
(at the expense of sacrificing some more bits) if the BER is not too large.
5. (Privacy amplification) From the estimated BER, Alice and Bob can estimate the
maximum amount of information that an eavesdropper is likely to have obtained
about the remaining bits.
They can replace their strings by even shorter strings about which the eavesdropper
has no knowledge of (with high probability).
An Example
Alice’s bit string 𝑥𝑥 1 0 1 1 0 1 0 1

Alice’s basis string 𝑦𝑦 1 0 0 1 0 1 1 0

X: |+>,|-> Z: |0>, |1> 𝑋𝑋 𝑍𝑍 𝑍𝑍 𝑋𝑋 𝑍𝑍 𝑋𝑋 𝑋𝑋 𝑍𝑍

Qubit states |−⟩ |0⟩ |1⟩ |−⟩ |0⟩ |−⟩ |+⟩ |1⟩

Bob’s basis string 𝑦𝑦 ′ 1 1 0 0 1 0 1 0

𝑋𝑋 𝑋𝑋 𝑍𝑍 𝑍𝑍 𝑋𝑋 𝑍𝑍 𝑋𝑋 𝑍𝑍

Bob’s resulting states |−⟩ |+⟩ |1⟩ |1⟩ |−⟩ |0⟩ |+⟩ |1⟩

Bob’s resulting bits 𝑥𝑥 ′ 1 0 1 1 1 0 0 1

Right basis? Y N Y N N N Y Y

Key string 𝑥𝑥� = 𝑥𝑥�′ 1 1 0 1

About Eavesdropper’s Attacks (1/2)
• Goal of the Eavesdropper: To learn the key without being recognized.
Note that if classical systems are measured, then any introduced disturbance can be
undone by Eve in theory; thus her presence cannot be detected.
• The Intercept-resend attack: Eve can intercept each transmitted qubit separately,
measure it in some chosen basis to acquire some information, and then send on the
post-measurement state to Bob.
• General coherent attack: Eve can introduce an auxiliary (possibly very large) probe
quantum system 𝐸𝐸 of her own and unitarily interact E with many of the passing
qubits. She measure 𝐸𝐸 to acquire information, which now can be joint information
about many qubits. Her measurement here can even be postponed until she
overhears Alice & Bob’s public discussions in Steps 2~5, and did what she likes.
About Eavesdropper’s Attack (2/2)
• Recall that standard classical strategy for eavesdropping on classical bits (reading
them and retaining a copy, and then sending them on perfectly intact) is not
available in the quantum protocol because of the no-cloning theorem and the use of
non-orthogonal states in the set of encoding states.
• In Step 5, the BER provides an upper bound on the amount of information that Eve
can have gained because non-orthogonal states cannot be perfectly distinguished
(i.e. information disturbance trade-off).
• Hence, the privacy amplification techniques from classical cryptography can be
shown to provide information-theoretic security against any possible eavesdropping
strategy obeying quantum mechanics.
[Gisin et al., 2002], [Mayers, 2001], [Shore-Preskill, 2000], [Pirandola, 2020]
An Intercept-Resend Attack
• Assume that the quantum channel is noiseless but Eve intercepts each passing qubit
and measures it in the so-called Breidbart basis:
𝛼𝛼0 = cos 𝜋𝜋8 0 + sin 𝜋𝜋8 |1⟩
𝛼𝛼1 = − sin 𝜋𝜋8 0 + cos 𝜋𝜋8 |1⟩

• Of course Eve can choose either ℬ0 or ℬ1 as before but the Breidbart basis lies
“midway” between the above two bases.
→ The eavesdropping will result in a disturbance amounting to BER = 25%.
� with probability cos 2 𝜋𝜋8 ≈ 0.85.
Eve will learn each bit of 𝒙𝒙
• If spotting any difference in Step 4, they just abort the protocol since they have
noticed Eve’s presence. Then they run the protocol again.
→ The probability of not noticing Eve will thus be exponentially small.
 𝛼𝛼0 = cos 𝜋𝜋8 0 + sin 𝜋𝜋8 1
Analysis for The BER (1/2) 𝛼𝛼1 = − sin 𝜋𝜋8 0 + cos 𝜋𝜋8 |1⟩

Alice sent Eve’s outcome Bob’s outcome

0 𝛼𝛼0 2= cos 2 𝜋𝜋8

𝛼𝛼0 sin2 𝜋𝜋8 Pr error = 2 cos 2 𝜋𝜋8 sin2 𝜋𝜋8
= 1/4
0 1 Pr Eve learns = 0 𝛼𝛼0 2
= cos 2 𝜋𝜋8
𝛼𝛼1 cos 2 𝜋𝜋8
sin2 𝜋𝜋8

1 𝛼𝛼1 2= sin2 𝜋𝜋8

𝛼𝛼0 cos 2 𝜋𝜋8 Pr error = 2 cos 2 𝜋𝜋8 sin2 𝜋𝜋8
= 1/4
1 0
Pr Eve learns = 1 𝛼𝛼1 2
𝛼𝛼1 sin2 𝜋𝜋8 = cos 2 𝜋𝜋8
cos 2 𝜋𝜋8
 𝛼𝛼0 = cos 𝜋𝜋8 0 + sin 𝜋𝜋8 1
Analysis for The BER (2/2) 𝛼𝛼1 = − sin 𝜋𝜋8 0 + cos 𝜋𝜋8 |1⟩

Alice sent Eve’s outcome Bob’s outcome

2= 1 2
+ 𝛼𝛼0 cos 𝜋𝜋8 + sin 𝜋𝜋8 1 2
2
2
cos 𝜋𝜋8 − sin 𝜋𝜋8 Pr error
𝛼𝛼0 = 12 cos 𝜋𝜋8 + sin 𝜋𝜋8
2
cos 𝜋𝜋8 − sin 𝜋𝜋8
2

= 1/4
+ −
2
Pr Eve learns = + 𝛼𝛼0
2
1
cos 𝜋𝜋8 − sin 𝜋𝜋8
2
𝛼𝛼1 1
cos 𝜋𝜋8 + sin 𝜋𝜋8
2 = 12 cos 𝜋𝜋8 + sin 𝜋𝜋8 = cos 2 𝜋𝜋8
2 2

2 1 2
1
cos 𝜋𝜋8 − sin 𝜋𝜋8 cos 𝜋𝜋8 + sin 𝜋𝜋8 Pr error
2 𝛼𝛼0 2
2 2
= 12 cos 𝜋𝜋8 + sin 𝜋𝜋8 cos 𝜋𝜋8 − sin 𝜋𝜋8
− + = 1/4
2
Pr Eve learns = − 𝛼𝛼1
1
cos 𝜋𝜋8 + sin 𝜋𝜋8
2 𝛼𝛼1 1
cos 𝜋𝜋8 − sin 𝜋𝜋8
2 2
2 2 = 12 cos 𝜋𝜋8 + sin 𝜋𝜋8 = cos 2 𝜋𝜋8
Concluding Remarks & References
Resource Inequalities
1 qubit ≥ 1 cbit 1 qubit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1

1 qubit ≥ 1 ebit 𝑁𝑁 cbits ≩ 1 qubit ∀𝑁𝑁 ≥ 1 𝑁𝑁 ebits ≩ 1 cbit ∀𝑁𝑁 ≥ 1

1 qubit ≩ 𝑁𝑁 ebits ∀𝑁𝑁 > 1 𝑁𝑁 ebits ≩ 1 qubit ∀𝑁𝑁 ≥ 1

1 cbit ≩ 𝑁𝑁 cbits ∀𝑁𝑁 > 1 𝑀𝑀 cbits + 1 qubit ≩ 𝑁𝑁 qubit ∀𝑁𝑁 > 1, 𝑀𝑀 ≥ 1

1 ebit ≩ 𝑁𝑁 ebits ∀𝑁𝑁 > 1 𝑁𝑁 cbit ≩ 1 ebit ∀𝑁𝑁 ≥ 1

1 qubit + 1 ebit ≥ 2 cbits 𝛼𝛼 qubit + 𝛽𝛽 ebit ≩ 2 cbits ∀𝛼𝛼 < 1 or ∀𝛽𝛽 < 1

2 cbits + 1 ebit ≥ 1 qubit 𝛼𝛼 cbits + 𝛽𝛽 ebit ≩ 1 qubit ∀𝛼𝛼 < 2 or ∀𝛽𝛽 < 1 etc…
Concluding Remarks
• One-time pad: public classical channel + [cc] = private classical communication
• Dense coding: public quantum channel + [qq] = private classical communication
• Teleportation: public classical channel + [qq] = private quantum communication
• Beyond qubits: Provided a 𝑑𝑑-dimensional maximally entangled state Φ𝑑𝑑 ≔ 1
𝑑𝑑
∑𝑖𝑖 |𝑖𝑖𝑖𝑖⟩.
‒ A total of 𝑑𝑑2 messages (2 log 𝑑𝑑 bits) can be sent via a d-dimensional quantum system and Φ𝑑𝑑 .
logd qbits + logd ebits >= 2logd cbits
‒ As for teleportation, 2 log 𝑑𝑑 bits + log 𝑑𝑑 ebits ≥ log 𝑑𝑑 ebits.
• If entanglement is free, then 1 qubit is worth exactly two cbits.
Indeed, 1 qubit + 1 ebit = 2 cobits (coherent communication by Harrow, 2004).
• The basic quantum protocols are building blocks for large information-processing systems.
• Entanglement distillation protocol [Werner, 2001] & [Plenio-Virmani, 2007], [Horodeck et al., 2009]
• Extensions for Quantum Shannon Theory and capacity region for qubit/ebit/cbit.
[Chapter 8, Wilde, 2017]
References (1/4)
• A. S. Holevo, “Bounds for the quantity of information transmitted by a quantum communication
channel,” Problems of Information Transmission, 9:177-183, 1973.
• C. H. Bennett, S. J. Wiesner, “Communication via one- and two-particle operators on Einstein–
Podolsky–Rosen states,” Physical Review Letters, 69:2881-2884, 1992.
• K. Mattle, H. Weinfurther, P. G. Kwiat, and A. Zeilinger,
“Dense coding in experimental quantum communication,” Physical Review Letters, 76:4656-4659,
1996.
• C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an
unknown quantum state via dual classical and Einstein–Podolsky–Rosen channels,” Physical Review
Letters, 70:1895-1899, 1993.
• D. Boschi, S. Branca, F. De Martini, L. Hardy, and S. Popescu,
“Experimental realization of teleporting an unknown pure quantum state via dual classical and
Einstein–Podolsky–Rosen channels,” Physical Review Letters, 80:1121-1125, 1998.
References (2/4)
• R. F. Werner, "All teleportation and dense coding schemes," Journal of Physics A, 34:7081, 2001.
• M. B. Plenio and S. Virmani, "An introduction to entanglement measures. Quantum Information
and Computation," 7(1), 2007.
• R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, "Quantum entanglement," Review of
Modern Physics, 81, 865, 2009.
• C. H. Bennett and G. Brassard. "Quantum cryptography: Public key distribution and coin tossing".
In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 175:8,
1984.
• D. Mayers, "Unconditional security in quantum cryptography," Journal of the ACM, 48:351, 2001.
• P. W. Shor and J. Preskill, "Simple proof of security of the BB84 quantum key distribution protocol,"
Physical Review Letters, 85:441–444, 2000.
• M. Wilde, Quantum information theory. Cambridge Press, 2017.
References (3/4)
• C. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing”,
Theoretical Computer Science. Theoretical Aspects of Quantum Cryptography – celebrating 30 years
of BB84, 560, Part 1: 7–11, 2014.
• V. Scarani, “The security of practical quantum key distribution,” Review of Modern Physics, 81(3):
1301–1350, 2009.
• C. H. Bennett, "Quantum cryptography using any two nonorthogonal states," Physical Review
Letters, 68, 3121, 1992.
• A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters, 67, 661, 1991.
• N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, "Quantum cryptography," Review of Modern
Physics, 74: 145-195, 2002.
• S. Pirandola et al., "Advances in quantum cryptography," Advances in Optics and Photonics,
12(4):1012–1236, 2020.
• A. Harrow, "Coherent Communication of Classical Messages," Physical Review Letters, 92, 097902,
2004.
References (4/4)
• C. H. Bennett, P. Hayden, D. Leung, P. W. Shor, A. Winter, “Remote preparation of quantum states,”
IEEE Transactions on Information Theory, 51:56–74, 2005.
• I. Devetak, A. Harrow, A. Winter. “A resource framework for quantum Shannon theory,” IEEE
Transactions on Information Theory, 54(10), 4587–4618, 2008.
• A. Harrow, P. Hayden, D. Leung, “Superdense coding of quantum states,” Physical Review Letters,
92:187901, 2004.
• I. Devetak, J. Yard, “Exact cost of redistributing multipartite quantum states,” Physical Review Letters
100:230501, 2008.
• Terhal B.M. (2016) Quantum Dense Coding. In: Kao MY. (eds) Encyclopedia of Algorithms.
Springer, New York, NY.
• Anshu A., Devabathini V.K., Jain R., Mukhopadhyay P. (2016) Teleportation of Quantum States. In:
Kao MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY.
• Renner R. (2016) Quantum Key Distribution. In: Kao MY. (eds) Encyclopedia of Algorithms.
Springer, New York, NY.