A New Way to Measure How Complex Quantum States Are

In the paper's words

Quantum information processing lacks a universally accepted quantitative measure of the algorithmic content of quantum states: existing algorithmic information measures either describe quantum objects through classical strings or become infinite when applied directly to the continuum of quantum amplitudes. This gap blocks principled comparison of state-preparation costs and rigorous randomness certification. We define a family of quantum Kolmogorov complexity (QKC) measures as the length of the shortest quantum program that, executed on a universal deterministic-control quantum Turing machine, outputs a target state within a prescribed fidelity, with an additive fidelity penalty.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. As a worked illustration, assuming a translator-program length of 120 bits and a classical Kolmogorov complexity of 500 bits for a 256-bit string, we derive the two-sided bound $380 \le K_U^{\varepsilon}(|x\rangle) \le 620$ bits, and with $\varepsilon = 2^{-10}$ a concrete 400-bit program yields the upper bound 410 bits.

   from Abstract

2. A worked numerical derivation: under the stated assumptions $L_U = 120$ bits and $K(x) = 500$ bits, the QKC of the corresponding basis state lies in $[380, 620]$ bits, and a 400-bit program with $\varepsilon = 2^{-10}$ gives the upper bound 410 bits (Section 4).

   from 1. Introduction

3. With fidelity parameter $\varepsilon = 2^{-10}$, a program of length 400 bits meeting the fidelity condition yields $$ K_U^{2^{-10}}(|x\rangle) \;\le\; 410 \text{ bits}, $$ a value consistent with the interval of Result R1.

   from 5. Results

4. Every numerical value in the family depends on $\varepsilon$; the penalty contributes $\lceil -\log_2 \varepsilon \rceil$ bits, so tightening fidelity from $2^{-10}$ to $2^{-20}$ adds 10 bits to every program's cost.

   from 6.1 Limitations

5. The fidelity penalty at tolerance $\varepsilon = 2^{-k}$ is exactly $k$ bits, so a certification protocol operating at $1 - 2^{-20}$ pays a fixed overhead of 20 bits per program relative to the penalty-free variant — a projection that follows from the definition of Section 3.2 and the arithmetic of Section 4.3, with the assumption that $\varepsilon$ is a power of two.

   from 7. Practical Implications and Engineering Pathways

6. The worked derivation, under the explicit assumptions $L_U = 120$ bits and $K(x) = 500$ bits, localized the exact QKC of a 256-bit basis state to $[380, 620]$ bits and gave the fidelity-tolerant upper bound of 410 bits at $\varepsilon = 2^{-10}$.

   from 8. Conclusion

How it is done

1. We define a family of quantum Kolmogorov complexity (QKC) measures as the length of the shortest quantum program that, executed on a universal deterministic-control quantum Turing machine, outputs a target state within a prescribed fidelity, with an additive fidelity penalty.

   from Abstract

2. Hardware teams allocate qubits and gate depth using circuit-complexity heuristics; protocol designers assess the randomness of generated states through entropies that ignore algorithmic structure; theorists compare candidate state-preparation schemes without a state-level measure of intrinsic description length.

   from 1. Introduction

3. Our construction is organized around exactly these criteria: Section 3 proves the robustness criterion as the invariance theorem, the reduction of Section 3 secures compatibility with classical complexity, and the fidelity parameter ties the measure to quantum information theory through the fidelity functional. [3] develops a Kolmogorov-style extension theorem for multitime (bi)probabilities in quantum mechanics and shows that two trajectories are enough for that purpose.

   from 2. Background and Related Work

4. We adopt the deterministic-control quantum Turing machine (dcq-TM) of [6] as the universal model.

   from 3.1 Model of Computation

What would falsify it

1. The central theoretical claim — uncomputability of exact QKC — would be falsified if an algorithm were exhibited that, for every quantum state $\rho$, outputs the exact value of $K_U^{0}(\rho)$.

   from 6.2 Falsifiability

2. The quantitative model, by contrast, is falsifiable at the level of its assumptions: if a concrete pair of universal dcq-TMs were instantiated and their translator program measured to have length far from the assumed 120 bits, the interval of Result R1 would have to be recomputed with the measured constant, and if the translator length were found to grow with the size of the simulated machine rather than remaining fixed, Theorem 1 itself would fail.

   from 6.2 Falsifiability

3. A statement of limitations, falsification conditions, and the smallest concrete test of the additive-constant model (Sections 6 and 7).

   from 1. Introduction

Where the claim stops

1. The assumed translator length $L_U = 120$ bits depends on the instruction set and encoding scheme of the dcq-TM; a different standard encoding changes $L_U$ and thereby shifts both interval endpoints by the same amount.

   from 6.1 Limitations

2. Extending the numerical illustration to entangled or generic superposed states requires assumptions about their classical description lengths that this paper does not supply.

   from 6.1 Limitations

3. For fixed $\varepsilon \gt 0$ the reduction yields only approximate bounds with a slack term growing with the tolerance; whether uncomputability extends verbatim to every fixed positive tolerance is open.

   from 6.1 Limitations

Where to read

1. Abstract198 words · 1 min
2. 1. Introduction377 words · 2 min
3. 2. Background and Related Work616 words · 3 min
4. 3. Methods904 words · 4 min
5. 4. Analysis448 words · 2 min
6. 5. Results179 words · 1 min
7. 6. Discussion622 words · 3 min
8. 7. Practical Implications and Engineering Pathways753 words · 3 min
9. 8. Conclusion217 words · 1 min
10. Provenance and AI Involvement240 words · 1 min