Original title: Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity
Morteza Saberikamarposhti · September 2026
Quantum cryptography needs basic building blocks to keep information secure. One fundamental puzzle block is called a one-way puzzle. Previously, researchers could only explain these puzzles using an uncomputable measure of data compression called Kolmogorov complexity, which cannot run within realistic time limits. To fix this, the researchers created a new measure of time-bounded quantum program complexity for strings, called pKq^t. It works by describing strings produced by quantum programs and recovering them using amplitude amplificationA quantum technique to boost the probability of finding correct outputs, used here for decoding., a quantum search method. First, they proved that strings appearing with probability delta get short descriptions that a quantum machine can decode in time O(sqrt(1/delta)) times a polynomial. Second, they proved one-way puzzlesCryptographic puzzles that are easy to check but hard to solve, without needing one-way functions. exist if and only if estimating this complexity at subexponential time bounds is weakly hard on average for quantum computers.
Imagine you have a secret recipe that someone wrote down. To keep it hidden, they tell you only how long it took them to create it, but not the ingredients or steps. The difficulty is that this clue depends on how much time you have to think about it. In this paper, one-way puzzles are like that secret recipe, and the time-bounded complexity is the clue used to characterize when such puzzles can exist.
This work helps cryptographers understand the minimal assumptions needed for secure systems. It shows that one-way puzzles, which are simpler than traditional cryptographic primitives, can be fully characterized by a specific type of computational hardness.
The paper leaves the polynomial-time characterization as an open conjecture. It also identifies relativized barriers that limit the approach. The results are exact only at subexponential time bounds, not at polynomial time.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity — Morteza Saberikamarposhti
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.