Quantum Černý complexity of binary words
Abstract
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.
Related
- Temporal complexity hierarchies in solvable quantum many-body dynamics
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Isometry Groups of Right Invariant Metrics in Geometric Quantum Complexity
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
BibTeX
@misc{lee2026quantum,
title = {{Quantum Černý complexity of binary words}},
author = {Pui Hang Lee and Pui-Yee Lee and Bjørn Kjos-Hanssen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40154},
eprint = {2609.40154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40154},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Černý complexity of binary words
AU - Pui Hang Lee
AU - Pui-Yee Lee
AU - Bjørn Kjos-Hanssen
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40154
UR - https://arxiv.org/abs/2609.40154
AB - 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× 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(0^m)=⌈√(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.
ER -