{"id":"arxiv/2609.40154","url":"https://arxiv.org/abs/2609.40154","tags":["quant-ph","cs.DM"],"score":0,"title":"Quantum Černý complexity of binary words","domain":"quant-ph","source":"arxiv","authors":["Pui Hang Lee","Pui-Yee Lee","Bjørn Kjos-Hanssen"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}