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.

AI Summary

The paper studies a quantum analogue of reset complexity: for a binary word $w$, $\mathrm{qc}(w)$ is the smallest Hilbert-space dimension admitting two quantum channels and an initial state such that $w$ is the unique shortest word whose channel is constant on all reachable states. The variant $\mathrm{qcp}(w)$ additionally requires a pure reset target. For every nonempty word, it establishes $2\leq\mathrm{qc}(w)\leq\lceil\sqrt{|w|+1}\rceil$, with equality in the upper bound for constant words: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\rceil$. Synchronization is reformulated as a matrix product annihilating the reachable-difference space, of dimension at most $d^2-1$. The upper bound embeds a pattern-matching automaton into channel perturbations around complete depolarization; the constant-word lower bound follows from nilpotency depth. In contrast, $\mathrm{qc}(01^n0)=2$ for all $n\geq1$, using dephasing and a precisely chosen qubit rotation. Thus reset length has no dimension-only bound. For pure targets, a rigidity argument excludes every word of length at least two in dimension two. An explicit qutrit rotation-and-funnel construction establishes $\mathrm{qcp}(01^n0)=3$, with reset holding on all input states. Both complexity functions are computable through real quantifier elimination. The unbounded-length constructions rely on exact parameter coincidences and are generically destroyed by perturbations; parameter precision is not charged as a resource. Open questions include approximate synchronization, typical-word complexity, efficient computation, characterization of dimension-two realizations, and a general square-root upper bound for pure targets.

Some signs of AI-generated textOverclaimsStrong assumptionsPossible error

Error found: The qubit construction's supplied proof does not specify an initial state or prove shortestness and uniqueness, although choosing |0⟩⟨0| and analyzing projection–rotation products repairs the gap. The qubit proof displays an incorrect formula for the nth rotation and reverses its off-diagonal signs, although the final maximally mixed output remains correct. The linearization proof's subspace recurrence fails at k=0, although adding the first-step difference space repairs the argument without changing its finite bound.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography

Arash Atashpendar

From the output produced by a memoryless deletion channel with a uniformly random input of known length $n$, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length $m$. We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings $\texttt{000}\ldots$, $\texttt{111}\ldots$ and maximized by the alternating strings $\texttt{0101}\ldots$, $\texttt{1010}\ldots$. We present related combinatorial theorems involving binary (sub/super)-sequences and prove the minimal entropy conjecture for single and double deletions using clustering techniques. We then prove the minimization conjecture in the asymptotic limit using results from hidden word statistics by showing how the analytic-combinatorial methods of Flajolet, Szpankowski and Vallée, relying on generating functions, can be applied to resolve the case of fixed output length and $n\rightarrow\infty$. Next, we revisit the notion of deniability in quantum key exchange (QKE). We introduce and formalize the notion of coercer-deniable QKE. We then establish a connection between covert communication and deniability to propose DC-QKE, a simple and provably secure construction for coercer-deniable QKE. We relate deniability to fundamental concepts in quantum information theory and suggest a generic approach based on entanglement distillation for achieving information-theoretic deniability, followed by an analysis of other closely related results such as the relation between the impossibility of unconditionally secure quantum bit commitment and deniability. Finally, we present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.

arXiv:2003.11663•Mar 25, 2020•2 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•18 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 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.

arXiv:2502.09522•New Journal of Physics•Oct 23, 2025•3 citations

Quantum Kolmogorov Complexity and the Quantum Turing Machine

Markus P. Müller

The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.

arXiv:0712.4377•Dec 28, 2007•17 citations

On the undecidability of quantum channel capacities

Archishna Bhattacharyya, Arthur Mehta, Yuming Zhao

An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.

quant-pharXiv:2601.22471•Feb 2, 2026•2 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.
The paper studies a quantum analogue of reset complexity: for a binary word www, qc(w)\mathrm{qc}(w)qc(w) is the smallest Hilbert-space dimension admitting two quantum channels and an initial state such that www is the unique shortest word whose channel is constant on all reachable states. The variant qcp(w)\mathrm{qcp}(w)qcp(w) additionally requires a pure reset target.
For every nonempty word, it establishes 2≤qc(w)≤⌈∣w∣+1⌉2\leq\mathrm{qc}(w)\leq\lceil\sqrt{|w|+1}\rceil2≤qc(w)≤⌈∣w∣+1​⌉, with equality in the upper bound for constant words: qc(0m)=⌈m+1⌉\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\rceilqc(0m)=⌈m+1​⌉. Synchronization is reformulated as a matrix product annihilating the reachable-difference space, of dimension at most d2−1d^2-1d2−1. The upper bound embeds a pattern-matching automaton into channel perturbations around complete depolarization; the constant-word lower bound follows from nilpotency depth.
In contrast, qc(01n0)=2\mathrm{qc}(01^n0)=2qc(01n0)=2 for all n≥1n\geq1n≥1, using dephasing and a precisely chosen qubit rotation. Thus reset length has no dimension-only bound. For pure targets, a rigidity argument excludes every word of length at least two in dimension two. An explicit qutrit rotation-and-funnel construction establishes qcp(01n0)=3\mathrm{qcp}(01^n0)=3qcp(01n0)=3, with reset holding on all input states. Both complexity functions are computable through real quantifier elimination.
The unbounded-length constructions rely on exact parameter coincidences and are generically destroyed by perturbations; parameter precision is not charged as a resource. Open questions include approximate synchronization, typical-word complexity, efficient computation, characterization of dimension-two realizations, and a general square-root upper bound for pure targets.
From the output produced by a memoryless deletion channel with a uniformly random input of known length nnn, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length mmm. We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings 000…\texttt{000}\ldots000…, 111…\texttt{111}\ldots111… and maximized by the alternating strings 0101…\texttt{0101}\ldots0101…, 1010…\texttt{1010}\ldots1010…. We present related combinatorial theorems involving binary (sub/super)-sequences and prove the minimal entropy conjecture for single and double deletions using clustering techniques. We then prove the minimization conjecture in the asymptotic limit using results from hidden word statistics by showing how the analytic-combinatorial methods of Flajolet, Szpankowski and Vallée, relying on generating functions, can be applied to resolve the case of fixed output length and n→∞n\rightarrow\inftyn→∞. Next, we revisit the notion of deniability in quantum key exchange (QKE). We introduce and formalize the notion of coercer-deniable QKE. We then establish a connection between covert communication and deniability to propose DC-QKE, a simple and provably secure construction for coercer-deniable QKE. We relate deniability to fundamental concepts in quantum information theory and suggest a generic approach based on entanglement distillation for achieving information-theoretic deniability, followed by an analysis of other closely related results such as the relation between the impossibility of unconditionally secure quantum bit commitment and deniability. Finally, we present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
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.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
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.
The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.
An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.