In quantum information theory, the foundation of quantum cryptography, the concepts of general/generalised measurements and quantum channels are rooted in the concept of quantum operation [Pre18, Sec. 3.2.4].

• A general measurement can be realised by entangling a system with a meter and performing a projective measurement on the meter.
• A quantum channel arises if we measure the meter but completely forget the measurement outcome.

While the time evolution of a closed quantum system can be expressed using a single unitary operator, the time evolution of an open quantum system is much less straightforward [HXK20], and this is where the theory of quantum operations come in.

Here, the axiomatic approach in [NC10, Sec. 8.2.4] to defining quantum operations is discussed, starting with Definition 1.

Justification of Axiom 1: In the absence of measurement, $\mathcal{E}$ by itself completely describes the quantum operation, and Axiom 1 reduces to the requirement that $\text{tr}\{\mathcal{E}(\rho)\}=1=\text{tr}(\rho)$; in this case, the quantum operation is trace-preserving.

• If $\mathcal{E}$ does not completely describe the operation, then there exists $\rho$ such that $\text{tr}\{\mathcal{E}(\rho)\}\lt1$, and $\mathcal{E}$ is so-called non-trace-preserving.
• Every physical quantum operation on $\rho$ satisfies the requirement that $\text{tr}\{\mathcal{E}(\rho)\}\leq1$.

Justification of Axiom 2: Let $\rho = \sum_ip_i\rho_i$, then

$\mathcal{E}(\rho) = \mathcal{E}(\sum_ip_i\rho_i) = \sum_i \Pr\{i,\mathcal{E}\}\dfrac{\mathcal{E}(\rho_i)}{\text{tr}\{\mathcal{E}(\rho_i)\}} = \Pr\{\mathcal{E}\} \sum_i \Pr\{i|\mathcal{E}\}\dfrac{\mathcal{E}(\rho_i)}{\text{tr}\{\mathcal{E}(\rho_i)\}},$

where $\text{tr}\{\mathcal{E}(\rho_i)\}$ is a normalisation factor.

By Bayes’ rule,

$\Pr\{i|\mathcal{E}\} = \color{red}{\Pr\{\mathcal{E}|i\}}\dfrac{p_i}{\Pr\{\mathcal{E}\}} = \color{red}{\text{tr}\{\mathcal{E}(\rho_i)\}}\dfrac{p_i}{\Pr\{\mathcal{E}\}}.$

Justification of Axiom 3: A quantum operation maps a density operator to a density operator — by itself or as part of a larger system — and density operators are always positive, so $\mathcal{E}$ must be a completely positive map.

Axioms 1-3 lead to the following important theorem.

In Theorem 1,

The freedom in the operator-sum representation is especially useful for studying quantum error correction.

Watch lectures on Kraus representations by Artur Ekert, inventor of the E91 QKD protocol:

Quantum key distribution (QKD) is a method for generating and distributing symmetric cryptographic keys with information-theoretic security based on quantum information theory [ETS18].

A QKD protocol establishes a secret key between two parties — let us call them 👩 Alice and 🧔 Bob as per tradition — connected by 1️⃣ an insecure quantum channel and 2️⃣ an authenticated classical channel [Gra21, Sec. 3.1].

• The established key can be however long as required so that it can serve as the key in a one-time pad.
• “Authenticated” does not imply “confidential” and does not necessarily require the use of cryptography. Alice and Bob can physically meet and verify each other’s identity.
• In practice, the authenticated classical channel can be established using 1️⃣ a pre-shared symmetric key, or 2️⃣ public-key cryptography [PAB+20, Sec. F].

A QKD protocol typically proceeds in two phases [Wol21, Ch. 4]:

1. the quantum transmission phase, in which 👩 Alice and 🧔 Bob send and/or measure quantum states;
2. the classical post-processing phase, where the bitstrings generated in the previous phase are converted into a pair of secret keys.

The security of QKD hinges on the principles of quantum mechanics, rather than the hardness of any computational problem, and hence does not get threatened by advances in computing technologies.

• During the quantum transmission phase, any adversary — let us call it 😈 Eve as per tradition — eavesdropping on the quantum channel inherently disturbs the channel and interrupts the key establishment process.
• Eve cannot make a copy of any transmitted state (that contributes to the key to be established) thanks to the no-cloning theorem.

The earliest QKD protocol is due to Bennett and Brassad [BB84] and is called BB84, named after the authors and the year it was proposed.

QKD leverages physical mechanisms, so unavoidably we need to discuss the physical mechanisms that underlie/enable BB84, which are based primarily on the polarisation of photons [Wol21, Sec. 1.3.1].

Polarisation

The polarisation of photons specifies the geometrical orientation of the oscillation of its electromagnetic field.

• Polarisation is linear if the field only oscillates in one direction.
• Polarisation is circular if the field rotates in a plane as the wave propagates.

We only consider linear polarisation here. For linear polarisation, we distinguish between two bases:

• rectilinear basis, which includes horizontal and vertical orientations; and
• diagonal basis, which is essentially the rectilinear basis rotated by $+45^\circ$; as shown in Fig. 1.

Consider the effect of polarisation filters depicted in Fig. 1:

• When a ↕ vertically polarised photon passes through a rectilinear polarisation filter, it is deflected to the right (➡).
• When a ↔ horizontally polarised photon passes through a rectilinear polarisation filter, it is deflected to the left (⬅).
• When a diagonally polarised photon passes through a rectilinear polarisation filter, it is equally likely to be deflected to the left and right.

Thus, measuring a diagonally polarised photon in the rectilinear basis, and similarly measuring a vertically/horizontally polarised photon in the diagonal basis, give a random result.

• We call the rectilinear and diagonal bases mutually conjugate (see Definition 1).

  Definition 1: Conjugate bases

  Two bases are mutually conjugate [BB84; FGG+97] or unbiased [Wol21, p. 9] if each vector of one basis has equal-length projections onto all vectors of the other basis.

• The Heisenberg uncertainty principle ensures that when making two sequential measurements using conjugate bases, the system is disturbed in such a way that the uncertainty of the measurement outcome is maximised [Woj22, p. 42].

With knowledge of polarisation in mind, let us now discuss the quantum transmission phase of BB84, which involves encoding of classical bits into quantum states, communication over a quantum channel, and decoding of quantum states into classical bits.

Quantum transmission phase

This phase of the protocol involving 👩 Alice and 🧔 Bob goes like this [Wol21, Sec. 1.3.2]:

1. 👩 Alice chooses a string of $N$ random classical bits: $X_1,\ldots,X_N$.
2. 👩 Alice chooses a random sequence of rectilinear (Z) bases and diagonal (X) bases; these are called the canonical bases [Dua14, p. 295].

3. 👩 Alice encodes her bitstring into a collection of photons with basis-dependent polarisation.

   In the rectilinear basis, 0 and 1 are encoded as → and ↑ respectively.

   In the diagonal basis, 0 and 1 are encoded as ↗ and ↖ respectively.

4. When 🧔 Bob receives the photons, he randomly (and independently of Alice) decides for each photon whether to measure/decode it in the rectilinear or diagonal basis to retrieve the classical bit.
5. At the end of this quantum transmission phase, 👩 Alice and 🧔 Bob each holds a classical bit string, denoted $\vec{X}=[X_1,\ldots,X_N]$ for Alice and $\vec{Y}=[Y_1,\ldots,Y_N]$ for Bob. $\vec{X}$ and $\vec{Y}$ form the raw key pair.

An illustration of the process above can be found Fig. 1.

Since the polarisation state of each photon is a discrete variable, BB84 is an example of a discrete-variable quantum key distribution (DV-QKD) scheme.

BB84 is also an example of a prepare-and-measure protocol, because of the preparation action of 👩 Alice and the measurement action of 🧔 Bob.

Classical post-processing phase

This phase of the protocol involves 👩 Alice and 🧔 Bob exchanging a sequence of classical information in the classical channel to transform their raw key pair into a shared secret key [Wol21, Sec. 1.3.3]:

1. This is the sifting step (steps 4-5 in Fig. 1):
   • 🧔 Bob publicly announces the bases he has chosen to measure the photons Alice has sent.
   • 👩 Alice compares Bob’s bases to the ones she used and confirms which bases Bob has chosen correctly.
   • 👩 Alice and 🧔 Bob discard all the bits for which the encoding and measurement bases are not the same.
2. This is the parameter estimation step:
   • 👩 Alice and 🧔 Bob want to compute an estimate of the quantum bit error rate (QBER) in the quantum channel, i.e., the fraction of bits where $\vec{X}$ and $\vec{Y}$ differ in the Z and X bases [Gra21, p. 38].
   • For this, 🧔 Bob reveals a random subset of his key bits.
   • In case of no eavesdropping, these bits should be the same as Alice’s bits and 👩 she confirms them.
   • If the QBER is too high, 👩 Alice and 🧔 Bob suspect eavesdropping and abort the protocol.
   • The bits that have been revealed during this step are discarded as their information is now public to eavesdroppers.
3. Computation of the final key if the error rate is not too high:
   • 👩 Alice and 🧔 Bob perform steps, which were later additions to the original BB84 [BBR88], to correct errors in their keys and increase the secrecy of their key.

   • The first step is error correction (also called information reconciliation), where they erase all errors in their bit strings. After this step, they hold identical strings.

     Direct vs reverse reconciliation [GG02; Djo19, p. 7; PAB+20, Sec. B]

     ▶ Direct reconciliation: 👩 Alice sends correction information and 🧔 Bob corrects his key elements to have the same values as Alice’s.

     • For example, 👩 Alice performs low-density parity check (LDPC) encoding and sends the parity bits to 🧔 Bob, who in turn performs LDPC decoding.
     • Error correction fails when quantum channel loss exceeds 50%.

     ◀ Reverse reconciliation: 🧔 Bob sends correction information and 👩 Alice corrects her key elements to have the same values as Bob’s.

     • For example, 🧔 Bob performs LDPC encoding and sends the parity bits to 👩 Alice, who in turn performs LDPC decoding.
     • Preferred option to direct reconciliation.
     • Provides a usable key when the mutual information of Alice ($A$) and Bob ($B$) exceeds the mutual information of Bob and Eve ($E$), i.e., $I(A;B)>I(B;E)$; the difference between these two terms gives the asymptotic secret key rate.
   • The second step is privacy amplification, which is a procedure that minimises Eve’s knowledge of the key.

Table 1 shows an example of an exchange between 👩 Alice and 🧔 Bob in the absence of eavesdropping.

For discussion of physical realisations of BB84, follow this knowledge base entry.

Performance and security evaluation

In terms of performance, a basic figure of merit of every QKD protocol is the secret key rate, i.e. the fraction of secure key bits produced per protocol round.

For security, follow this overview of QKD security.

Continuing from an overview of BB84, this entry discusses several ways in which BB84 can be realised.

Fig. 1 shows an experimental setup built by IBM [NC10, Box 12.7], where

• 🧔 Bob generates strong coherent states $|\alpha\rangle$ using a 1.3 μm (near infrared wavelength) diode laser and transmits the states to 👩 Alice 10 km away via an optical fibre.
• 👩 Alice attenuates the states to generate approximately a single photon, and subsequently polarises the photon to one of $|0\rangle$, $|1\rangle$, $|+\rangle$ and $|-\rangle$.
• 👩 Alice returns the photon to 🧔 Bob, who measures it using a polarisation analyser in a random basis (either rectilinear or diagonal).

For the setup in Fig. 1,

• The reason for making the photons traverse the optical fibre twice (from Bob to Alice then back to Bob) is to automatically compensate for asymmetry and fluctuations of the medium.
• The polarisation controller (“Pol Cont” in Fig. 1) is for correcting polarisation drifts in the quantum channel [Sud10, p. 111].
• The Faraday rotator (“Faraday Rot” in Fig. 1) effects polarisation through the Faraday (rotation) effect; watch demonstration on YouTube.
• The classical channel of wavelength 1.55 μm is carried over the same optical fibre. Multiplexing of the quantum and classical channels is achieved through the wavelength (division) multiplexers (“WM” in Fig. 1).
• The polarising beamsplitter (also called polarization beamsplitter, or “PBS” in Fig. 1) plays a crucial role, but let us first look at Thorlabs’ Quantum Cryptography Analogy Demonstration Kit (part number EDU-QCRY1), because the accompanying manual [Tho20] is rich with practical information rarely found elsewhere.

Fig. 2 shows a minimalist block diagram for EDU-QCRY1, while Fig. 3 shows a photo of a physical setup realising the block diagram.

Let us study the functions of the PBS in this context:

• For Alice to send a $|0\rangle$ to Bob, a half-wave plate (HWP, also called λ/2 plate, labelled as “Polarization Rotator” in Fig. 4) is physically rotated to 0°.

  To send a $|1\rangle$, the HWP is physically rotated by 45° to achieve a polarisation rotation of 90°.

  In general, for linearly polarised light, polarisation is rotated by a value twice as large as the rotation of the HWP.

• On Bob’s side, a horizontally polarised photon ($|0\rangle$) passes through the PBS, while a vertically polarised photon ($|1\rangle$) gets reflected, as shown:

  Thus, a single-photon detector is needed to detect each state.

• To support both the rectilinear basis (0° and 90°) and diagonal basis (-45° and 45°), the setup in Fig. 4 is extended to the setup in Fig. 6, where Alice’s polarisation rotator now support four angles in total ($|0\rangle$, $|1\rangle$, $|+\rangle$, $|-\rangle$), and Bob gets a polarisation rotator that supports two angles (one for each basis).

  Note Bob still needs only two photon detectors, one for each basis state of the selected basis.

• Eve can be emulated by simply 1️⃣ duplicating the setup for Bob (for intercepting Alice’s photons), and 2️⃣ duplicating the setup for Alice (for “replaying” measured states to Bob); as shown in Fig. 2.

In recent years, satellite-based experiments on BB84 and extensions of BB84 (e.g., decoy-state BB84) had been conducted [LCPP22].

Compared to free space, polarisation is harder to preserve over commercial optical fibres [GK05, Fig. 11.7]. An alternative approach to polarisation is using an interferometer, such as a Mach-Zehnder interferometer; see Fig. 7 and [HIP+21, Sec. 3.2].

References

Consider the circuit below, where a Hadamard gate is connected to qubit $q_0$ and a controlled-NOT (CNOT) gate is connected to $|q_0q_1\rangle$ after the Hadamard gate:

The Hadamard gate in Fig. 1 effects the transformations: $|0\rangle\to|+\rangle$ and $|1\rangle\to|-\rangle$.

The CNOT gate in Fig. 1 has its control qubit connected to the $q_0$ line, and its target qubit connected to the $q_1$ line.

The unitary matrix representing the CNOT gate is

$\text{CNOT} = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{bmatrix}.$

If the input to the CNOT gate is the state $|q_0q_1\rangle = a|00\rangle + b|01\rangle + c|10\rangle + d|11\rangle = \begin{bmatrix}a & b & c & d\end{bmatrix}^\top$, then the output is

$\text{CNOT}|q_0q_1\rangle = \begin{bmatrix}a & b & d & c\end{bmatrix}^\top = a|00\rangle + b|01\rangle + d|10\rangle + c|11\rangle.$

Thus, as an example, if the input is $|q_0q_1\rangle = |10\rangle$, then the Hadamard gate transforms it to $|-,0\rangle = \frac{1}{\sqrt{2}}(|00\rangle - |10\rangle)$, and the CNOT gate further transforms it to

$\text{CNOT}\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 0 & -1 & 0\end{bmatrix}^\top = \frac{1}{\sqrt{2}}\begin{bmatrix}1 & 0 & 0 & -1\end{bmatrix}^\top = \frac{1}{\sqrt{2}}(|00\rangle - |11\rangle).$

Table 1 is the truth table summarising the outputs corresponding to basis-state inputs.

The output states in Table 1 are called the Bell states or Einstein-Podolsky-Rosen (EPR) pairs [KLM07, p. 75; NC10, Sec. 1.3.6], and can be represented concisely as

$|\beta_{xy}\rangle = \frac{1}{\sqrt{2}}\left[|0,y\rangle + (-1)^x|1,\bar{y}\rangle \right].$

When the Bell states are used as an orthonormal basis, they are called the Bell basis [Wil17, pp. 91-93].

Consider the ket vector $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, where $\alpha$ and $\beta$ are complex-valued probability amplitudes, $|0\rangle$ and $|1\rangle$ are the computational bases.

We can express $\alpha$ and $\beta$ in the exponential form [Wil17, (3.6)]:

$\alpha = r_0e^{j\varphi_0}, \qquad \beta = r_1e^{j\varphi_1},$

we can rewrite $|\psi\rangle$ as

$|\psi\rangle = e^{j\varphi_0}\underbrace{\left\{\cos\left(\frac{\theta}{2}\right)|0\rangle + e^{j(\varphi_1-\varphi_0)}\sin\left(\frac{\theta}{2}\right)|1\rangle\right\}}_{\text{Portion that matters}},$

where $\theta$ is related to $r_0$ and $r_1$ by:

$r_0 \triangleq \cos\left(\frac{\theta}{2}\right), \qquad r_1 \triangleq \sin\left(\frac{\theta}{2}\right).$

Thus, given $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, we can rewrite it in the physically equivalent form:

$|\psi\rangle = \cos\left(\frac{\theta}{2}\right)|0\rangle + e^{j\varphi}\sin\left(\frac{\theta}{2}\right)|1\rangle,$

where $\varphi\triangleq\varphi_1-\varphi_0$, $0\leq\varphi\lt2\pi$, $0\leq\theta\leq\pi$. Note:

$\left|\cos\left(\frac{\theta}{2}\right)\right|^2 + \left|e^{j\varphi}\right|^2\left|\sin\left(\frac{\theta}{2}\right)\right|^2 = 1.$

💡 Above, $\theta/2$ is used instead of $\theta$ because for visualisation using a Bloch sphere (more on this later), as $\theta$ ranges from 0 to $\pi$, the values of $\cos$ and $\sin$ are confined within $[0,1]$ to ensure the qubit representation is unique [Wil17, p. 57].

So what is a Bloch sphere?

Named after physicist Felix Bloch, a Bloch sphere is a unit-radius sphere for visualising a qubit relative to the computational basis states.

As shown in Fig. 1,

• The north and south poles are typically chosen to represent $|0\rangle$ and $|1\rangle$ respectively, or the spin-up and spin-down states of an electron respectively.
• Orthogonal states like $|0\rangle$ and $|1\rangle$ do not appear to be geometrically orthogonal in a Bloch sphere.
• The angles $\theta$ and $\varphi$ represent the polar and azimuthal angles respectively [Le 06, Sec. 3.1].
• The $x$, $y$ and $z$ coordinates of a ket vector on the Bloch sphere are not as meaningful.
• Every point on the equator represents an equally weighted superposition of $|0\rangle$ and $|1\rangle$.

As explained in Fig. 2, a sphere provides the necessary number of degrees of freedom to represent a ket vector.

The equator of a Bloch sphere enables the representation of complementary bases. For example, in Fig. 3,

• $|x\rangle$ ($\theta=0$, $\varphi$ undetermined) and $|y\rangle$ ($\theta=\pi$, $\varphi$ undetermined) represent the basis states for linear polarisations along two perpendicular axes [Le 06, p. 12].
• $|R\rangle$ ($\theta=\pi/2$, $\varphi=\pi/2$) and $|L\rangle$ ($\theta=\pi/2$, $\varphi=3\pi/2$) represent the basis states for circular polarisation, [Le 06, p. 33].
• $|x\rangle,|y\rangle$ and $|R\rangle,|L\rangle$ are complementary bases, which play a crucial role in quantum key distribution.

Consider a multi-qubit system consisting of two qubits. There are four possible final states: $|00\rangle, |01\rangle, |10\rangle, |11\rangle$; and it makes sense to express the quantum state of this two-qubit system as the linear combination:

$|a\rangle = a_{00}|00\rangle + a_{01}|01\rangle + a_{10}|10\rangle + a_{11}|11\rangle,$

where the normalisation rule still applies:

$|a_{00}|^2 + |a_{01}|^2 + |a_{10}|^2 + |a_{11}|^2 = 1.$

An alternative representation of $|00\rangle,\ldots,|11\rangle$ is

$|0\rangle_2, \quad |1\rangle_2, \quad |2\rangle_2, \quad |3\rangle_2,$

where the subscript indicates the order of the system.

Some authors call the set $\{|00\rangle, |01\rangle, |10\rangle, |11\rangle\}$, and equivalently $\{|0\rangle_2, |1\rangle_2, |2\rangle_2, |3\rangle_2\}$, the tensor base [Des09, p. 316].

Watch Microsoft Research’s presentation on “Quantum Computing for Computer Scientists”:

In the vector representation, given two separated qubits:

$|a\rangle = \begin{bmatrix}a_0\\a_1\end{bmatrix}, \qquad |b\rangle = \begin{bmatrix}b_0\\b_1\end{bmatrix},$

their collective state can be expressed using the Kronecker product (also called the matrix direct product and tensor product):

$|b\rangle\otimes|a\rangle \equiv \begin{bmatrix} b_0\begin{bmatrix}a_0\\a_1\end{bmatrix} \\ b_1\begin{bmatrix}a_0\\a_1\end{bmatrix}\end{bmatrix} = \begin{bmatrix}b_0a_0 \\ b_0a_1 \\ b_1a_0 \\ b_1a_1\end{bmatrix}.$

Multiple shorthands exist for $|b\rangle\otimes|a\rangle$: 1️⃣ $|b\rangle|a\rangle$, 2️⃣ $|b,a\rangle$, 3️⃣ $|ba\rangle$ [Mer07, p. 6; NC10, Sec. 2.1.7]; we have used the third shorthand earlier.

In general, we can compose the Hilbert space of a multi-qubit system using the vector space direct product (also called tensor direct product) of lower-dimensional Hilbert spaces [NC10, Sec. 2.1.7]:

• The vector space direct product is a specialisation of the direct product, and should be differentiated from Kronecker product because the latter operates on vectors and matrices.
• Suppose $V$ and $W$ are Hilbert spaces of dimensions $m$ and $n$ respectively, then $V \otimes W$ (read “$V$ tensor $W$”) is an $mn$-dimensional Hilbert space.
• Suppose $|i\rangle$ and $|j\rangle$ are othonormal bases for $V$ and $W$ respectively, then $|i\rangle\otimes|j\rangle$ is a basis for $V \otimes W$.
• Thus the elements of $V \otimes W$ are linear combinations of the tensor products of the orthonormal bases for $V$ and $W$. For example, suppose $V$ is a two-dimensional Hilbert space with basis vectors $|0\rangle$ and $|1\rangle$, then every element of $V \otimes V$ is a linear combination of $|0\rangle\otimes|0\rangle$, $|0\rangle\otimes|1\rangle$, $|1\rangle\otimes|0\rangle$ and $|1\rangle\otimes|1\rangle$.

• Suppose $|v\rangle\in V$ and $\mathbf{A}$ is a linear operator on $V$. Similarly, suppose $|w\rangle\in W$ and $\mathbf{B}$ is a linear operator on $W$. Then we can define the composite linear operator $\mathbf{A}\otimes\mathbf{B}$ on $V \otimes W$ by:

  $(\mathbf{A}\otimes\mathbf{B})(|v\rangle\otimes|w\rangle) \equiv \mathbf{A}|v\rangle\otimes\mathbf{B}|w\rangle.$

  The above implies

  $(\mathbf{A}\otimes\mathbf{B})\left(\sum_i a_i|v\rangle_i\otimes|w\rangle_i\right) \equiv \sum_ia_i\mathbf{A}|v\rangle \otimes \mathbf{B}|w\rangle.$

  Some authors write $\mathbf{A}\tilde{\otimes}\mathbf{B}$ to differentiate $\tilde{\otimes}$ (representing a Kronecker product) from $\otimes$ (representing a direct product) [Zyg18, p. 16].

• Inner product in $V \otimes W$ is defined as

  $\left\langle \sum_ia_i|v\rangle_i\otimes|w\rangle_i \Bigg| \sum_jb_j|v'\rangle_j\otimes|w'\rangle_j \right\rangle \equiv \sum_{i,j}a_i^\ast b_j\langle v_i|v'_j \rangle\langle w_i|w'_j \rangle.$

Classical-quantum state

In quantum cryptography, we often encounter states that are partially classical and partially quantum.

A classical state (c-state for short) is a state defined by a density matrix $\rho_X$ that is diagonal in the standard basis of the $d$-dimensional state space of $X$, i.e., $\rho_X$ has the form:

$\rho_X = p_0|0\rangle\langle0| + p_1|1\rangle\langle1| + \cdots + p_{d-1}|d-1\rangle\langle d-1|,$

where $\sum_{i=0}^{d-1}p_i=1$.

Suppose we prepare the following states for Alice and Bob: with probability 1/2, we prepare $|0\rangle\langle0|_X\otimes\rho_0^Q$ and with probability 1/2, we prepare $|1\rangle\langle1|_X\otimes\rho_1^Q$. Then, the joint state is the so-called classical-quantum state (cq-state for short):

$\rho_{XQ} = \dfrac{1}{2}\sum_{x\in\{0,1\}}|x\rangle\langle x|_X\otimes\rho_x^Q.$

In quantum-cryptographic convention,

• $x$ typically denotes some (partially secret) classical string that Alice creates during a quantum protocol,
• $X$ denotes a classical register (in fact, the symbols $X,Y,Z$ are reserved for classical registers),
• $Q$ denotes a quantum register, and
• $\rho_x^Q$ denotes some quantum information that an adversary may have gathered during the protocol, and which may be correlated with the string $x$.

Formally,

The following introduces Shannon entropy before von Neumann entropy.

Shannon entropy

The Shannon entropy of a random variable, say $X$, measures the uncertainty of $X$.

Intuition:

• Minimum entropy occurs when $X$ takes on a specific value at probability 1. Let us say entropy is 0 in this case.
• Maximum entropy occurs when $X$ takes on one of $2^r$ different values at equal probability. Let us say entropy is $r$ bits in this case, because we need $r$ bits to represent all possible outcomes in binary.

The following definition of entropy, denoted by $H(X)$, measured in number of bits, can reflect the two extreme cases above [MC12, Definition 5.4]:

where $p_i$ denotes the probability of $X$ taking on the $i$th value.

⚠ Note: 1️⃣ $0\log_20\triangleq0$; 2️⃣ number of bits is discrete in practice but as a metric of comparison, we need entropy to be a continuous-valued metric.

If $X$ has $s$ possible values, and $Y$ has $t$, the joint entropy of $X$ and $Y$ is defined as [MC12, Definition 6.2]:

The conditional entropy of $X$ given $Y$ is defined as [MC12, (6.53)]:

$H(X|Y) \triangleq -\sum_{i=1}^s\sum_{j=1}^t \Pr_{X,Y}(x_i,y_j) \log_2 \Pr_{X|Y}(x_i|y_j).$

The chain rule for entropy states [MC12, p. 151; Gra21, (2.48)]:

or more generally,

Von Neumann entropy

The Shannon entropy measures the uncertainty associated with a classical probability distribution.

Quantum states are described in a similar fashion, with density operators replacing probability distributions.

The von Neumann entropy of a quantum state, $\rho$, is defined as [NC10, Sec. 11.3]:

$S(\rho) \triangleq -\text{tr}(\rho\log_2\rho),$

where $\log_2\rho$ denotes the base-2 logarithm of $\rho$ and not the element-wise application of base-2 logarithm to $\rho$.

Watch an introduction to the matrix logarithm on YouTube:

If $\lambda_i$ are the eigenvalues of $\rho$, then

A square matrix, $\mathbf{A}$, is idempotent if it is equal to its square, i.e., $\mathbf{A}^2=\mathbf{A}$ [Ber18, Definition 4.1.1].

Notable properties:

• Every idempotent matrix is necessarily a projector [Mey00, (5.9.13)].
• $\mathbf{A}$ is idempotent $\implies \text{rank}(\mathbf{A})=\text{tr}(\mathbf{A})$ [Ber18, Proposition 8.1.7].
• $\mathbf{A}$ is idempotent $\iff$ eigenvalues of $\mathbf{A}$ are either 0 or 1 [Loc08].

Let $V$ and $W$ be vector spaces. The mapping $T:V\to W$ is called a linear transformation if and only if

$T(c\vec{u}+\vec{v}) = cT(\vec{u}) + T(\vec{v}),$

for every choice of $\vec{u},\vec{v}\in V$ and scalar $c\in\mathbb{R}$.

When $V=W$, $T$ is called a linear operator [DG09, p. 202].

Mathematical programming (theory-based optimisation methods as opposed to heuristics) works best with differentiable cost/loss functions.

Mathematical programming also works with continuous loss functions [Byr15].

Differentiability implies continuity but the converse is not true, so continuity is a weaker condition than differentiability. For example, piecewise continuous functions are not differentiable at all points.

Lipschitzness is a particular form of continuity. Strictly speaking, Lipschitzness is a form of uniform continuity:

It follows from the definition above that if the derivative of $f$ is everywhere bounded in absolute value by $\rho$, then $f$ is $\rho$-Lipschitz.

The following introduces classical mutual information before quantum mutual information.

Classical mutual information

Consider the channel model of a transmission system in Fig. 1.

Since the input takes a certain value at a certain probability, the input is a discrete random variable, which we denote by $X$.

• For the same reason, the output is also a discrete random variable, which we denote by $Y$.
• Watch Khan Academy’s video on random variables if you need a refresher.

The posterior probability helps us determine the amount of information that can be inferred about the input when the output takes a certain value.

The information gain or uncertainty loss about input $x_i$ upon receiving output $y_j$ is the mutual information of $x_i$ and $y_j$, denoted by $I(x_i;y_j)$ [MC12, pp. 126-127].

• $I(x_i;y_j)$ is thus the uncertainty in $x_i$ before receiving $y_j$ minus the uncertainty in $x_i$ after receiving $y_j$.
• The uncertainty in $x_i$ before receiving $y_j$, measured in number of bits, is $\log_2\left(\frac{1}{\Pr_X\{x_i\}}\right)$.
• The uncertainty in $x_i$ after receiving $y_j$, measured in number of bits, is $\log_2\left(\frac{1}{\Pr_{X|Y}\{x_i|y_j\}}\right)$.

• Thus,

  $I(x_i;y_j) \triangleq \log_2\left(\frac{1}{\Pr_X\{x_i\}}\right) - \log_2\left(\frac{1}{\Pr_{X|Y}\{x_i|y_j\}}\right) = \log_2\left(\frac{\Pr_{X|Y}\{x_i|y_j\}}{\Pr_X\{x_i\}}\right).$

• By Bayes’ Theorem, $\Pr_{X|Y}\{x_i|y_j\} = \Pr_{Y|X}\{y_j|x_i\}\Pr_X\{x_i\}/\Pr_Y\{y_j\}$, so

  $I(x_i;y_j) = \log_2\left(\frac{\Pr_{X|Y}\{x_i|y_j\}}{\Pr_X\{x_i\}}\right) = \log_2\left(\frac{\Pr_{Y|X}\{y_j|x_i\}}{\Pr_Y\{y_j\}}\right) = I(y_j;x_i),$

  i.e., $x_i$ provides as much information about $y_j$ as $y_j$ does about $x_i$.

Extending the result above from $x_i$ to $X$ and from $y_j$ to $Y$, we define the system/average mutual information of $X$ and $Y$, denoted by $I(X;Y)$, as the information gain or uncertainty loss about random variable $X$ by observing random variable $Y$ [MC12, Definition 6.7]:

It is trivial to show that 1️⃣ $I(X;Y)=I(Y;X)$, 2️⃣ $I(X;Y)\geq0$, 3️⃣ $I(X;Y)=0$ iff $X$ and $Y$ are independent.

Omitting the derivation in [MC12, p. 129],

where $H(X)$ denotes the Shannon entropy of $X$.

Fig. 1 depicts the relation between mutual information and different entropies.

Quantum mutual information

Quantum mutual information is mutual information where the entropy is von Neumann entropy instead of Shannon entropy.

The positive operator-valued measure (POVM) is a mathematical formalism/tool representing a measurement operation [NC10, Sec. 2.2.6; WN17, Sec. 1.5.1] that satisfies Postulate 3.

Suppose a measurement described by measurement operators $\mathbf{M}_m$, where $m$ takes value from a finite set, is performed on a quantum system in the state $|\psi\rangle$, then the probability of outcome $m$ is given by

$\Pr\{m|\psi\} = \langle\psi|\mathbf{M}_m^\dagger\mathbf{M}_m|\psi\rangle = \text{tr}(\mathbf{M}_m^\dagger\mathbf{M}_m|\psi\rangle\langle\psi|).$

Suppose we define

$\mathbf{E}_m \triangleq \mathbf{M}_m^\dagger\mathbf{M}_m,$

then $\mathbf{E}_m$ satisfies 1️⃣ the completeness relation $\sum_m\mathbf{E}_m=\mathbf{I}$ and 2️⃣ $\Pr\{m|\psi\} = \langle\psi|\mathbf{E}_m|\psi\rangle = \text{tr}(\mathbf{E}_m|\psi\rangle\langle\psi|) \geq 0 \implies \mathbf{E}_m$ is positive-semidefinite.

• The general equality $\Pr\{m\} = \text{tr}(\mathbf{E}_m\rho)$ for some density matrix $\rho$ is known as the POVM version of the Born rule.
• The operators $\mathbf{E}_m$ are called the POVM elements associated with the measurement.
• The complete set $\{\mathbf{E}_m\}$ is known as a POVM.

When the POVM elements are projectors, such as in the preceding example, the POVM is called a projection-valued measure (PVM) [Hay17, p. 7].

Watch edX Lecture 1.6 “Generalized measurements” of Quantum Cryptography by CaltechDelftX QuCryptox.

For Hermitian matrix $\mathbf{A}$, the following statements are equivalent, and any one can serve as the definition of the positive definiteness of $\mathbf{A}$ [Mey00, Sec. 7.6; Woe16, Sec. 7.4]:

• $\vec{x}^\ast\mathbf{A}\vec{x}>0$, for all $\vec{x}\neq\vec{0}$. Note $\vec{x}^\ast\mathbf{A}\vec{x}$ is called a quadratic form.

  In Dirac notation, $\langle x|\mathbf{A}|x\rangle\gt0$, for all $|x\rangle\neq\vec{0}$. Note $|0\rangle\color{red}{\neq}\vec{0}$.

• The eigenvalues of $\mathbf{A}$ are all positive.
• $\mathbf{A}$ can be put in the form $\mathbf{A}=\mathbf{B}^\ast\mathbf{B}$ or $\mathbf{A}=\mathbf{B}\mathbf{B}^\ast$, where $\mathbf{B}$ is a nonsingular matrix.

Similarly, the following statements are equivalent, and any one can serve as the definition of the positive semidefiniteness of $\mathbf{A}$:

• $\vec{x}^\ast\mathbf{A}\vec{x}\geq0$, for all $\vec{x}\neq\vec{0}$.

  In Dirac notation, $\langle x|\mathbf{A}|x\rangle\geq0$, for all $|x\rangle\neq\vec{0}$.

• The eigenvalues of $\mathbf{A}$ are all nonnegative.

The discussion here follows from the discussion of the positive operator-valued measure (POVM).

The POVM cannot be used to determine the post-measurement state because the post-measurement state may not be pure [WN17, p. 13]. Instead, a Kraus operator representation of the POVM, known as projective measurement, is necessary to specify the post-measurement state.

Projective measurements are repeatable, and the outcome observed as a result of projective measurement is deterministic [MM12, Sec. 2.7], as explained below.

Projective measurements are often discussed in terms of an observable, which is defined as a Hermitian operator acting on the state space of a system.

Every observable $\mathbf{M}$ has a spectral decomposition [Mey00, p. 517]:

where $\lambda_i$ are the eigenvalues of $\mathbf{M}$, and $\mathbf{M}_i$ are so-called spectral/orthogonal projectors onto the null space of $(\mathbf{M}-\lambda_i\mathbf{I})$. More precisely, 1️⃣ $\mathbf{M}_i$ are Hermitian and idempotent, 2️⃣ $\sum_i\mathbf{M}_i=\mathbf{I}$, and 3️⃣ $\mathbf{M}_i$ are mutually orthogonal.

Clearly, $\mathbf{M}_i$ are valid POVM elements.

A (non-unique) Kraus operator representation or Kraus decomposition of $\mathbf{M}$ is defined as [WN17, Definition 1.5.2]:

where $\mathbf{A}_i^\dagger\mathbf{A}_i = \mathbf{M}_i$.

• If we define $\mathbf{A}_i\triangleq\mathbf{M}_i$, then $\mathbf{A}_i^\dagger\mathbf{A}_i = \mathbf{M}_i^\dagger\mathbf{M}_i = \mathbf{M}_i^2 = \mathbf{M}_i$.
• If we define $\mathbf{A}_i\triangleq\mathbf{U}\sqrt{\mathbf{M}_i}$, where $\mathbf{U}$ is any unitary matrix, then $\mathbf{A}_i^\dagger\mathbf{A}_i = \sqrt{\mathbf{M}_i}^\dagger\mathbf{U}^\dagger\mathbf{U}\sqrt{\mathbf{M}_i} = \mathbf{M}_i$.
• Thus, there is no unique Kraus representation/decomposition.

With Kraus operators, we can now define projective measurement:

Since the default Kraus operators are the same as the orthogonal projectors, most authors skip discussion of Kraus operators altogether 🤷‍♂️.

Measuring the observable $\mathbf{M}$ is equivalent to performing a projective measurement with respect to the decomposition $\mathbf{I} = \sum_i\mathbf{M}_i$, where the measurement outcome $i$ corresponds to eigenvalue $\lambda_i$.

In Example 2, the observation that the projective measurement preserves the quantum state is not a coincidence. In fact, building on Definition 1, applying measurement $\mathbf{A}_i$ to $|\psi'\rangle$, i.e., applying $\mathbf{A}_i$ to $|\psi\rangle$ twice gives us [MM12, p. 153]:

$\begin{split} |\psi''\rangle = \dfrac{\mathbf{A}_i|\psi'\rangle}{\sqrt{\langle\psi'|\mathbf{A}_i|\psi'\rangle}} = \dfrac{\mathbf{A}_i|\psi\rangle}{\sqrt{\langle\psi'|\mathbf{A}_i|\psi'\rangle\langle\psi|\mathbf{A}_i|\psi\rangle}} = \dfrac{\mathbf{A}_i|\psi\rangle}{\sqrt{\frac{\langle\psi|\mathbf{A}^\dagger_i}{\sqrt{p_i}}\mathbf{A}_i\frac{\mathbf{A}_i|\psi\rangle}{\sqrt{p_i}}p_i}} = |\psi'\rangle, \end{split}$

where $p_i\triangleq\langle\psi|\mathbf{A}_i|\psi\rangle$.

As defined in Practical 1 of COMP 5074, a qubit is a quantum state with two possible outcomes. Mathematically, a qubit is a two-dimensional Hilbert space.

A pure state is the quantum state of a qubit that we can precisely define at any point in time [Qis21, Sec. 1].

• For example, a qubit, say $|q\rangle$, that started out as $|0\rangle$ becomes $|+\rangle$ when it passes through a Hadamard gate.
• When we measure $|q\rangle$ in the computational basis (Z-basis), we get $|0\rangle$ at a probability of 0.5, or $|1\rangle$ at the same probability.
• Regardless of our measurement, in the ideal condition, we can say with absolute certainty that $|q\rangle$ has quantum state $|+\rangle$, and $|q\rangle$ is an example of a pure state.

In non-ideal conditions, a qubit can assume a certain quantum state at a certain probability, and other quantum states at other probabilities, regardless of measurements.

• For example, consider the two-qubit entangled state in Fig. 1:

  $|\psi_{AB}\rangle = \frac{1}{\sqrt{2}}(|0_A0_B\rangle + |1_A1_B\rangle),$

  where the subscripts $A$ and $B$ label the qubits associated with registers $q_1$ and $q_0$ respectively.

• Since the qubits of $q_1$ and $q_0$ are entangled, measuring a $|0_A\rangle$ in $q_1$ causes $|0_B\rangle$ to be measured in $q_0$. Similarly, measuring a $|1_A\rangle$ in $q_1$ causes $|1_B\rangle$ to be measured in $q_0$.
• Equivalently, the qubit of $q_0$, namely $\psi_B$, assumes values $|0_B\rangle$ and $|1_B\rangle$ at equal probability.
• However, this is NOT to say $\psi_B$ is a superposition of $|0_B\rangle$ and $|1_B\rangle$, i.e., we CANNOT express $\psi_B$ as $\frac{1}{\sqrt{2}}(|0_B\rangle+|1_B\rangle)$.
• $\psi_B$ is a mixture or ensemble of the states $|0_B\rangle$ and $|1_B\rangle$ [KLM07, Sec. 3.5].
• $\psi_B$ is an example of a mixed state, i.e., a statistical ensemble of quantum states [Qis21, Sec. 2].

A direct but rather clunky representation of a mixed state is the set of pairs:

$\{(|\psi_1\rangle,p_1), \ldots, (|\psi_n\rangle,p_n)\},$

where each pair $(|\psi_i\rangle,p_i)$ means the pure state $|\psi_i\rangle$ appears at probability $p_i$, for $i=1,\ldots,n$. Note $\sum_{i=1}^n p_i=1$.

A more compact and useful representation of a mixed state can be obtained from the type of Hilbert-space operators called density operators [KLM07, Sec. 3.5.1].

• The matrix representation of a density operator is a density matrix.

• The density matrix representing the pure state $|\psi\rangle$ is defined as the outer product

  $\rho \triangleq |\psi\rangle\langle\psi|.$

• The density matrix representing the mixed state $\{(|\psi_1\rangle,p_1), \ldots, (|\psi_n\rangle,p_n)\}$ is defined as the weighted sum of outer products:

  $\rho \triangleq \sum_{i=1}^n p_i|\psi_i\rangle\langle\psi_i|.$

  Note $\psi_i$ do not need to be basis states.

  Example 1

  Revisiting the example in Fig. 1, the density matrix of $|\psi_B\rangle$ is thus

  $\begin{aligned} \rho_B & = \frac{1}{2}|0_B\rangle\langle 0_B| + \frac{1}{2}|1_B\rangle\langle1_B| = \frac{1}{2}\begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} + \frac{1}{2}\begin{bmatrix} 0 \\ 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} \\ & = \frac{1}{2}\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} + \frac{1}{2}\begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \frac{1}{2}\mathbf{I}. \end{aligned}$

• It is important to know the effect of measuring a mixed state.

  Suppose the pure state $|\psi_i\rangle\langle\psi_i|$, where $i=1,\ldots,n$, is measured in the computational (Z) basis, then the probability of getting $|0\rangle$ as the measurement outcome is [WN17, Sec. 1.2.1]:

  $\Pr\{0|i\} = |\langle\psi_i|0\rangle|^2 = \langle\psi_i|0\rangle\langle\psi_i|0\rangle = \langle0|\psi_i\rangle\langle\psi_i|0\rangle.$

  Similarly, the probability of getting $|1\rangle$ as the measurement outcome is $\Pr\{1|i\} = \langle1|\psi_i\rangle\langle\psi_i|1\rangle$.

  Now suppose we are measuring the mixed state $\rho = \sum_i p_i|\psi_i\rangle\langle\psi_i|$. By the law of total probability, the probability of getting $|0\rangle$ is now 

  $\Pr\{0\} = \sum_i p_i\Pr\{0|i\} = \sum_i p_i\langle0|\psi_i\rangle\langle\psi_i|0\rangle = \langle0| \cdot \sum_i p_i|\psi_i\rangle\langle\psi_i| \cdot |0\rangle = \langle0|\rho|0\rangle.$

  Similarly, the probability of getting $|1\rangle$ is $\Pr\{1\} = \langle1|\rho|1\rangle$.

  Thus in general, the probability of measuring mixed state $\rho$ and getting basis vector $|i\rangle$ is

  $\Pr\{i\} = \langle i|\rho|i\rangle.$

  Example 2

  Continuing from Example 1, let us find out the probability of getting $|+\rangle$ when $\rho = \frac{1}{2} |0\rangle\langle0| + \frac{1}{2}|1\rangle\langle1|$ is measured in the Hadamard (X) basis.

  The probability of getting $|+\rangle$ is

  $\langle+|\rho|+\rangle = \begin{bmatrix}1/\sqrt{2} & 1/\sqrt{2}\end{bmatrix}\begin{bmatrix}1/2 & 0 \\ 0 & 1/2\end{bmatrix}\begin{bmatrix}1/\sqrt{2} \\ 1/\sqrt{2}\end{bmatrix} = \dfrac{1}{2}.$

  Similarly, the probability of getting $|-\rangle$ is $\langle-|\rho|-\rangle=\dfrac{1}{2}$.

  In case there is any confusion that mixed state $\rho$ is equivalent to $|+\rangle$, consider what happens when $|+\rangle$ is measured in the X basis: the measurement outcome is simply $|+\rangle$ at a probability of 1.

  Example 3

  [Leo10, Sec. 1.2]

• A quick way to test whether a density matrix represents a pure state or a mixed state is to use the trace operator [Gra21, p. 11; NC10, Theorem 2.5]:

  $\rho$ represents a pure state if $\text{tr}(\rho^2)=1$.

  $\rho$ represents a mixed state if $\text{tr}(\rho^2)\lt1$.

  ⚠ $\rho$ is positive-semidefinite (i.e., $\rho$ is a positive operator) and $\text{tr}(\rho)\equiv1$ for any density matrix $\rho$.

  A useful property of $\text{tr}$ is available through the observation that since $\langle\psi|\mathbf{A}|\psi\rangle$ is a scalar,

  $\langle\psi|\mathbf{A}|\psi\rangle = \text{tr}(\langle\psi|\mathbf{A}|\psi\rangle),$

  for matrix $\mathbf{A}$ and ket $|\psi\rangle$. Applying the cyclic property of $\text{tr}$, we get $\text{tr}(\langle\psi|\mathbf{A}|\psi\rangle) = \text{tr}(\mathbf{A}|\psi\rangle\langle\psi|)$, and consequently [WN17, Exercise 1.2.3]:

  $\text{tr}(\mathbf{A}|\psi\rangle\langle\psi|) = \langle\psi|\mathbf{A}|\psi\rangle.$

  (1)

If the explanation above is hard to grasp, see if edX Lecture 1.2 “The density matrix” of Quantum Cryptography by CaltechDelftX QuCryptox helps.

When applied with unitary operator $\mathbf{U}$, state $|\psi\rangle$ evolves into $\mathbf{U}|\psi\rangle$. Accordingly, the density matrix of the mixed state $\rho = \sum_{i=1}^n p_i|\psi_i\rangle\langle\psi_i|$ evolves into

Our adventure with the trace operator continues because an important application of the trace operator is determining the probability of getting result $m$ when applying measurement operator $\mathbf{M}_m$ to mixed state $\rho=\sum_i p_i|\psi_i\rangle\langle\psi_i|$.

By definition, the probability of getting result $m$ given initial state $|\psi_i\rangle$ is [NC10, p. 99]:

$\Pr\{m|i\} = |\mathbf{M}_m|\psi_i\rangle|^2 = \langle\psi_i|\mathbf{M}_m^\dagger\mathbf{M}_m|\psi_i\rangle = \text{tr}(\mathbf{M}_m^\dagger\mathbf{M}_m|\psi_i\rangle\langle\psi_i|).$

The last equality is due to Eq. (1). By the law of total probability,

Omitting the derivation in [NC10, pp. 99-100], the density matrix of the system after making measurement $\mathbf{M}_m$ and obtaining result $m$ is:

By the law of total probability,

$\rho = \sum_m\Pr\{m\}\rho_m = \sum_m\text{tr}(\mathbf{M}_m^\dagger\mathbf{M}_m\rho)\dfrac{\mathbf{M}_m\rho\mathbf{M}_m^\dagger}{\text{tr}(\mathbf{M}_m^\dagger\mathbf{M}_m\rho)} = \sum_m\mathbf{M}_m\rho\mathbf{M}_m^\dagger,$

implying

$\sum_m\mathbf{M}_m\mathbf{M}_m^\dagger = \mathbf{I},$

which is called the completeness equation. ⚠ Note $\mathbf{M}_m$ is unitary if and only if $m$ has one value.

Postulates of quantum mechanics

Using the language of the density operator, we can phrase the fundamental postulates of quantum mechanics as [NC10, pp. 98-102; Gra21, p. 11-12]:

Postulate 3 defines general/generalised measurement [NC10, Box 2.5], which consists of 1️⃣ a rule describing the probabilities of different measurement outcomes, and 2️⃣ a rule describing the post-measurement state.

• For applications where measurement is made once at the conclusion of some experiment, the main items of interest are the probabilities rather than the post-measurement state. For these applications, the mathematical tool of positive operator-valued measure (POVM) is applicable.
• To determine the post-measurement state but in a way that the measurement is repeatable and the outcome is deterministic, we use projective measurement.

The reduced density operator is an application of the density operator.

The reduced density operator is so useful it is indispensable in the analysis of composite quantum systems [NC10, Sec. 2.4.3].

Consider a composite system, with density matrix $\rho_{AB}$, consisting of Alice’s system and Bob’s system, there is often a need to express the state of Alice’s or Bob’s system in terms of $\rho_{AB}$.

The operation that takes us from $\rho_{AB}$ to $\rho_A$ (denoting Alice’s density matrix) or $\rho_B$ (denoting Bob’s density matrix) is called the reduced density operator.

The reduced density operator for Alice’s system is defined by

where $\text{tr}_B$ is a map of operators known as the partial trace over Bob’s system.

Suppose $|a_1\rangle$ and $|a_2\rangle$ are any two vectors in Alice’s state space, and furthermore, $|b_1\rangle$ and $|b_2\rangle$ are any two vectors in Bob’s state space, then the partial trace $\text{tr}_B$ is defined by the operation [NC10, (2.178)]:

Above, the notation $|a_1\rangle\langle a_2|\otimes|b_1\rangle\langle b_2|$ is equivalent to

$\left(|a_1\rangle\otimes|b_1\rangle\right)\left(\langle a_2|\otimes\langle b_2|\right) = |a_1b_1\rangle\langle a_2b_2|.$

To see why the definition above makes sense, suppose a quantum system is in the product state $\rho_{AB} = \rho_A\otimes\rho_B$, where $\rho_A$ and $\rho_B$ are the density matrices for subsystems $A$ and $B$ respectively, then

$\text{tr}_B(\rho_{AB}) = \text{tr}_B(\rho_A\otimes\rho_B) = \rho_A\text{tr}(\rho_B) = \rho_A,$

since the trace of any density matrix is 1. Similarly,

$\text{tr}_A(\rho_{AB}) =  \rho_B.$

In general, if

$\rho_{AB} = \sum_{ijk\ell}c_{ij}^{k\ell}|i\rangle\langle j|_A\otimes|k\rangle\langle \ell|_B,$

where $\{|i\rangle_A,|j\rangle_A\}$ is an orthonormal basis of $A$, and $\{|k\rangle_B,|\ell\rangle_B\}$ is an orthonormal basis of $B$, then the partial trace over $B$ is [WN17, Definition 1.6.1]:

For a quick summary of discussion up to this point, watch edX Lecture 1.7 “The partial trace” of Quantum Cryptography by CaltechDelftX QuCryptox.

Expressing a bipartite vector in the Schmidt basis makes it much easier to compute the partial trace of either subsystem. For this reason, let us discuss Schmidt decomposition.

For $\mathbf{A}\in\mathbb{F}^{n\times m}$, suppose its singular values are $\sigma_1,\ldots,\sigma_{\min(n,m)}$.

Then, the Schatten $p$-norm of $\mathbf{A}$, where $p\in[1,\infty]$, is defined as [Ber09, Proposition 9.2.3]:

$\|\mathbf{A}\|_{\sigma p} \triangleq \begin{cases} \left[\sum_{i=1}^{\min(n,m)}\sigma_i^p(\mathbf{A}) \right]^{1/p}, & 1\leq p\lt\infty,\\ \sigma_\max(\mathbf{A}), & p = \infty.\end{cases}$

When $p=1$, we have the Schatten 1-norm, which is also called the trace norm or nuclear norm [Ber09, p. 549]:

$\text{tr}\langle\mathbf{A}\rangle \triangleq \|\mathbf{A}\|_{\sigma1} = \sigma_1(\mathbf{A})+\cdots+\sigma_{\min(n,m)}(\mathbf{A}).$

When $p=2$, we have the Frobenius norm:

$\|\mathbf{A}\|_F \triangleq \left[\text{tr}(\mathbf{A}^\ast\mathbf{A})\right]^{1/2} = \|\mathbf{A}\|_{\sigma2}.$

When $p=\infty$, we have the spectral norm:

$\|\mathbf{A}\|_{\sigma\infty} = \sigma_\max(\mathbf{A}).$

The secret key rate is the fraction of secure key bits produced per protocol round, where a round is the transmission of a quantum state through the quantum channel [Gra21, p. 38].

The secret key rate generally depends on the total number of rounds $M$ performed.

The asymptotic secret key rate (often just asymptotic key rate) is the secret key rate when $M\to\infty$ is assumed to simplify analysis.

• Assuming direct reconciliation, the asymptotic key rate of any quantum key distribution (QKD) protocol with one-way error correction is lower-bounded by the Devetak-Winter rate [DW05]:

  $r_\text{DW} = I(A;B) - I(A;E),$

  where $I$ denotes quantum mutual information, $A$, $B$ and $E$ are the random variables representing Alice’s, Bob’s and Eve’s raw key bits.

• An intuitive interpretation of the Devetak-Winter rate: the fraction of secret bits generated per round of using the protocol is equal to the amount of information shared by Alice and Bob, $I(A; B)$, minus the amount of information that Eve has on Alice’s part of the key, $I(A;E)$ [Wol21, p.145].

Assuming $M\to\infty$ is not realistic, and the security of a QKD protocol has to be analysed assuming a finite $M$ and generally finite resources.

Analysis of the secret key rate and associated security properties of a QKD protocol is called finite-key analysis [TLGR12], to be covered in the future.

Methods for analysing the security of quantum key distribution (QKD) schemes/protocols are still being developed [PAB+20, PR22].

• These methods combine existing cryptographic notions and techniques with quantum information theory.
• Depending on the implementation of the QKD scheme, physical laws governing the implementation (e.g., quantum-optical laws) also play a role.
• Compared to computational security, which can be reduced to complexity-theoretic reasoning based on the Turing machine, methods for analysing the security of QKD schemes are thus more involved and, in terms of the transdisciplinary effort required, more challenging.

The security of a QKD scheme is typically analysed in terms of the level of success of 1️⃣ individual attacks, 2️⃣ collective attacks and 3️⃣ coherent attacks; in 🔼 increasing order of power given to the adversary [Wol21, Sec. 5.3.1].

• Individual and collective attacks are usually considered in order to simplify the security analysis, but it is necessary to also consider coherent attacks in order to prove the security of a QKD scheme.
• We can analyse the different types of attacks by the way 😈 Eve interacts with 👩 Alice’s signals and how Eve processes the information she gets in this way.

• General procedure for extracting information from a quantum system:

  1. 😈 Eve attaches an ancilla system in the predefined state $|E\rangle_E\langle E|$ to the quantum state $\rho_A$ transmitted by 👩 Alice; $|E\rangle_E\langle E|$ and $\rho_A$ are density-matrix representations of quantum states.

     Please spend time understanding pure state, mixed state and density matrix.

  2. 😈 Eve then performs a unitary operation $\mathbf{U}$ on the composite system, which leaves the state of the ancilla system in the form:

     $\rho_E = \text{tr}_A\left(\mathbf{U}^\dagger \rho_A\otimes|E\rangle_E\langle E| \mathbf{U}\right),$

     where $\otimes$ is the Kronecker operator and $\text{tr}_A$ denotes partial trace.

     Please spend time understanding reduced density matrix and partial trace.

The security of a QKD scheme is also often analysed in terms of composability, short for universally composable security.

• Informally, we say a QKD scheme is composable if the key it produces is almost as good as if it were distributed with an ideal key distribution protocol [Van06, Sec. 12.2.6].
• A cryptographic primitive, which is secure when used with an ideally secret key, must still be secure if used with a QKD-distributed key.
• Composability is critical since QKD-derived secret keys are used in other applications, e.g., data encryption [JCM+22].

TODO: Trace distance criterion [PR22], security = correctness + secrecy [Gra21]. Asymptotic vs finite-key security analysis.

Security evaluation of practical QKD implementations involves evaluating the level of success of “quantum hacking” (i.e., side-channel attacks on QKD).

The joint state, $\rho_{AB}$, of two quantum systems $A$ and $B$ is separable [WN17, Definition 2.1.1] if there exists a probability distribution $\{p_i\}$, and sets of density matrices $\{\rho_i^A\}_i$ and $\{\rho_i^B\}_i$ such that

If such an expression for $\rho_{AB}$ does not exist, $\rho_{AB}$ is entangled [WN17, Definition 2.1.1].

Specifically, if $\rho_{AB}=|\psi\rangle\langle\psi|_{AB}$ is a pure state, then $|\psi\rangle_{AB}$ is separable if and only there exists $|\psi\rangle_A$ and $|\psi\rangle_B$ such that

$|\psi\rangle_{AB} = |\psi\rangle_A\otimes|\psi\rangle_B.$

Singular values, like eigenvalues, are an intrinsic property of a matrix. Unsurprisingly, they can be defined in terms of eigenvalues:

Singular values can also be defined through the operation called singular value decomposition:

Spectral theorem is one of the fundamental theorems of linear algebra [ABH09, Sec. 3.6].

Based on the spectral theorem, spectral decomposition is an essential tool in quantum theory [NC10, Box 2.2].

Multiple equivalent interpretations of the spectral theorem exist, e.g., [ABH09, Theorems 3.6.4 and 3.6.12].

The interpretation in Theorem 1 directly defines spectral decomposition, and is hence also called the spectral decomposition theorem.

Any normal operator, $\mathbf{M}$, has an outer product representation [KLM07, Sec. 2.4; Mey00, p. 517]:

$\mathbf{M} = \sum_i\lambda_i|i\rangle\langle i|,$

where

• $(\lambda_i, |i\rangle)$ are the eigenpairs of $\mathbf{M}$;
• $|i\rangle$ form an orthormal basis of the Hilbert space in which $\mathbf{M}$ is defined.

The outer products $\mathbf{P}_i \triangleq |i\rangle\langle i|$ are projectors that satisfy

• the completeness relation: $\sum_i\mathbf{P}_i = \mathbf{I}$; and
• the orthonormality relation: $\mathbf{P}_i\mathbf{P}_j = \delta_{ij}\mathbf{P}_i$, where $\delta_{ij}$ is the Kronecker delta.

At the highest level, the time-evolution postulate of quantum theory [KLM07, p. 44] states

But how do we arrive at the understanding of the role of the unitary operator?

Consider the evolution of one quantum state:

$\alpha_1|x_1\rangle + \cdots + \alpha_n|x_n\rangle$

to another quantum state:

$\alpha'_1|x_1\rangle + \cdots + \alpha'_n|x_n\rangle,$

where $|x_1\rangle, \ldots, |x_n\rangle$ are basis state vectors. Suppose there exists a linear operator $\mathbf{U}$ that captures this evolution:

$\begin{bmatrix}\alpha'_1 \\ \vdots \\ \alpha'_n\end{bmatrix} = \mathbf{U}\begin{bmatrix}\alpha_1 \\ \vdots \\ \alpha_n\end{bmatrix},$

such that $\sum_{i=1}^n|\alpha'_i|^2 = \sum_{i=1}^n|\alpha_i|^2$. Besides linearity and conservation of overlaps (overlap of a vector with itself = norm squared), there are other properties that $\mathbf{U}$ must satisfy.

Define $\mathbf{U}(t)$ as a time-dependent map of one quantum state to another: $|\psi(t)\rangle = \mathbf{U}(t)|\psi(0)\rangle$, then the additional properties that $\mathbf{U}(t)$ must satisfy are [Hir04, Sec. 8.3.1]:

1. Decomposability: $\mathbf{U}(t_1+t_2) = \mathbf{U}(t_1)\mathbf{U}(t_2), \forall t_1,t_2\in\mathbb{R}$.
2. Continuity/smoothness: $|\psi(t')\rangle = \lim_{t\to t'}|\psi(t)\rangle = \lim_{t\to t'}\mathbf{U}(t)|\psi(0)\rangle$.

Summarising the discussion so far, the time-evolution postulate can be rephrased in more precise mathematical terms [NC10, Postulate 2']:

Measurement of information is crucial to cybersecurity. One of these measures is distance measure between two quantum states.

• Static measures quantify how close two quantum states are [NC10, p. 399].
• Dynamic measures quantify how well information is preserved during a dynamic process [NC10, p. 399]. Dynamic measures can be derived from static measures.

Distance measures are defined in a way that makes sense to the analysis they are applied to, hence more than one distance measure exist in the literature, but two of these measures are in particularly wide use, namely trace distance and fidelity.

The focus here is trace distance, which for probability density functions $p_x,q_x$ and index set $x$ is defined to be [NC10, Eq. (9.1)]:

$D(p_x, q_x) \triangleq \frac{1}{2}\sum_x |p_x - q_x|.$

Trace distance is also called $L_1$ distance and Kolmogorov distance.

Extending the earlier definition to quantum states, the trace distance between density matrices $\rho$ and $\sigma$ is defined as [MM12, Sec. 3.11]:

$D(\rho,\sigma)\triangleq\frac{1}{2}\text{tr}|\rho-\sigma|.$

If

The trace of a square matrix $\mathbf{A}$, denoted by tr$\mathbf{A}$ or tr$(\mathbf{A})$, is a linear map that maps the matrix to a complex number, and is specifically the sum of the diagonal elements of the matrix.

Obvious properties:

• $\text{tr}\mathbf{A} = \text{tr}\mathbf{A}^\top$ [Ber18, p. 287].
• If $\mathbf{AB}$ and $\mathbf{BA}$ are square matrices, then the cyclic property applies: $\text{tr}(\mathbf{AB}) = \text{tr}(\mathbf{BA})$ [Ber18, p. 287].

Useful property involving brakets:

• If $\mathbf{A}$ is an $n\times n$ matrix, then $\text{tr}(\mathbf{A}) = \sum_i\langle i | \mathbf{A}| i\rangle$, where $\{|i\rangle\}$ is any orthonormal basis of $\mathbb{C}^n$ [WN17, Definition 1.2.4].

A vector norm $\|\cdot\|$ on $\mathbb{C}^{m\times n}$ is unitarily invariant if for any $\mathbf{A}\in\mathbb{C}^{m\times n}$ and unitary matrices of appropriate dimensions $\mathbf{U}$ and $\mathbf{V}$, we have $\|\mathbf{A}\|=\|\mathbf{UAV}\|$ [Hog13, Sec. 24.3].