Source-linked AI summary
Quantum \v{C}ern\'y complexity of binary words
Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen
TL;DR
Classical reset complexity measures a word by the smallest automaton in which it is the unique shortest synchronizing word, motivating a quantum counterpart. The paper linearizes synchronization as matrix-product vanishing and finds that constant words attain the general upper bound while 01^n0 has quantum complexity 2; exact synchronization is fragile under generic perturbations.
Problem
Classical reset complexity measures a word by the smallest automaton in which it is the unique shortest synchronizing word, against the background of the Černý conjecture on reset lengths.
Source: §1 · p. 1Method
Linearization turns synchronization into matrix-product vanishing on an invariant difference space, enabling finite checks of words shorter than the target word.
Source: §2 · p. 2Results
Takeaways & Limitations
For 01^n0, the pure-target variant has complexity 3, witnessed by an explicit qutrit construction with a computational-basis target.
Source: §1 · p. 2Both counter constructions rely on exact coincidences that generic parameter perturbations destroy, so an approximate theory may behave differently.
Source: Fragility · p. 8
Abstract
from arXiv · showhide
We introduce the quantum \v{C}ern\'y 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 $\rho_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 \v{C}ern\'y 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.
1 Introduction
The paper extends machine-based reset complexity to quantum channels, asking for the least dimension in which a binary word is the unique shortest synchronizing word. Its results show that quantum complexity can vary sharply across words, while requiring a pure target changes the outcome for a studied family.
1 Introduction
- Quantum reset complexity asks for the least channel dimension in which a word is the unique shortest word making the channel constant on reachable states.The classical reset complexity instead measures the least automaton state count for which the word is the unique shortest synchronizing word.Source: §1 · p. 1
- For every nonempty word, qc(w) is at least 2, and qc(w) is no greater than qcpure(w).The pure-target variant requires the synchronization target to be a pure state.Source: §1 · p. 2
- Constant words attain the general upper bound, while qc(01^n0)=2 uniformly in n; the pure-target value for this family is 3.The qubit construction uses a rotation angle to count the run of 1s; the pure-target result is witnessed by a qutrit construction.Source: §1 · p. 2
2 Linearization and the general upper bound
The section recasts synchronization as a linear-algebraic condition on differences between reachable states. This viewpoint supports constructions, a computability result, and a quadratic saving in dimension from the available traceless directions.
2 Linearization and the general upper bound
- A word synchronizes exactly when its linear action vanishes on the invariant span of differences between reachable states.That span can be computed from reachable states using words of length at most d²−1.Source: §2 · p. 2
- qc and qcpure are computable by expressing fixed-dimension instances in the first-order theory of the reals and applying Tarski’s decision procedure.The decision statement quantifies over finitely many words of length at most |w|.Source: §2 · p. 2
- The prefix-matching automaton for w can be represented in traceless directions, with a sink at the origin, to make w the unique shortest synchronizing word.The construction uses linearly independent traceless Hermitians and channel maps obtained through a depolarizing perturbation.Source: §2 · p. 3
- The d²−1-dimensional difference space yields a quadratic saving in the general upper bound, and a classical channel construction gives qcpure(w) ≤ |w| + 1.The pure target in that construction is |n⟩⟨n|.Source: §2 · p. 3
3 Constant words are extremal
Constant words have maximal quantum complexity for their length: their complexity matches the general upper bound. The lower bound follows from nilpotence, and a matching construction uses a nilpotent map to make 0^m uniquely shortest.
3 Constant words are extremal
- qc(0^m)=⌈√m + 1⌉, so the constant word attains the general upper bound and is most complex among words of its length.The theorem states the bound as ⌈√m + 1⌉.Source: §3 · p. 3
- If 0^m is uniquely shortest, the action of 0 on the difference space must be nilpotent of index exactly m, forcing m ≤ d²−1.Otherwise 0^(m−1) would already synchronize.Source: §3 · p. 4
- A nilpotent map on an m-dimensional subspace, paired with the identity action for 1, makes synchronization equivalent to containing at least m zeros.The unique shortest word with that property is 0^m.Source: §3 · p. 4
4 A phase counter: qc(01n0) = 2
A single qubit synchronizes 01^n0 for every n by using a rotation angle as a counter. This yields arbitrarily long unique shortest synchronizing words in fixed dimension.
4 A phase counter: qc(01n0) = 2
- The word 01^n0 is stated to be synchronizing, with 2I as its synchronizing state; the argument considers arbitrary density states reachable by operators A0 and A1.Source: §4 · p. 5
- For each fixed dimension d≥2, unique shortest synchronizing words can have unbounded length, so no dimension-only reset-length bound exists.This rules out a quantum analogue of the Černý function.Source: §4 · p. 5
- A continuous rotation angle acts as a counter, detecting exactly n consecutive 1s through a single orthogonality coincidence.The qubit's channel acts as an affine map on the Bloch ball, while A0 removes off-diagonal entries.Source: §4 · pp. 4–5
- Unlike 01^n0, synchronizing 0^m requires the m-th application of one map and forces a nilpotent chain of length m.The continuous parameter counter is unavailable for this constant-word case.Source: §4 · p. 5
5 Pure targets: qcpure(01n0) = 3
For every n ≥ 1, the pure-target complexity of 01^n0 is 3, achieved by a qutrit construction that synchronizes every input to a basis state. Dimension 2 cannot realize a unique shortest pure-target synchronizing word of length at least 2.
5 Pure targets: qcpure(01n0) = 3
- No dimension-2 instance has a unique shortest pure-target synchronizing word of length at least 2.Consequently, the pure-target words realizable in dimension 2 are exactly {0, 1}.Source: §5 · p. 5
- In dimension 3, a non-constant channel can collapse a proper face of the state space, while a coherent rotation steers reachable states onto that face.This face-collapse mechanism underlies the qutrit construction.Source: §5 · p. 6
- qcpure(01^n0)=3, with target |e2⟩⟨e2| and synchronization on every 3×3 input state.Theorem 5.2 gives both the exact dimension and a universal reset.Source: §5 · p. 6
- The qutrit construction rotates the state after the first 0 so the final 0 funnels its support to |e2⟩⟨e2|, for every input state.After A0, the support lies in span(e2,e3); U^n moves it into span(e1,e3), where the final A0 is constant.Source: §5 · p. 6
- Uniqueness follows because competing words preserve distinct reachable parameters unless they contain 01^j0 with j≥n, whose shortest possibility is 01^n0.The proof rules out shorter competitors and shows equality in the length bound only for 01^n0.Source: §5 · pp. 6–7
- The diagonal action of A0 alone cycles levels 2 and 3, so the coherent rotation is essential to make the qutrit construction synchronize.The rotation transfers level-2 population back to level 1 before the funnel closes.Source: §5 · p. 7
6 Discussion and open problems
The discussion frames qc as a dimension-based description measure with counterintuitive costs, and notes that its exact synchronization constructions are fragile. It leaves open questions about qc’s distribution, efficient computation, pure-target bounds, and approximate synchronization.
What does qc measure?
- Constant words 0^m are extremal for qc, whereas patterned words 01^n0 have qc=2, making qc anti-correlated with intuitive descriptive complexity.The discussion attributes the low cost of 01^n0 to a continuous rotation angle that encodes the run length.Source: What does qc measure? · p. 7
Fragility
- Under a generic parameter perturbation, neither counter construction synchronizes exactly; in the qutrit construction the funnel is robust but the steering coincidence is measure-zero.The authors propose studying an approximate definition separately.Source: Fragility · p. 8
Open problems
- Open questions include whether qc(01101001)=2, which words have qc=2, and whether qc can be computed in polynomial time or belongs to NP or ∃R.The stated bound for qc(01101001) is at most 3.Source: Open problems · p. 8
- The authors ask whether qc=2 for almost all uniformly random words and whether 0^m, its reversal, and its complementations are the only large-length maximizers.The classical counting result cited in the discussion gives rc(w) ≳ m/(2 log m) for most words.Source: Open problems · p. 8
- A general quadratic-type upper bound for qcpure remains open; the proof of Theorem 2.4 does not adapt because it places the target at the maximally mixed state.Source: Open problems · p. 8
- The discussion calls for an ε-approximate theory to determine which words remain expensive and whether an approximate analogue of Corollary 4.2 holds.Source: Open problems · p. 8