Unbounded length minimal synchronizing words for quantum channels over qutrits

This paper extends previous findings on qutrit quantum channels by demonstrating the existence of channels with arbitrarily long minimal synchronizing words, thereby contrasting with the bounds suggested by Černý's conjecture for finite automata.

The Gist

The Big Picture: A Quantum "Reset Button"

Imagine you have a complex machine with many different settings. In the world of classical computers (like the ones we use every day), there is a famous idea called Černý's Conjecture. It suggests that no matter how complicated your machine is, there is always a short, specific sequence of buttons you can press to force the machine into one single, known "reset" state.

Think of it like a combination lock. Even if the lock has thousands of possible positions, the theory says there's a short code (like "Left-Right-Left") that will always snap the lock open, regardless of where it started.

This paper asks a bold question: Does this rule hold true for Quantum Computers?

The authors, Bjørn Kjos-Hanssen and Swarnalakshmi Lakshmanan, say No. They prove that for quantum machines (specifically those using "qutrits," which are 3-state quantum bits), you can build a machine where the "reset code" can be arbitrarily long. There is no maximum limit. If you want a machine that requires a reset code longer than the distance to the moon, they can build it.

---

The Characters in Our Story

To understand how they did this, let's meet the two "operators" (or buttons) in their quantum machine:

1. The Shuffler (Operator A): Imagine a card dealer who swaps two specific cards (let's call them Card 2 and Card 3) but leaves the third card (Card 1) alone. If you press "A," the cards swap places. If you press "A" again, they swap back. It's a perfect, predictable shuffle.
2. The Nudge (Operator B): Imagine a very gentle wind. If the wind is strong, it blows the cards around wildly. But in this experiment, the authors make the wind extremely weak. It barely moves the cards at all. It's almost like doing nothing (the "Identity" operation).

The Magic Trick: How They Break the Rule

The authors' strategy is a game of "hide and seek" with time.

1. The Setup: They build a quantum machine where the "Nudge" (Operator B) is so weak that pressing it once barely changes anything.
2. The Trap: They ask: "What is the shortest code to reset this machine?"
3. The Problem: To reset the machine, you usually need to mix the cards up and then line them up.
   • If you press the "Shuffler" (A) too many times, the cards just keep swapping back and forth.
   • If you press the "Nudge" (B) a few times, it's too weak to actually move the cards into the right position.
   • To get the cards to line up, you have to press the "Nudge" many, many times to build up enough force to overcome the "Shuffler's" swapping.

The Analogy:
Imagine trying to push a heavy boulder up a hill.

• Operator A is a person who keeps kicking the boulder back down the hill every time it moves up.
• Operator B is a tiny ant pushing the boulder up.
• If the ant is really tiny (very weak), it might take the ant one million steps just to move the boulder one inch.
• If you only allow the ant to take 10 steps (a short word), it will never reach the top. The boulder will never reset.
• The authors proved that by making the ant smaller and smaller, they can force the "reset" to take as many steps as they want.

The Mathematical Proof (Simplified)

The paper uses a concept called Trace Distance. Think of this as a "ruler" that measures how different two states are.

• If two states are identical, the distance is 0.
• If they are completely different, the distance is large.

The authors showed that:

1. If you use a very weak "Nudge" (small angle $\theta$), the machine barely changes after a few steps.
2. Because the machine barely changes, a short code (length $l$) cannot possibly force the machine into a single state. It's like trying to clean a messy room with a single swipe of a feather duster; it won't work.
3. However, they also proved that if you wait long enough (specifically, a word like $A B^n A$), the "Nudge" eventually builds up enough power to overcome the "Shuffler" and reset the machine to a specific state.

Why This Matters

This is a big deal because it shatters the expectation that quantum systems behave like classical ones.

• Classical World: There is a "speed limit" on how long a reset code needs to be.
• Quantum World: There is no speed limit. You can design a quantum system where the reset code is longer than the age of the universe, simply by making the system's "nudge" weaker.

The Conclusion

The paper concludes that Černý's Conjecture fails in the quantum world. While classical automata have a predictable maximum length for their reset codes, quantum channels (specifically for qutrits) can be constructed to require reset codes of any length you desire.

It's a reminder that in the quantum realm, things can be much more stubborn and complex than our everyday intuition suggests. You can't just assume a short code will fix everything; sometimes, you might need a code longer than the stars in the sky.

Technical Summary

1. Problem Statement

The paper addresses the concept of synchronizing words in the context of quantum channels, specifically contrasting them with the classical theory of deterministic finite automata (DFA).

• Classical Context: In classical automata theory, a synchronizing word is a sequence of inputs that maps all possible states of a DFA to a single specific state, regardless of the starting state. Černý's Conjecture posits that for any DFA with $q$ states that admits a synchronizing word, there exists one with a length of at most $(q-1)^2$.
• Quantum Context: The authors investigate whether a similar bound exists for quantum channels acting on qutrits (3-dimensional quantum systems). Previous work by Grudka et al. (2025) demonstrated the existence of quantum channels with synchronizing words of length 3.
• Core Question: Is there a finite upper bound on the length of the minimal synchronizing word for quantum channels as a function of the system's dimension (number of basis states)? The authors aim to prove that, unlike in the classical case, no such finite upper bound exists for quantum channels, even when the dimension is fixed at $q=3$.

2. Methodology

The authors construct a family of quantum channels (specifically, deterministic automata where states are density matrices) to demonstrate that minimal synchronizing words can be arbitrarily long.

Construction of the Quantum Channel

The construction modifies a model by Grudka et al. using two Kraus operators, $A$ and $B_n$, acting on the space of $3 \times 3$ density matrices ($\mathbb{C}^3$):

1. Operator $A$: Defined by two Kraus matrices $A_1$ and $A_2$.
   $$A(\rho) = A_1 \rho A_1^* + A_2 \rho A_2^*$$
   This operator is non-injective and acts as a permutation on specific basis states (specifically swapping $|e_2\rangle\langle e_2|$ and $|e_3\rangle\langle e_3|$ while mapping $|e_1\rangle\langle e_1|$ to $|e_3\rangle\langle e_3|$).
2. Operator $B_n$: Defined by a single unitary matrix $B_n$ (a rotation in the $xy$-plane of the Bloch sphere representation):
   $$B_n = \begin{pmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{pmatrix}$$
   where $\theta = \frac{\pi}{2n}$. The channel is $B_n(\rho) = B_n \rho B_n^*$.
3. The Automaton $M_n$: The states are density matrices reachable from an initial state $|e_1\rangle\langle e_1|$ using the alphabet $\{A, B_n\}$.

Analytical Approach

To prove that no short synchronizing word exists, the authors employ Trace Distance ($D_{tr}$) as a metric for the distinguishability of quantum states.

• Approximation Strategy: They show that if the rotation angle $\theta$ is sufficiently small (by choosing a large $n$), the operator $B_n$ is arbitrarily close to the identity matrix $I$.
• Perturbation Bounds: Using the Hölder inequality for Schatten norms and properties of the trace distance, they derive a bound (Lemma 7) showing that for a channel $\Phi(\rho) = B\rho B^T$ close to identity, the trace distance $D_{tr}(\rho, \Phi(\rho))$ is bounded by $4\epsilon$, where $\epsilon$ represents the deviation of matrix entries from the identity.
• Inductive Accumulation: They prove that applying a sequence of $B_n$ operators accumulates error linearly (Lemma 9). Consequently, any word of length $l$ composed of $A$ and $B_n$ acts approximately like a power of $A$ (i.e., $A^k$), with an error proportional to the number of $B_n$ applications.

3. Key Contributions and Results

Theorem 11: Unbounded Minimal Length

The central result of the paper is Theorem 11, which states:

For every positive integer $l$, there exists an integer $n$ such that the quantum channel $M_n$ (over qutrits) possesses a synchronizing word, but no synchronizing word of length $\le l$ exists.

Proof Logic:

1. Assume a synchronizing word $w$ of length $\le l$ exists.
2. Because $B_n$ is close to identity, $w$ acts approximately as $A^j$ for some integer $j$.
3. The operator $A$ permutes the states $|e_2\rangle\langle e_2|$ and $|e_3\rangle\langle e_3|$. Therefore, $A^j$ maps these two distinct states to distinct states (or swaps them), maintaining a trace distance of 1 between them.
4. However, if $w$ were truly synchronizing, it would map both states to the same final state, implying a trace distance of 0.
5. By choosing $n$ large enough (making $\theta$ small), the accumulated error from the $B_n$ components is kept below $0.5$. This creates a contradiction: the distance between the images of the two states must be close to 1 (due to $A$) but also close to 0 (due to synchronization).
6. Thus, no such short word $w$ can exist.

Existence of Synchronizing Words

While minimal words are unbounded, the authors confirm (Lemma 12) that a synchronizing word does exist for any $n$. Specifically, the word $A B_n^n A$ is synchronizing and maps all states to $|e_2\rangle\langle e_2|$. This proves the system is synchronizable, but the minimal length depends on $n$ and can be made arbitrarily large.

4. Significance

• Refutation of a Quantum Analogue to Černý's Conjecture: The paper demonstrates that Černý's conjecture (or any finite bound based solely on dimension) fails in the quantum setting. In classical DFAs, the dimension (number of states) strictly limits the length of the minimal synchronizing word. In quantum channels, even with a fixed dimension of 3 (qutrits), the minimal synchronizing word length is unbounded.
• Role of Non-Injectivity: The construction highlights that the non-injectivity of the operator $A$ is crucial for synchronization. If all operators were injective, synchronization would be impossible. The "near-identity" behavior of $B_n$ allows the system to "delay" the synchronization effect of $A$ indefinitely.
• Theoretical Implications: This work deepens the understanding of control theory in quantum systems, showing that quantum channels can exhibit behaviors fundamentally different from their classical finite-state counterparts regarding reachability and synchronization.

5. Future Directions

The authors conclude by posing two open questions:

1. Do similar unbounded results hold for qubits (2-dimensional systems) instead of qutrits?
2. Can such constructions be achieved where both operators are unital (preserving the identity operator), which is a stricter condition often relevant in physical implementations?