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.