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.
We introduce the quantum Černý complexity qc(w) of a binary word w: the least dimension d for which there exist quantum channels A0,A1 on d×d density matrices and a start state ρ0 such that w is the unique shortest word whose associated channel is constant on the reachable set. We show that 2≤qc(w)≤⌈∣w∣+1⌉ for every nonempty w, a quadratic saving over the classical analogue, and that constant words are extremal: qc(0m)=⌈m+1⌉. In contrast, qc(01n0)=2 for every n≥1, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and qc is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant qcp in which the synchronization target is required to be a pure state. We prove that in dimension 2 no word of length at least 2 can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving qcp(01n0)=3 with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that qc is computable, by reduction to the first-order theory of the reals.
Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we show that with only two quantum channels, it is possible to bring an arbitrary qutrit state close to a designated target state. Furthermore, we demonstrate that following this reset, any pure real qutrit state can be closely approximated using the same two channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of universal quantum gates capable of both resetting and preparing arbitrary states.
Abstract Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we investigate whether the concatenation of two non-resetting quantum channels can give rise to a resetting channel. While we formulate the problem for general qudits, the complexity of the setting leads us to focus on particular resetting concatenations for qubits and qutrits. Furthermore, we demonstrate that following the reset, any pure real qutrit state can be closely approximated using the same two non-resetting channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of quantum channels capable of both resetting and preparing arbitrary states.
In this paper, we present new families of quantum channels for which corresponding minimum output Rényi p-entropy is not additive. Our manuscript is motivated by the results of Grudka et al. and we focus on channels characterized by both extensions and subspaces of the antisymmetric subspace inCd⊗Cd, which exhibit additivity breaking forp>2.