Registers, Tensor Products, and Partial Trace

If $\dim V=0$, [F1] gives $V=\{0\}$, so its only endomorphism is $D=0$. Assume henceforth $\dim V=m>0$ and choose an ordered basis.

If every entry of the matrix of $D$ were zero, [F2] would make $D$ vanish on every basis vector and hence on every vector. Thus if $D\mathrm{\ne }0$ there are indices $i,j<m$ with matrix entry $D_{ij}\mathrm{\ne }0$. Define $A({\sum }_{k<m}{a}_k{b}_k):=a_i{b}_j$ using the ordered basis chosen in step 1.1. Unique coordinates [F7] make this well-defined; for scalars $\alpha ,\beta$ and vectors with coordinate lists $(a_k)$ and $(c_k)$, the coordinate list of their linear combination is $(\alpha a_k+\beta c_k)$, so the formula gives $A(\alpha x+\beta y)=\alpha A(x)+\beta A(y)$. Thus $A$ is an endomorphism. Its matrix sends $b_i$ to $b_j$ and every other basis vector to $0$, so that matrix is $E_{ji}$.

By [F4], the matrix of $D\circ A$ is $[D][A]=[D]E_{ji}$. Row-by-column multiplication [F5] gives $([D]E_{ji}{)}_{kk}=D_{kj}{\delta }_{ik}$, so every diagonal entry is $0$ except the $(i,i)$ entry, which is $D_{ij}$. By [F6], $\mathrm{tr}(D\circ A)=D_{ij}\mathrm{\ne }0$. This contradicts the hypothesis for every $A$. Therefore $D=0$, including the zero-dimensional case from step 1.1.

For $n=0$, the declared space is $\mathbb{C}$ with its usual pairing and basis $\{1\}$. For $n>0$, repeated use of [F1] and the associativity identifications in [F2] shows that the lexicographically ordered elementary product vectors form a basis of the tensor space. If one factor basis is empty, the product basis is empty and the tensor space is zero.

Use the coordinates in this product basis to define the pairing by the standard coordinate formula of [F3]. The basis gives unique coordinates by [F5], so this is a well-defined sesquilinear positive-definite pairing. It is linear first and conjugate-linear second by [F3] and [F4].

Write $x_k={\sum }_{i_k}{x}_{k,i_k}{e}_{k,i_k}$ and $y_k={\sum }_{i_k}{y}_{k,i_k}{e}_{k,i_k}$ in the supplied bases, using their unique coordinates [F5]. Multilinearity of elementary tensors [F6], applied one factor at a time, gives the coefficient ${\prod }_k{x}_{k,i_k}$ of each product-basis vector in ${⨂}_k{x}_k$, and similarly ${\prod }_k{y}_{k,i_k}$ for ${⨂}_k{y}_k$. The standard coordinate formula [F3] therefore gives ${\sum }_{(i_0,\dots ,i_{n-1})}{\prod }_k{x}_{k,i_k}\overline{y_{k,i_k}}$. Repeated finite distributivity factors this as ${\prod }_k{\sum }_{i_k}{x}_{k,i_k}\overline{y_{k,i_k}}$, which is the displayed product formula. For $n=0$ both expressions are $1$; if a factor has dimension $0$, the product basis is empty and both the tensor pairing and product over factor pairings are $0$.

The product formula depends only on the factor pairings. Any other supplied orthonormal bases therefore give the same pairing on elementary tensors; elementary tensors span by [F1], so sesquilinearity makes the pairings equal everywhere.

The factor permutation in the Definition sends the product basis bijectionally to the product basis in the reordered factors. Unique coordinates [F5] make its linear extension well-defined, and [F7] makes that extension linear; applying the inverse permutation to basis vectors gives the inverse linear map. For the empty list the definition is already the identity.

For $j,k<d$, the coordinate formula in [F1] gives $⟨e_j,e_k{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}={\sum }_{r<d}{\delta }_{rj}{\delta }_{rk}$, which equals $1$ when $j=k$ and $0$ when $j\mathrm{\ne }k$. Thus the listed vectors are orthonormal.

By [F2] the same vectors form a basis, so they are an orthonormal basis of $Q_d$.

By [F3], the zero-qubit register is the empty tensor product $\mathbb{C}$ with basis $\{1\}$, distinct from the zero-dimensional coordinate space ${\mathbb{C}}^0$.

For each basis vector $e_{i^{\mathrm{\prime }}}$ of $H_A$, prescribe $S{e}_{i^{\mathrm{\prime }}}={\sum }_{i<a}({\sum }_{j<b}{R}_{(i,j),(i^{\mathrm{\prime }},j)})e_i$. Each inner and outer sum is finite; when $b=0$ its inner sum is $0$.

By the ordered-basis coordinate property [F2], these prescribed images extend uniquely to a linear map $S:H_A\to H_A$, and its matrix has exactly the displayed entries. Each entry is linear in the entries of $R$, so the resulting assignment $R\mapsto S$ is linear. This defines ${\mathrm{Tr}}_B$ even when either basis is empty.

For $n=0$, the prescribed map is the identity on $\mathbb{C}$. For $n>0$, the function $(x_0,\dots ,x_{n-1})\mapsto T_0{x}_0\otimes \cdots \otimes T_{n-1}{x}_{n-1}$ is linear in each argument: replacing any $x_k$ by $a{x}_k+b{y}_k$ replaces its image by $a{T}_k{x}_k+b{T}_k{y}_k$ by [F3], and tensoring is linear in that factor.

For $n>0$, [F2] gives a unique linear extension of the multilinear function in step 1.1, hence the map in the Definition. Repeated use of [F1] shows that elementary tensors span any nonempty iterated tensor product. If some $H_k=0$, every source elementary tensor is zero by [F1], so the domain is zero and the unique linear map from it is zero. If some $K_k=0$, the same argument makes the codomain zero, and the unique linear map to it is zero. In either case the displayed rule holds. For $n=0$, the empty elementary tensor is $1\in \mathbb{C}$ by [F2]; its prescribed image is $1$, which uniquely determines the identity linear map.

If $n=0$, the declared tensor space is $\mathbb{C}$, its product basis is $\{1\}$, and its dimension is $1$, the empty product. If $n=1$, the statement is exactly the supplied orthonormal basis of that factor.

For $n\ge 2$, repeated application of [F2] and the parenthesization identifications in [F4] shows that the elementary tensors of the factor bases form a basis indexed by the Cartesian product of their index sets. By [F1], the inner product of two such basis tensors is the product of their factor inner products; it is $1$ for equal tuples and $0$ for unequal tuples. Therefore this basis is orthonormal.

Repeated application of [F3] gives the product of the factor dimensions. If any $d_k=0$, [F2] makes the product basis empty and both sides are zero; the empty and one-factor cases were handled in step 1.1. Thus the formula holds in every finite case.

At $n=0$, the domain has just the empty word and the codomain is $\{0,\dots ,2^0-1\}=\{0\}$. By [F1], its index is $0$, so the map is bijective.

Assume the result for $n$. For a word of length $n+1$, write its first bit as $b\in \{0,1\}$ and its remaining word as $y\in \{0,1{\}}^n$. Splitting the first term from the sum in [F1] gives ${\mathrm{enc}}_{n+1}(b,y)=b{2}^n+{\mathrm{enc}}_n(y)$. By the induction hypothesis, the tail index ranges bijectively over $\{0,\dots ,2^n-1\}$.

If $b=0$, the resulting indices are exactly $0,\dots ,2^n-1$. If $b=1$, they are exactly $2^n,\dots ,2^{n+1}-1$. The two intervals are disjoint and their union is the full target, so equality of two encoded indices forces the first bits to agree and every target index is attained. For either fixed first bit, injectivity and surjectivity of the tail encoding give the corresponding claims for the remaining word.

By [F5], the base case and induction step prove bijectivity for all $n\ge 0$. A permutation $\sigma$ of the bit positions is a bijection on words, with inverse the permutation ${\sigma }^{-1}$; composing it with the basis labeling in [F2] therefore permutes the basis [F3, F4].

By [F8], choose ordered orthonormal bases $(e_i{)}_{i<a}$ of $H_A$ and $(f_j{)}_{j<b}$ of $H_B$, and set $S={\mathrm{Tr}}_B(R)$. For any $T\in \mathrm{End}(H_A)$, [F1], [F6] and [F7] give $\mathrm{tr}(S\circ T)={\sum }_{i,i^{\mathrm{\prime }}<a}{\sum }_{j<b}{R}_{(i,j),(i^{\mathrm{\prime }},j)}{T}_{i^{\mathrm{\prime }}i}$.

The identity $I_{H_B}$ is linear by [F9], so [F2] defines the linear map $T\otimes I_{H_B}$; its composite with $R$ is linear by [F9]. In the product basis, [F2] gives the matrix entry $T_{i^{\mathrm{\prime }}i}{\delta }_{j^{\mathrm{\prime }}j}$ of $T\otimes I$. By [F6] and [F7], $\mathrm{tr}(R\circ (T\otimes I))={\sum }_{i,j}{\sum }_{i^{\mathrm{\prime }},j^{\mathrm{\prime }}}{R}_{(i,j),(i^{\mathrm{\prime }},j^{\mathrm{\prime }})}{T}_{i^{\mathrm{\prime }}i}{\delta }_{j^{\mathrm{\prime }}j}={\sum }_{i,i^{\mathrm{\prime }},j}{R}_{(i,j),(i^{\mathrm{\prime }},j)}{T}_{i^{\mathrm{\prime }}i}$, which is the same finite sum as in step 1.1. Thus $S$ satisfies the displayed trace identity.

If $S^{\mathrm{\prime }}$ is any other map value at $R$ satisfying the identity for every $T$, then $\mathrm{tr}((S-S^{\mathrm{\prime }})\circ T)=0$ for every $T$. Apply [F5] on $H_A$ to obtain $S=S^{\mathrm{\prime }}$. Since this holds for every $R$, the trace identity characterizes the partial-trace map uniquely.

Repeat steps 1.1 and 2.1 with any other ordered orthonormal basis of $H_B$. The right-hand side is the trace of the same endomorphism $R\circ (T\otimes I_{H_B})$, and [F4] makes that trace basis-independent. Step 3.1 then forces the resulting partial-trace operator to equal $S$.

If $H_B=0$, the product space and $R$ are zero, [F1] is the empty sum, and both sides of the trace identity are $0$. If $H_A=0$, the input and output endomorphism spaces contain only the zero map, so the same identity and uniqueness hold.

By [F7], each $S_k{T}_k$ is linear and the composite of the two tensor maps is linear, so [F1] applies to both sides. On an elementary tensor ${⨂}_{k<n}{x}_k$, the left side of the composition identity equals ${⨂}_{k<n}{S}_k(T_k{x}_k)$ by [F1], which is the value of the right side. Since elementary tensors span by [F2], the two linear maps are equal.

By [F6], choose orthonormal bases for the finite factor spaces. For elementary tensors $x={⨂}_{k<n}{x}_k$ and $y={⨂}_{k<n}{y}_k$, the product pairing in [F2] and the factor adjoint identities in [F4] give $⟨({⨂}_k{T}_k)x,y⟩={\prod }_k⟨T_k{x}_k,y_k⟩={\prod }_k⟨x_k,T_k^{\ast }{y}_k⟩=⟨x,{⨂}_k{T}_k^{\ast }{y}_k⟩$. The pairing is extended using the first-linear convention [F5].

Each factor identity and the identity on the tensor space are linear by [F7]. The tensor map ${⨂}_{k<n}{I}_{H_k}$ fixes every elementary tensor by [F1]. The identity map does too; spanning in [F2] gives equality. If $n=0$, both maps are the identity on $\mathbb{C}$.

Sesquilinearity and spanning extend the identity in step 1.2 to all $x,y$. By existence and uniqueness in [F3] and the defining condition [F4], $({⨂}_k{T}_k{)}^{\ast }={⨂}_k{T}_k^{\ast }$. For $n=0$ both sides are the identity on $\mathbb{C}$; zero-dimensional factors are covered because the product bases may be empty.

By [F1], $P_{\sigma }$ sends each product-basis vector to exactly one product-basis vector, and the inverse permutation sends it back. Thus the basis assignment extends to a bijective linear map whose inverse is $P_{{\sigma }^{-1}}$. The empty list gives the identity on $\mathbb{C}$.

Write an arbitrary vector as ${\sum }_{\alpha }{c}_{\alpha }{e}_{\alpha }$ in the orthonormal product basis from [F2]. Its squared norm is ${\sum }_{\alpha }\mathrm{\mid }{c}_{\alpha }{\mathrm{\mid }}^2$. The map permutes that basis, so its image has the same coefficients in a permuted orthonormal basis and the same squared norm. Thus $P_{\sigma }$ is a linear isometry. If a factor is zero-dimensional, both tensor spaces are zero and the unique map between them is bijective and isometric.

When the source and target are the same register, steps 1.1 and 2.1 give an invertible linear isometry of that space, hence a unitary operator by [F3].

By [F10], choose ordered orthonormal bases $(e_i)$ and $(f_j)$ for $H_A,H_B$, and write $S={\mathrm{Tr}}_B(R)$. Since $R$ is self-adjoint by [F1], [F2] gives $R_{(i,j),(i^{\mathrm{\prime }},j)}=\stackrel{‾}{R_{(i^{\mathrm{\prime }},j),(i,j)}}$. Summing over $j$ in [F3] yields $S_{i{i}^{\mathrm{\prime }}}=\stackrel{‾}{S_{i^{\mathrm{\prime }}i}}$, so $S$ is self-adjoint. The product basis is orthonormal by [F5].

For $x={\sum }_i{x}_i{e}_i$, [F3] and [F6] give $⟨Sx,x⟩={\sum }_{i,i^{\mathrm{\prime }},j}{R}_{(i,j),(i^{\mathrm{\prime }},j)}{x}_{i^{\mathrm{\prime }}}\overline{x_i}$. For each fixed $j$, the coefficient of $e_i\otimes f_j$ in $R(x\otimes f_j)$ is ${\sum }_{i^{\mathrm{\prime }}}{R}_{(i,j),(i^{\mathrm{\prime }},j)}{x}_{i^{\mathrm{\prime }}}$; orthonormality [F5] therefore gives $⟨R(x\otimes f_j),x\otimes f_j⟩={\sum }_{i,i^{\mathrm{\prime }}}{R}_{(i,j),(i^{\mathrm{\prime }},j)}{x}_{i^{\mathrm{\prime }}}\overline{x_i}$. Summing these equalities over $j$ yields $⟨Sx,x⟩={\sum }_j⟨R(x\otimes f_j),x\otimes f_j⟩$. Each summand is nonnegative by [F1], hence $⟨Sx,x⟩\ge 0$ for every $x$. Together with step 1.1, the definition in [F1] gives $S\ge 0$.

In [F4] set $T=I_{H_A}$. By [F7], $I_{H_A}\otimes I_{H_B}$ fixes every elementary tensor; these span by the product-basis result [F5], so it is $I_{H_A\otimes H_B}$. Therefore [F4] gives $\mathrm{tr}(S\circ I_{H_A})=\mathrm{tr}(R\circ I_{H_A\otimes H_B})$. By [F8] the composites are $S$ and $R$, so their traces are equal by [F9]. Empty bases give empty traces $0$ on zero-dimensional factors, so the equality holds there as well.