Quantum ern'y complexity of binary words

We introduce the quantum Černý complexity qc(w) of a binary word w: the least dimension d for which there exist quantum channels A 0,A 1 on d times 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) sqrt w+1, for every nonempty w, a quadratic saving over the classical analogue, and that constant words are extremal: qc(0 m)= sqrt m+1,. In contrast, qc(01 n0)=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(01 n0)=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.