Quantum / CONCEPT

The Thue-Morse prefix 01101001 needs more than one qubit

Lee, Lee and Kjos-Hanssen (arXiv:2609.40154) define the quantum Cerny complexity qc(w) of a binary word w as the least dimension d for which two quantum channels on d x d density matrices and a start state make w the unique shortest synchronizing word, and conjecture that the Thue-Morse prefix 01101001 has qc = 2. No qubit instance has this word as its unique shortest synchronizing word, so the conjecture fails. Combined with the authors' upper bound qc(w) <= 3, which is proved in the paper and not formalized here, the value is 3.