{"ID":2898978,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.01292","arxiv_id":"2507.01292","title":"Hardness of Quantum Distribution Learning and Quantum Cryptography","abstract":"The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\\neq BQP$, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from $P \\neq NP$-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to $P \\neq NP$. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from $PP \\neq BQP$. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from $PP \\neq BQP$. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then $SampBQP \\neq SampBPP$ follows from the infiniteness of the polynomial hierarchy. Despite that, we show that $PP \\neq BQP$ is equivalent to another standard notion of hardness of learning: agnostic. We prove that $PP \\neq BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against $PPT^{Σ_3^P}$ learners implies $SampBQP \\neq SampBPP$.","short_abstract":"The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\\neq BQP$, whil...","url_abs":"https://arxiv.org/abs/2507.01292","url_pdf":"https://arxiv.org/pdf/2507.01292v1","authors":"[\"Taiga Hiroka\",\"Min-Hsiu Hsieh\",\"Tomoyuki Morimae\"]","published":"2025-07-02T02:12:38Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}