Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40154

Quantum Černý complexity of binary words

Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen

quant-phcs.DMSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

Related papers

Unbounded length minimal synchronizing words for quantum channels over qutrits

Bjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan

Grudka, Karczewski, Kurzynski, Stempin, Wójcik and Wojcik (2025) constructed quantum channels with synchronizing words of length 3 for qutrits. We extend their result to arbitrarily long minimal synchronizing words, providing a contrast to Černý's conjecture for finite automata.

arXiv:2603.00861•Mar 1, 2026•0 citations

Quantum synchronizing words

Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński +3 more

Abstract Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we investigate whether the concatenation of two non-resetting quantum channels can give rise to a resetting channel. While we formulate the problem for general qudits, the complexity of the setting leads us to focus on particular resetting concatenations for qubits and qutrits. Furthermore, we demonstrate that following the reset, any pure real qutrit state can be closely approximated using the same two non-resetting channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of quantum channels capable of both resetting and preparing arbitrary states.

New Journal of Physics•Oct 23, 2025•1 citation

Quantum Synchronizing Words: Resetting and Preparing Qutrit States

Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński +3 more

Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we show that with only two quantum channels, it is possible to bring an arbitrary qutrit state close to a designated target state. Furthermore, we demonstrate that following this reset, any pure real qutrit state can be closely approximated using the same two channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of universal quantum gates capable of both resetting and preparing arbitrary states.

arXiv:2502.09522•Feb 13, 2025•0 citations

Quantum Computers Speed Up Classical with Probability Zero

Yuri Ozhigov

Let $f$ denote length preserving function on words. A classical algorithm can be considered as $T$ iterated applications of black box representing $f$, beginning with input word $x$ of length $n$. It is proved that if $T=O(2^{n/(7+e)}), e >0$, and $f$ is chosen randomly then with probability 1 every quantum computer requires not less than $T$ evaluations of $f$ to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity $T$ and $f$ chosen randomly with probability 1 every quantum simulation of classical computation requires at least $Ω(\sqrt {T})$ evaluations of $f$.

arXiv:quant-ph/9803064•Mar 24, 1998•13 citations

Every architecture of six two-qubit gates is locally universal on three qubits

Hyunho Cha, Jungwoo Lee

We present the \emph{first} analytical determination of the exact accessible dimension for every fixed architecture of arbitrary two-qubit gates on three qubits. A support word represents which pair of qubits each two-qubit gate acts on, and its reduced length is obtained by merging consecutive gates on the same pair. If the reduced length is $r$, then the set of implementable three-qubit unitaries has accessible dimension $d(w)=\min\{63,9r+9\}$. Consequently, six arbitrary two-qubit gates are \emph{necessary and sufficient for local universality}: every fixed architecture reaches a nonempty open subset of $\mathrm{SU}(8)$ when its reduced length is at least six. The result is stronger than existence of one favorable architecture. Every reduced six-slot support word is locally universal, including the alternating nearest-neighbor line $AB,BC,AB,BC,AB,BC$. The upper bound follows from a standard parameter-counting argument. The matching lower bounds are proved by Jacobian certificates in the Pauli basis. Up to qubit relabeling and reversal, there are $22$ reduced architectures of lengths two through six. For each one, a product of rational Pauli rotations yields a nonzero maximal minor modulo the prime $1{,}000{,}003$. Thus, any obstruction to global universality with six two-qubit gates must go beyond parameter counting, connectivity, and differential rank.

quant-pharXiv:2609.22176•Aug 28, 2026•0 citations

Unbounded Length Minimal Synchronizing Words for Quantum Channels Over Qutrits*

Bjørn Kjos-Hanssen, Swarnalakshmi Lakshmanan

Grudka et al. constructed quantum channels with synchronizing words of length 3 for qutrits. We extend their result to arbitrary long minimal synchronizing words.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•0 citations
We introduce the quantum Černý complexity qc(w)\mathrm{qc}(w)qc(w) of a binary word www: the least dimension ddd for which there exist quantum channels A0,A1A_0,A_1A0​,A1​ on d×dd\times dd×d density matrices and a start state ρ0ρ_0ρ0​ such that www is the unique shortest word whose associated channel is constant on the reachable set. We show that 2≤qc(w)≤⌈∣w∣+1 ⌉2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil2≤qc(w)≤⌈∣w∣+1​⌉ for every nonempty www, a quadratic saving over the classical analogue, and that constant words are extremal: qc(0m)=⌈m+1 ⌉\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceilqc(0m)=⌈m+1​⌉. In contrast, qc(01n0)=2\mathrm{qc}(01^n0)=2qc(01n0)=2 for every n≥1n\ge 1n≥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\mathrm{qc}qc is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant qcp\mathrm{qcp}qcp in which the synchronization target is required to be a pure state. We prove that in dimension 222 no word of length at least 222 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\mathrm{qcp}(01^n0)=3qcp(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\mathrm{qc}qc is computable, by reduction to the first-order theory of the reals.
Abstract Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we investigate whether the concatenation of two non-resetting quantum channels can give rise to a resetting channel. While we formulate the problem for general qudits, the complexity of the setting leads us to focus on particular resetting concatenations for qubits and qutrits. Furthermore, we demonstrate that following the reset, any pure real qutrit state can be closely approximated using the same two non-resetting channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of quantum channels capable of both resetting and preparing arbitrary states.
Synchronizing words in classical automata theory provide a mechanism to reset any state of a deterministic automaton to a specific target state via a carefully chosen finite sequence of transition rules. In this work, we extend the concept of synchronizing words to quantum information theory. Specifically, we show that with only two quantum channels, it is possible to bring an arbitrary qutrit state close to a designated target state. Furthermore, we demonstrate that following this reset, any pure real qutrit state can be closely approximated using the same two channels. These findings establish a quantum analogue of synchronizing words, highlighting their potential applications in constructing minimal sets of universal quantum gates capable of both resetting and preparing arbitrary states.
Let fff denote length preserving function on words. A classical algorithm can be considered as TTT iterated applications of black box representing fff, beginning with input word xxx of length nnn. It is proved that if T=O(2n/(7+e)),e>0T=O(2^{n/(7+e)}), e >0T=O(2n/(7+e)),e>0, and fff is chosen randomly then with probability 1 every quantum computer requires not less than TTT evaluations of fff to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity TTT and fff chosen randomly with probability 1 every quantum simulation of classical computation requires at least Ω(T)Ω(\sqrt {T})Ω(T​) evaluations of fff.
We present the \emph{first} analytical determination of the exact accessible dimension for every fixed architecture of arbitrary two-qubit gates on three qubits. A support word represents which pair of qubits each two-qubit gate acts on, and its reduced length is obtained by merging consecutive gates on the same pair. If the reduced length is rrr, then the set of implementable three-qubit unitaries has accessible dimension d(w)=min⁡{63,9r+9}d(w)=\min\{63,9r+9\}d(w)=min{63,9r+9}. Consequently, six arbitrary two-qubit gates are \emph{necessary and sufficient for local universality}: every fixed architecture reaches a nonempty open subset of SU(8)\mathrm{SU}(8)SU(8) when its reduced length is at least six. The result is stronger than existence of one favorable architecture. Every reduced six-slot support word is locally universal, including the alternating nearest-neighbor line AB,BC,AB,BC,AB,BCAB,BC,AB,BC,AB,BCAB,BC,AB,BC,AB,BC. The upper bound follows from a standard parameter-counting argument. The matching lower bounds are proved by Jacobian certificates in the Pauli basis. Up to qubit relabeling and reversal, there are 222222 reduced architectures of lengths two through six. For each one, a product of rational Pauli rotations yields a nonzero maximal minor modulo the prime 1,000,0031{,}000{,}0031,000,003. Thus, any obstruction to global universality with six two-qubit gates must go beyond parameter counting, connectivity, and differential rank.