arXiv:2609.40154
Quantum Černý complexity of binary words
Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen
Abstract
We introduce the quantum Černý complexity $\mathrm{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\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{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 $\mathrm{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 $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.
AI Summary
The paper studies a quantum analogue of reset complexity: for a binary word $w$, $\mathrm{qc}(w)$ is the smallest Hilbert-space dimension admitting two quantum channels and an initial state such that $w$ is the unique shortest word whose channel is constant on all reachable states. The variant $\mathrm{qcp}(w)$ additionally requires a pure reset target. For every nonempty word, it establishes $2\leq\mathrm{qc}(w)\leq\lceil\sqrt{|w|+1}\rceil$, with equality in the upper bound for constant words: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\rceil$. Synchronization is reformulated as a matrix product annihilating the reachable-difference space, of dimension at most $d^2-1$. The upper bound embeds a pattern-matching automaton into channel perturbations around complete depolarization; the constant-word lower bound follows from nilpotency depth. In contrast, $\mathrm{qc}(01^n0)=2$ for all $n\geq1$, using dephasing and a precisely chosen qubit rotation. Thus reset length has no dimension-only bound. For pure targets, a rigidity argument excludes every word of length at least two in dimension two. An explicit qutrit rotation-and-funnel construction establishes $\mathrm{qcp}(01^n0)=3$, with reset holding on all input states. Both complexity functions are computable through real quantifier elimination. The unbounded-length constructions rely on exact parameter coincidences and are generically destroyed by perturbations; parameter precision is not charged as a resource. Open questions include approximate synchronization, typical-word complexity, efficient computation, characterization of dimension-two realizations, and a general square-root upper bound for pure targets.
Error found: The qubit construction's supplied proof does not specify an initial state or prove shortestness and uniqueness, although choosing |0⟩⟨0| and analyzing projection–rotation products repairs the gap. The qubit proof displays an incorrect formula for the nth rotation and reverses its off-diagonal signs, although the final maximally mixed output remains correct. The linearization proof's subspace recurrence fails at k=0, although adding the first-step difference space repairs the argument without changing its finite bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.