{"id":"arxiv/2609.02687","url":"https://arxiv.org/abs/2609.02687","tags":["quant-ph"],"score":0,"title":"Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity","domain":"quant-ph","source":"arxiv","authors":["Morteza Saberikamarposhti"],"reviews":0,"subject":"quant-ph","summary":"We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}