Polynomial-time coding theorem for time-bounded quantum Kolmogorov complexity

Conjecture: For every quantum polynomial-time sampler $S$ and every classical string $x$ that $S$ outputs with probability $\delta$ , there is a quantum program for $x$ of length at most $\log(1/\delta)+O(\log n)$ , decodable in quantum polynomial time. Equivalently, for the corresponding time-bounded quantum program complexity, $pKq^{\mathrm{poly}(n)}(x)\leq \log(1/\delta)+O(\log n)$ , where $n$ is the relevant input-length parameter.

References

Primary source

arXiv

Additional references

Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity — arXiv

computational-complexity kolmogorov-complexity quantum-cryptography

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new preprint proves a weaker quantum coding result and a related cryptographic characterization, but the desired polynomial-time theorem remains conjectural.

The problem asks for a polynomial-time coding theorem for time-bounded quantum Kolmogorov complexity. The latest work isolates this theorem as the remaining conjectural step toward a polynomial-time characterization of one-way puzzles.

September 2, 2026 development

The preprint defines probabilistic time-bounded quantum program complexity and proves a quantum coding theorem plus an exact characterization of one-way puzzles at time bound $2^{n/2}\,\mathrm{poly}(n)$ . It formulates, but does not prove, the polynomial-time analogue.

Current status (as of September 2026): A subexponential-time characterization is claimed in the preprint, while the polynomial-time coding theorem remains open and unverified.

Sources

No solutions have been posted yet.