Unbounded length minimal synchronizing words for quantum channels over qutrits

Bjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan · 2026

Read Unbounded length minimal synchronizing words for quantum channels over qutrits by Bjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00861.txt.

Introduction

Kjos-Hanssen and Lakshmanan extend a construction of quantum channels with synchronizing words of length 3 for qutrits. They build qutrit channels whose minimal synchronizing words are arbitrarily long, pushing the length without bound. The result contrasts with Černý's conjecture for finite automata, which bounds synchronizing word length, showing quantum channels behave differently from classical automata.

Catalog record

CREATORBjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13092
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.00861

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unbounded length minimal synchronizing words for quantum channels over qutrits* Thanks: This work was partially supported by a grant from the Simons Foundation (#704836 to Bjørn Kjos-Hanssen). Bjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan Abstract Grudka, Karczewski, Kurzynski, Stempin, Wójcik and Wojcik (2025) constructed quantum channels with synchronizing words of length 3 for qutrits. We extend their result to arbitrarily long minimal synchronizing words, providing a contrast to Černý’s conjecture for finite automata. I Introduction Grudka et al. [ 2 ] . constructed quantum channels with synchronizing words of length 3 for qutrits. We extend their result to arbitrary long minimal synchronizing words. Definition 1 . A deterministic automaton (DA) M consists of a set of states Q , an alphabet \Sigma , a start state q_{0} , a set of accepting states F\subseteq Q , and a transition function \delta:Q\times\Sigma\to Q . If Q and \Sigma are finite sets then M is a deterministic finite automaton (DFA). Let \lambda denote the empty word and let \Sigma^{*} be the set of finite words over \Sigma . The function \delta induces a map \delta^{*}:Q\times\Sigma^{*}\to Q by \delta^{*}(q,\lambda)=q,\quad\delta^{*}(q,wa)=\delta(\delta^{*}(q,w),a) where w\in\Sigma^{*} and a\in\Sigma^{*} . Definition 2 . A synchronizing word in a DFA over an alphabet \{A,B\} is a word w\in\{A,B\}^{*} such that \delta^{*}(q,w)=\delta^{*}(r,w) for all states r and q . Our study is motivated by Černý’s conjecture [ 1 ] on the shortest synchronizing words in DFAs. Ján Černý demonstrated that for some DFAs with q many states, the shortest synchronizing word has length (q-1)^{2} . The longstanding Černý’s conjecture asserts that whenever a DFA has a synchronizing word, it has one of length at most this bound. Our result here shows that if we count only basis states (i.e., dimension) then in a quantum setting Černý’s conjecture fails. The reason is simply that there is no finite upper bound on the minimal synchronizing word length at all, as a function of dimension. We prove in Theorem 11 that for each l\in\mathbb{N} there is a quantum channel of qutrits (hence having q=3 basis states) in which there is a synchronizing word, but none of length at most l . II Construction Our construction is a modification of one due to Grudka et al. Let A_{1}=\begin{pmatrix}0&0&0\\ 1&0&0\\ 0&0&0\end{pmatrix},\quad A_{2}=\begin{pmatrix}0&0&0\\ 0&0&-1\\ 0&1&0\end{pmatrix} and define a Kraus operator A by A(\rho)=A_{1}\rho A_{1}^{*}+A_{2}\rho A_{2}^{*} . For each positive integer n , let B=B_{n}=\begin{pmatrix}\cos\theta&-\sin\theta&0\\ \sin\theta&\cos\theta&0\\ 0&0&1\end{pmatrix} where \theta=\pi/(2n) , and define the Kraus operator B by B(\rho)=B\rho B^{*} . Let e_{1},e_{2},e_{3} be the standard basis vectors for \mathbb{C}^{3} , so that for example \ket{e_{2}}\bra{e_{2}}=\begin{pmatrix}0&0&0\\ 0&1&0\\ 0&0&0\end{pmatrix} Definition 3 . For any positive integer n , \mathscr{M}_{n} is the DA whose states are density matrices over \mathbb{C}^{3} , whose alphabet is \{A,B_{n}\} , with transition function \delta(\rho,C)=C(\rho) for C\in\{A,B_{n}\} . The countable subautomaton \mathscr{M}_{n}^{\prime} is identical to \mathscr{M}_{n} except that its set of states is Q=\{\delta^{*}(\ket{e_{1}}\bra{e_{1}},w);\,w\in\{A,B_{n}\}^{*}\} i.e., density matrices reachable from \ket{e_{1}}\bra{e_{1}} using A and B_{n} . Notice that both A and B are quantum channels, in particular trace-preserving and satisfying \sum A_{i}^{*}A_{i}=\mathbbm{1}=B^{*}B. (1) If A and B were both injective they could not generate a synchronizing word. For example, \mathscr{M}^{\prime}_{1} in its entirety looks like this: \textstyle{{\ket{e_{3}}\bra{e_{3}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{A} \scriptstyle{B} \textstyle{{\ket{e_{2}}\bra{e_{2}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \textstyle{{\ket{e_{1}}\bra{e_{1}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{A} It is verifiable by inspection that the word ABA is synchronizing, and the non-injectivity of A is crucial for this to happen. (See Figure 1 for a finite part of the infinite, and more complicated, DA \mathscr{M}_{2}^{\prime} .) The fact that ( 1 ) can be maintained is a surprising next best thing after injectivity. III Main results Let a positive integer l be given. Our strategy is simple: If we take the angle \theta very small compared to l , then the operator B is close to the identity I , hence any word of length l or less is approximately just a power A^{p} . As A permutes \ket{e_{2}}\bra{e_{2}} and \ket{e_{3}}\bra{e_{3}} , it follows that there is no synchronizing word of length l or less. To speak precisely about B being close to I we use the trace distance. Definition 4 . The trace distance between \rho and \sigma is given by D_{\mathrm{tr}}(\rho,\sigma)=\tfrac{1}{2}\,\left\lVert\rho-\sigma\right\rVert_{1}=\tfrac{1}{2}\operatorname{tr}\!\big(\sqrt{(\rho-\sigma)^{2}}\big) . We recall the well-known Lemma 5 . Lemma 5 . For any quantum channel \Phi , D_{\mathrm{tr}}(\Phi(\rho),\Phi(\sigma))\leq D_{\mathrm{tr}}(\rho,\sigma). Lemma 6 (Hölder inequality for Schatten norms [ MR2978290 ] (5.6)) . Let A,B be complex (or real) matrices, and let 1\leq p,q,r\leq\infty satisfy \frac{1}{r}\;\leq\;\frac{1}{p}+\frac{1}{q}. Then \|AB\|_{r}\;\leq\;\|A\|_{p}\,\|B\|_{q}, where \|\cdot\|_{p} denotes the Schatten p -norm, \|X\|_{p}=\begin{cases}\bigl(\operatorname{tr}[(X^{*}X)^{p/2}]\bigr)^{1/p},&1\leq p<\infty,\\[6.0pt] \max_{i}s_{i}(X),&p=\infty,\end{cases} and s_{i}(X) are the singular values of X . In particular, for p=q=\infty and r=1 , \|AB\|_{1}\leq\|A\|_{\infty}\,\|B\|_{1}. We now obtain a trace-distance bound for a rank-one channel close to the identity. Lemma 7 . Let B be a 3\times 3 real matrix, and define a quantum channel \Phi(\rho)=B\rho B^{T}. Assume that every entry of B differs from the identity by at most \epsilon\leq 2/9 : B=I+E,\qquad|E_{ij}|\leq\epsilon. Then D_{\mathrm{tr}}(\rho,\Phi(\rho))\leq 4\epsilon . Proof. We would like to bound the trace distance D_{\mathrm{tr}}(\rho,\Phi(\rho))=\tfrac{1}{2}\|\Phi(\rho)-\rho\|_{1}=\tfrac{1}{2}\|B\rho B^{T}-\rho\|_{1}. Write B\rho B^{T}-\rho=(B-I)\rho B^{T}+\rho(B^{T}-I). Applying the triangle inequality and Lemma 6 \|XYZ\|_{1}\leq\|XY\|_{1}\|Z\|_{\infty}\leq\|X\|_{\infty}\,\|Y\|_{1}\,\|Z\|_{\infty}, we get \|B\rho B^{T}-\rho\|_{1}\leq\|B-I\|_{\infty}\,\|\rho\|_{1}\,\|B\|_{\infty}+\|\rho\|_{1}\,\|B^{T}-I\|_{\infty}. Since \|\rho\|_{1}=\operatorname{tr}\rho=1 and \|B^{T}-I\|_{\infty}=\|B-I\|_{\infty} , \|B\rho B^{T}-\rho\|_{1}\leq\|B-I\|_{\infty}\,(\|B\|_{\infty}+1). (2) For a 3\times 3 matrix, the Frobenius norm satisfies \|M\|_{\infty}\leq\|M\|_{F}=\sqrt{\sum_{i,j}|M_{ij}|^{2}}\leq 3\max_{i,j}|M_{ij}|. Hence, using |E_{ij}|\leq\epsilon , \|B-I\|_{\infty}=\|E\|_{\infty}\leq\|E\|_{F}\leq 3\epsilon. Also, \|B\|_{\infty}\leq\|I\|_{\infty}+\|E\|_{\infty}\leq 1+3\epsilon. Substituting into ( 2 ) gives \|B\rho B^{T}-\rho\|_{1}\leq(3\epsilon)\bigl(1+1+3\epsilon\bigr)=3\epsilon(2+3\epsilon). Finally, D_{\mathrm{tr}}(\rho,\Phi(\rho))=\tfrac{1}{2}\|B\rho B^{T}-\rho\|_{1}\leq 3\epsilon+\tfrac{9}{2}\epsilon^{2}\leq 4\epsilon.\qed Lemma 8 . For our choice of B=B_{n} , the values |E_{ij}| in Lemma 7 are bounded by |\theta| . Proof. These values are 0, \cos\theta-1 , and \pm\sin\theta , and we have |\sin\theta|\leq|\theta| and |\cos\theta-1|\leq|\theta| . ∎ Lemma 9 . If D_{\mathrm{tr}}(B(\rho),\rho)\leq\delta for all \rho then for all integers s\geq 0 and all \rho , D_{\mathrm{tr}}(B^{s}(\rho),\rho)\leq s\cdot\delta . Proof. For s=0 , D_{\mathrm{tr}}(B^{0}(\rho),\rho)=D_{\mathrm{tr}}(\rho,\rho)=0 . Inductively, \displaystyle D_{\mathrm{tr}}(B^{s+1}(\rho),\rho) \displaystyle\leq D_{\mathrm{tr}}(B^{s+1}(\rho),B^{s}(\rho))+D_{\mathrm{tr}}(B^{s},\rho) \displaystyle\leq\delta+s\cdot\delta=(s+1)\cdot\delta.\qed Lemma 10 . If D_{\mathrm{tr}}(B(\rho),\rho)\leq\delta for all \rho then D_{\mathrm{tr}}\left(\left(\prod_{i=1}^{t}A^{a_{i}}B^{b_{i}}\right)\rho,\,A^{\sum_{i}a_{i}}\rho\right)\leq\delta\sum_{i}b_{i}. Proof. By Lemma 5 and Lemma 9 , \left(\prod_{i=1}^{t}A^{a_{i}}B^{b_{i}}\right)\rho=A^{a_{1}}B^{b_{1}}\left(\prod_{i=2}^{t}A^{a_{i}}B^{b_{i}}\right)\rho is within b_{1}\cdot\delta of A^{a_{1}}\left(\prod_{i=2}^{t}A^{a_{i}}B^{b_{i}}\right)\rho, so by induction we are done. ∎ Theorem 11 . For each l there is an n such that there is no synchronizing word in \mathscr{M}_{n} or \mathscr{M}_{n}^{\prime} of length at most l over the alphabet \{A,B_{n}\} . Proof. Let \epsilon<1/2 and \epsilon^{\prime}=\frac{\epsilon}{4l} . Choose |\theta|\leq\epsilon^{\prime} . Since \theta=\pi/(2n) this amounts to choosing n\geq\pi/(2\epsilon^{\prime}) . Let w be a purported synchronizing word of length l or less. We may assume w has length exactly l since for any word v , the concatenated word vw is synchronizing as well. By Lemma 10 with \rho=\ket{e_{2}}\bra{e_{2}} , there is a certain j with \displaystyle D_{\mathrm{tr}}(w(\ket{e_{2}}\bra{e_{2}}),A^{j}(\ket{e_{2}}\bra{e_{2}}))\leq\epsilon and \displaystyle D_{\mathrm{tr}}(w(\ket{e_{3}}\bra{e_{3}}),A^{j}(\ket{e_{3}}\bra{e_{3}}))\leq\epsilon. Since w is synchronizing, w(\ket{e_{2}}\bra{e_{2}})=w(\ket{e_{3}}\bra{e_{3}}) . However, A permutes \ket{e_{2}}\bra{e_{2}} and \ket{e_{3}}\bra{e_{3}} , so this is impossible: \displaystyle 1 \displaystyle=D_{\mathrm{tr}}(\ket{e_{2}}\bra{e_{2}},\ket{e_{3}}\bra{e_{3}}) \displaystyle=D_{\mathrm{tr}}(A^{j}(\ket{e_{2}}\bra{e_{2}}),A^{j}(\ket{e_{3}}\bra{e_{3}}) \displaystyle\leq D_{\mathrm{tr}}(A^{j}(\ket{e_{2}}\bra{e_{2}}),w(\ket{e_{2}}\bra{e_{2}}) \displaystyle+D_{\mathrm{tr}}(w(\ket{e_{2}}\bra{e_{2}}),A^{j}(\ket{e_{3}}\bra{e_{3}}) \displaystyle\leq 2\epsilon<1.\qed Lemma 12 . For all positive integers n , the word AB^{n}_{n}A is synchronizing in \mathscr{M}_{n} and in \mathscr{M}_{n}^{\prime} and maps all states to \ket{e_{2}}\bra{e_{2}} . Proof. The matrix B^{n}_{n} is independent of n and was called B by Grudka et al. [ 2 ] who proved that ABA is synchronizing; see their equation (73). ∎ \textstyle{{\begin{pmatrix}3&3&0\\ 3&3&0\\ 0&0&2\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \textstyle{{\begin{pmatrix}3&0&0\\ 0&0&0\\ 0&0&1\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \textstyle{{\begin{pmatrix}1&1&0\\ 1&1&0\\ 0&0&2\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{A} \scriptstyle{B} \textstyle{{\begin{pmatrix}1&0&0\\ 0&0&0\\ 0&0&1\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \scriptstyle{A} \textstyle{{\begin{pmatrix}1&1&0\\ 1&1&0\\ 0&0&0\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{A} \scriptstyle{B} \textstyle{{\ket{e_{1}}\bra{e_{1}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \scriptstyle{A} \textstyle{{\ket{e_{2}}\bra{e_{2}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{A} \scriptstyle{B} \textstyle{{\begin{pmatrix}1&-1&0\\ -1&1&0\\ 0&0&0\end{pmatrix}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{B} \scriptstyle{A} \textstyle{{\ket{e_{3}}\bra{e_{3}}}}

Read the complete text