11 Wielandt Bound
This chapter proves the quantum Wielandt bounds of [ SPGWC10 ] . For a primitive normalized tensor, it compares the uniform vector-spreading index \(q(\mathcal{E}_A)\) with the first exact word length \(\iota (A)\) satisfying \(S_{\iota (A)}(A)=M_{D}(\mathbb {C})\) and proves \(\iota (A)\le (D^2-\operatorname{kr}(A)+1)D^2\). The cumulative bound \(T_{D^2}(A)=M_{D}(\mathbb {C})\) is an intermediate step in the proof of Lemma 1.
11.1 Cumulative span
The exact-word identities used in this section are proved in Section 11.6. The stabilization and spectral linear algebra behind the cumulative estimates are collected in Section 11.7.
Let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices. For a word \(w=(i_1,\ldots ,i_n)\), its word evaluation is
with the empty word evaluated as the identity matrix.
The fixed-length vector span at length \(n\) is
This is \(S_n(K)|\varphi \rangle \) in the notation of [ SPGWC10 ] .
11.1.1 Paper primitivity and indices
For the quantitative bounds, write \(d'=\dim S_1(A)\) for the number of linearly independent Kraus operators. The source definitions and Proposition 3 of [ SPGWC10 ] distinguish uniform vector spreading, eventual exact-word spanning, and spectral strong irreducibility.
The next seven results use the following notation. For nonnegative integers \(d\) and \(D\), let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, and let \(\mathcal{E}_K\) be its Kraus map.
For every choice of \(d\), \(D\), and \(K\) as above, every \(q\ge 0\), and every \(\varphi \in \mathbb {C}^D\),
Expand the Kraus representation of the \(q\)-fold iterate. Each summand is \(K^w|\varphi \rangle \! \langle \varphi |(K^w)^\dagger =|K^w\varphi \rangle \! \langle K^w\varphi |\).
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then \(\mathcal{E}_K^q(|\varphi \rangle \! \langle \varphi |){\gt}0\) for every \(\varphi \neq 0\).
The preceding theorem expresses the image as the frame operator of the spanning family \((K^w\varphi )_{|w|=q}\). A finite frame operator is positive definite exactly when its vectors span the ambient space.
For every choice of \(d\), \(D\), and \(K\) as above and every \(n\ge 0\), the iterate \(\mathcal{E}_K^n\) maps positive-semidefinite matrices to positive-semidefinite matrices.
Decompose a positive-semidefinite matrix into a finite sum of rank-one positive matrices and apply Theorem 11.1.1.1 to every summand.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). Then \(\mathcal{E}_K^q(\rho ){\gt}0\) for every nonzero positive-semidefinite matrix \(\rho \).
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). Then every nonzero positive-semidefinite fixed point of \(\mathcal{E}_K\) is positive definite.
A fixed point of \(\mathcal{E}_K\) is fixed by \(\mathcal{E}_K^q\), whose action on every nonzero positive-semidefinite matrix is positive definite.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). For every \(p{\gt}0\), each nonzero positive-semidefinite fixed point of \(\mathcal{E}_K^p\) is positive definite.
If \(\mathcal{E}_K^p(\rho )=\rho \), then \(\mathcal{E}_K^{pq}(\rho )=\rho \). Factor this iterate as \(\mathcal{E}_K^q\mathcal{E}_K^{(p-1)q}\). The inner image is nonzero and positive semidefinite, so the outer application is positive definite.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), if \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \), then the Kraus map \(\mathcal{E}_K\) is irreducible.
Let \(P\) be an invariant orthogonal projection. Every word \(K^w\) preserves \(\operatorname {ran}P\). If \(P\neq 0\), choose a nonzero vector in this range. Its length-\(q\) word orbit spans \(\mathbb {C}^D\) by hypothesis and remains in \(\operatorname {ran}P\), hence \(P=\mathbb {1}\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be positive. If \(E(X)=\mu X\), then \(E(X^\dagger )=\overline\mu X^\dagger \).
Positivity implies that \(E\) preserves adjoints. Taking the adjoint of \(E(X)=\mu X\) gives the result.
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be linear. If \(E(X)=\mu X\) and \(\mu ^p=1\), then \(E^p(X)=X\).
Theorem 8.1.8 gives \(E^p(X)=\mu ^pX=X\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be positive. If \(E(X)=\mu X\) and \(\mu ^p=1\), then \(E^p(X^\dagger )=X^\dagger \).
The conjugate eigenvalue is \(\overline\mu \), and \((\overline\mu )^p=\overline{\mu ^p}=1\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) preserve the trace. If \(E(X)=\mu X\) and \(\mu \neq 1\), then \(\operatorname{tr}(X)=0\).
Trace preservation gives \(\mu \operatorname{tr}(X)=\operatorname{tr}(E(X))=\operatorname{tr}(X)\). Since \(\mu -1\neq 0\), the trace vanishes.
Let \(E\) be a channel, and suppose \(E(X)=\mu X\) with \(X\neq 0\), \(\mu \neq 1\), and \(\mu ^p=1\). Then there is a nonzero Hermitian matrix \(H\) such that \(\operatorname{tr}(H)=0\) and \(E^p(H)=H\).
At least one of \(X+X^\dagger \) and \(i(X^\dagger -X)\) is nonzero. Both are Hermitian, both have trace zero, and each is fixed by \(E^p\).
Suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). If \(p{\gt}0\) and \(\rho ,\sigma \) are nonzero positive-semidefinite fixed points of \(\mathcal{E}_K^p\), then \(\sigma =c\rho \) for some \(c\in \mathbb {C}\).
Fixed-length spreading makes every nonzero positive-semidefinite fixed point of \(\mathcal{E}_K^p\) positive definite. The critical-scalar argument then gives proportionality.
If \(E\) is completely positive, then \(E^p\) is completely positive for every \(p\geq 0\).
Induct on \(p\), using complete positivity of the identity map at \(p=0\) and closure of completely positive maps under composition for the induction step.
If \(E\) is a channel, then \(E^p\) is a channel for every \(p\geq 0\).
Complete positivity and trace preservation are both closed under composition and hold for the identity map.
Let \(K\) be trace-preserving and suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). If \(p{\gt}0\) and \(H=H^\dagger \) satisfies \(\operatorname{tr}(H)=0\) and \(\mathcal{E}_K^p(H)=H\), then \(H=0\).
Decompose \(H\) as a difference of positive-semidefinite fixed points of the channel \(\mathcal{E}_K^p\). Both are proportional to one nonzero fixed point. Their traces and \(\operatorname{tr}(H)=0\) force equal coefficients, hence \(H=0\).
Let \(D{\gt}0\), and let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices satisfying
Suppose there is a common length \(q\ge 0\) such that \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then there is a positive-definite matrix \(\rho \) such that \(\mathcal{E}_K(\rho )=\rho \).
Let \(D{\gt}0\), and let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices satisfying
Suppose there is a common length \(q\ge 0\) such that \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then the Kraus map \(\mathcal{E}_K\) is primitive: it has a nonzero fixed point and \(1\) is its only peripheral eigenvalue.
The normalization makes \(\mathcal{E}_K\) a channel, so Theorem 8.1.20 gives a nonzero positive-semidefinite fixed point. This supplies the peripheral eigenvalue \(1\). Theorem 11.1.1.7 gives irreducibility. Thus \(\mathcal{E}_K\) is an irreducible channel. By Theorem 2.13.2.7, every peripheral eigenvalue \(\mu \) is a root of unity; choose \(p{\gt}0\) with \(\mu ^p=1\).
Suppose \(\mu \neq 1\). Theorem 11.1.1.12 gives a nonzero Hermitian matrix \(H\) with \(\operatorname{tr}(H)=0\) and \(\mathcal{E}_K^p(H)=H\). Theorem 11.1.1.16 gives \(H=0\), a contradiction. Thus \(\mu =1\).
11.2 Nonzero trace product
Let \(T_N(K)\) be the span of the products of at most \(N\) matrices from a finite family \(K\). If \(D{\gt}0\) and \(T_N(K)=M_{D}(\mathbb {C})\), then there are a word \(w\), a nonzero scalar \(\mu \), and a nonzero vector \(\varphi \in \mathbb {C}^D\) such that
Since the identity lies in \(T_N(K)\) and has nonzero trace, some word of length at most \(N\) has nonzero trace. Such a matrix has a nonzero eigenvalue and a corresponding nonzero eigenvector by Theorem 11.7.4.
11.3 Eigenvector spreading
Let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, where \(D{\gt}0\), and let \(\varphi \neq 0\). If, for some \(N\), words in \(K\) of length at most \(N\) span \(M_{D}(\mathbb {C})\), then the vectors \(K^w\varphi \) with \(|w|\leq D-1\) span \(\mathbb {C}^D\).
The cumulative vector spaces are monotone and have dimension at most \(D\). Once two consecutive spaces agree, the common space is invariant under every \(K^i\). Full cumulative matrix span then forces it to contain \(M_{D}(\mathbb {C})\varphi =\mathbb {C}^D\). Since the initial space is nonzero, it reaches dimension \(D\) by step \(D-1\).
Suppose \(K^{i_0}\varphi =\mu \varphi \) with \(\mu \neq 0\). For every \(n\), the span of \(K^w\varphi \) over words with \(|w|\leq n\) equals \(H_n(K,\varphi )\).
Repeating the letter \(i_0\) pads a word of length \(m\leq n\) to length \(n\). Its action on \(\varphi \) gains the nonzero factor \(\mu ^{n-m}\), so every shorter-word vector belongs to the fixed-length span. The reverse inclusion is immediate.
Let \(K=(K^i)_{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, where \(D{\gt}0\), and suppose that \(S_n(K)=M_{D}(\mathbb {C})\) for every sufficiently large \(n\). If \(\varphi \neq 0\), \(\mu \neq 0\), and \(K^{i_0}\varphi =\mu \varphi \), then \(H_{D-1}(K,\varphi )=\mathbb {C}^D\).
Eventual fullness gives a level at which the cumulative matrix span is all of \(M_{D}(\mathbb {C})\). The cumulative vector spaces therefore reach \(\mathbb {C}^D\) by level \(D-1\). The eigenvector relation then pads shorter words to length \(D-1\) by nonzero powers of \(\mu \).
11.4 Quantum Wielandt bounds
Section 11.8 proves the one-step augmentation facts used in cases (2) and (3). The blocking identities used in the general case are proved in Section 11.9.
In this section we return to the notation of [ Wol12 , Theorem 6.9 ] : \(K_n\) is the complex linear span of the Kraus operators of the \(n\)-th power of the channel, \(k=\dim K_1\) is the Kraus rank, and \(q\) is the least integer such that \(K_m=M_{d}(\mathbb {C})\) for every \(m\geq q\).
For a finite Kraus family on \(M_{d}(\mathbb {C})\), define \(k=\dim K_1\). When the family has eventually full word spans, define
For a primitive quantum channel the set in the second definition is nonempty by Theorem 8.10.3.
If the exact word spans are eventually full, then the least threshold \(q\) is itself admissible. It is no larger than any other admissible threshold. In particular, for a trace-preserving Kraus family, \(K_N=M_{d}(\mathbb {C})\) implies \(q\leq N\).
The set of admissible thresholds is nonempty by eventual fullness, so its infimum in \(\mathbb N\) belongs to the set and is minimal. Trace preservation propagates the identity \(K_N=M_{d}(\mathbb {C})\) to every \(K_m\) with \(m\geq N\).
Let \(T:M_{d}(\mathbb {C})\to M_{d}(\mathbb {C})\) be a primitive quantum channel of Kraus rank \(k\). Then there are an integer \(n\) and a word \(K^{(n)}\in K_n\) such that
Let \(R_n\) be the span of the spaces \(K_m\) with \(1\leq m\leq n\). Starting from \(\dim R_1=k\), strict growth continues until \(R_n=M_{d}(\mathbb {C})\); otherwise equality at two consecutive levels would persist and contradict primitivity. Thus \(R_{d^2-k+1}=M_{d}(\mathbb {C})\). Since the identity has nonzero trace, one of the spanning words occurring at a positive level has nonzero trace.
Let \(T:M_{d}(\mathbb {C})\to M_{d}(\mathbb {C})\) be a primitive quantum channel and suppose that one of its Kraus operators, denoted by \(A\), satisfies \(A|\varphi \rangle =\mu |\varphi \rangle \), where \(\varphi \neq 0\) and \(\mu \neq 0\). Then
\(K_{d-1}|\varphi \rangle =\mathbb {C}^d\);
if \(A\) is not invertible, then \(|\varphi \rangle \! \langle \psi |\in K_{d^2-d+1}\) for every \(\psi \in \mathbb {C}^d\).
Part (a) is Theorem 11.3.3. For part (b), decompose \(A\) into its nonzero and zero generalized eigenspaces. If \(r\) is the largest zero Jordan-block size and \(\widetilde d\) is the rank of \(A^d\), strict growth of the rectangular spaces \(A^rK_n\) reaches \(A^rM_{d}(\mathbb {C})\) by level \(d\widetilde d\). Hence \(|\varphi \rangle \! \langle \psi |\in K_{d\widetilde d+r}\). Finally, \(\widetilde d\leq d-r\) and \(r\geq 1\) give \(d\widetilde d+r\leq d^2-d+1\).
Let \(T:M_{d}(\mathbb {C})\to M_{d}(\mathbb {C})\) be a primitive quantum channel of Kraus rank \(k\). Then the minimal threshold \(q\) satisfies
in general, \(q\leq (d^2-k+1)d^2\);
if \(K_1\) contains an invertible element, then \(q\leq d^2-k+1\);
if \(K_1\) contains an element with a nonzero eigenvalue, then \(q\leq d^2\).
For part (2), adjoining an invertible element already in \(K_1\) does not alter any \(K_n\). Left multiplication by that element preserves linear independence, so the dimensions grow strictly from \(k\) until they reach \(d^2\). This gives \(K_{d^2-k+1}=M_{d}(\mathbb {C})\).
For part (1), Lemma 11.4.3 gives a word \(K^{(n)}\) with nonzero trace and \(n\leq d^2-k+1\). It has a nonzero eigenvalue. Regard the length-\(n\) words as the Kraus operators of a blocked family and apply Lemma 11.4.4. The invertible branch uses part (2); in the noninvertible branch the rank-one operators from part (b), followed by the vector spreading in part (a), give \(K_{nd^2}=M_{d}(\mathbb {C})\). Thus \(q\leq nd^2\leq (d^2-k+1)d^2\). Part (3) is the same blocked argument with \(n=1\).
11.5 Wielandt Bound
This section collects exact-word, cumulative-span, augmentation, blocking, complementary-gap, and one-step padding results used by the main quantitative argument earlier in this chapter.
11.6 Exact-word and block-injectivity support
If \(C\in M_{D}(\mathbb {C})\) is nonzero, then
This is the matrix-factorization input used in [ PGVWC07 , Lemma 3 ] .
Choose a nonzero entry \(C_{pq}\). Then every matrix unit \(E_{ij}\) is a scalar multiple of \(E_{ip}CE_{qj}\), so the span in (1) contains the standard matrix basis.
11.7 Cumulative-span and spectral linear algebra
The next two lemmas connect irreducible matrix actions with the cumulative word span used throughout Chapter 11.
A Fitting decomposition of a linear endomorphism \(f:V\to V\) on a finite-dimensional vector space over an algebraically closed field consists of:
\(f\) is nilpotent on the generalized \(0\)-eigenspace,
\(f\) is invertible on each generalized \(\mu \)-eigenspace for \(\mu \neq 0\),
the generalized eigenspaces span \(V\),
the generalized eigenspaces are linearly independent.
Every linear endomorphism on a finite-dimensional vector space over an algebraically closed field admits a Fitting decomposition.
Nilpotency on the zero generalized eigenspace follows from the definition of generalized eigenspaces. Invertibility on nonzero generalized eigenspaces follows because \(f-\mu \) is nilpotent there, so \(f=\mu (1-(1-f/\mu ))\) is invertible. Spanning and independence are standard results for generalized eigenspaces over algebraically closed fields. In [ SPGWC10 ] and [ Wol12 , Lemma 6.3(b) ] , the Jordan normal form is used directly. The argument is phrased in terms of generalized eigenspaces instead.
If \(f\) is nilpotent on a space of dimension \(n\), then \(f^n=0\).
A nilpotent endomorphism on an \(n\)-dimensional space has nilpotency index at most \(n\).
If \(M\in M_{D}(\mathbb {C})\) has \(\operatorname{tr}(M)\neq 0\), then \(M\) has a nonzero eigenvalue \(\mu \neq 0\) and a corresponding eigenvector \(\varphi \neq 0\) satisfying \(M\varphi =\mu \varphi \).
The trace is the sum of the eigenvalues of \(M\), counted with multiplicity, so a nonzero trace gives a nonzero eigenvalue \(\mu \). Choosing a nonzero vector \(\varphi \in \ker (M-\mu \mathbb {1})\) gives \(M\varphi =\mu \varphi \).
11.8 One-step augmentation
11.9 Blocking and fixed-length spanning
Fix a block length \(L\) and regard the words of length \(L\) in a Kraus family \(K\) as a new family \(K^{[L]}\). Evaluation of a blocked word agrees with evaluation of its flattened word, and consequently
If \(L{\gt}0\) and the exact word spans of \(K\) are eventually full, then the exact word spans of \(K^{[L]}\) are eventually full as well.
The evaluation identity follows by induction on the blocked word. Taking spans gives the displayed equality. For eventual fullness, sufficiently large \(n\) also makes \(nL\) exceed the original threshold.
11.10 Complementary-gap consequences
11.11 Identity in the one-step span
In \(M_{2}(\mathbb {C})\), let \(A^0=E_{12}\) and \(A^1=E_{21}\) be the off-diagonal matrix units. Then \(\operatorname{alg}(A)=M_{2}(\mathbb {C})\) and \(T_2(A)=M_{2}(\mathbb {C})\), but the word spans alternate: \(S_n(A)\) contains only off-diagonal matrices for odd \(n\) and only diagonal matrices for even \(n\). Hence \(S_n(A)\neq M_{2}(\mathbb {C})\) for every \(n\), and \(A\) is not normal. The one-step padding condition fails because \(\mathbb {1}\notin S_1(A)=\operatorname{span}_{\mathbb {C}}\{ E_{12},E_{21}\} \).