REVIEW 4 major objections 4 minor 16 references
Hardness of Quantum Distribution Learning and Quantum Cryptography
T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper proves that quantum one-way puzzles exist exactly when proper quantum distribution learning is hard on average, and that $PP \neq BQP$ holds exactly when agnostic quantum distribution learning with respect to KL divergence is…
desk verdict Genuinely new OWPuzz–distribution-learning equivalence, but the PP≠BQP half is only as strong as an unproved companion lemma it leans on. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing choice is distribution learning itself as the learning model, because its hardness profile sits between the right two oracles: unlike quantum PAC learning, distribution learning has no efficient verifier, so its hardness survives a QCMA oracle, while a PP oracle can estimate quantum probability distributions and therefore breaks it — matching how OWPuzzs are broken by a PP oracle but not by a QCMA oracle. For Theorem 1.1 the workhorse object is the non-uniform quantum pseudorandom generator (nuQPRG), a QPT generator $Gen(1^n,\mu)$ with hidden seed $\mu \in [n]$ that is statistically far from uniform yet computationally indistinguishable from it; the reduction from learning hardness to a break uses a QPT-computable set $Good'$ of seeds defined by a hypothetical learner's behavior on uniform samples, letting a distinguisher amplify one learner into a full break. For Theorem 1.3 the intermediate object is worst-case hardness of quantum maximum likelihood estimation (QML): given one string $x$, no QPT algorithm finds a hypothesis $h$ with $\Pr[x \leftarrow D(h)]$ within a $2^{1/\epsilon(n)}$ factor of $\max_z \Pr[x \leftarrow D(z)]$, and the equivalence $PP = PostBQP$ turns a QML solver into a decider for every $PP$ language. For the agnostic upper bounds the engine is Stockmeyer counting — an NP oracle estimates classical probabilities within multiplicative error — which yields the $\Sigma_3^P$-oracle learner for the statistical-distance objective, whose approximation factor $(3+1/\epsilon)$ is forced by a known lower bound that no algorithm, even an unbounded one, can beat a factor of 3.
What would settle it
The concrete check is to run the two constructions against each other. For Theorem 1.1, build $D(\mu,b)$ from the proof of Lemma 3.5 using any specific candidate non-uniform quantum pseudorandom generator (for example, a random-circuit sampler); a QPT learner that, given polynomially many samples $(\mu,x_i)$, outputs $(\mu^*,b^*)$ with statistical distance at most $1/n$ for a $1 - 1/n^{100}$ fraction of seeds would break the generator and falsify the equivalence. For Theorem 1.3, fix any language in $PP$ and build the family $M^*(x,c)$ from Lemma 4.5; a QPT algorithm that on input $(x,1)$ returns a hypothesis whose likelihood is within a factor 2 of $\max_c \Pr[(x,1) \leftarrow M^*(x,c)]$, succeeding for all $x$, would decide that language in $BQP$ — which, for a language outside $BQP$ if $PP \ne BQP$, would refute the claimed characterization.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that two standard hardness notions of distribution learning exactly match the two central assumptions of quantum cryptography. Theorem 1.1 states that OWPuzzs exist if and only if proper quantum distribution learning is average-case hard: one direction builds a puzzle whose puzzling part is a batch of samples $x_1,\dots,x_t$ from $D(z)$ and whose unbounded verifier performs maximum likelihood over the parameter $z$ before checking statistical closeness of the claimed answer, and the other direction goes through non-uniform quantum pseudorandom generators, constructing a family $D(\mu,b)$ whose samples carry the hidden seed $\mu$ and either a pseudorandom or uniform string, so that learning the family amounts to distinguishing the generator from uniform. Theorem 1.3 states that $PP \ne BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard, with worst-case hardness of quantum maximum likelihood estimation as the intermediate object and the equality $PP = PostBQP$ as the lever: from the postselecting machine of a $PP$ language one builds a two-hypothesis family whose likelihood ratio is at least 3 exactly on the language, so a QML solver would decide the language in $BQP$. Theorem 1.5 then shows that hardness of agnostic quantum distribution learning with respect to statistical distance against PPT learners with a $\Sigma_3^P$ oracle implies $SampBQP \ne SampBPP$, which the paper notes is the first sampling-based quantum advantage derived from a worst-case hardness assumption on a standard learning framework.
Load-bearing premise
The load-bearing premise of the $PP \ne BQP$ characterization is Lemma 4.6, the claim that $PP = BQP$ would make worst-case quantum maximum likelihood estimation easy, whose proof the paper defers entirely to Lemma 4.2 of an earlier preprint by two of its own authors; if that borrowed lemma fails, agnostic KL distribution-learning hardness could not be shown to imply $PP \ne BQP$, and the equivalence of Theorem 4.4 collapses.
Editorial extensions
If this is right
- Average-case hardness of proper quantum distribution learning and the existence of OWPuzzs become the same assumption: every OWPuzz yields a hard-to-learn family, and every efficient learner for such a family yields a puzzle-breaking adversary.
- $PP \ne BQP$ becomes a statement about a standard worst-case learning problem: it holds exactly when every QPT-generatable family resists agnostic distribution learning with respect to KL divergence.
- Hardness of agnostic quantum distribution learning with respect to statistical distance, against PPT learners that carry a $\Sigma_3^P$ oracle, implies $SampBQP \ne SampBPP$ — the first sampling-based quantum advantage sourced from a worst-case hardness assumption on a standard learning framework.
- The classical analogues close an old gap: OWFs exist if and only if proper classical distribution learning is average-case hard, and $NP \nsubseteq BPP$ if and only if agnostic classical distribution learning with respect to KL divergence is hard, completing an equivalence whose one direction had been attributed only to personal communication.
- Any black-box PP-hardness proof for worst-case proper quantum distribution learning would imply $SampBQP \ne SampBPP$ from the infiniteness of the polynomial hierarchy, so the natural route from $PP \ne BQP$ to OWPuzzs must evade the black-box barrier; Theorem 1.2 records this as the reason the route looks extremely difficult.
Reading between the lines
- My inference: the two equivalences sit one level apart — average-case proper hardness characterizes OWPuzzs while worst-case agnostic KL hardness characterizes $PP \ne BQP$ — so the missing worst-case-to-average-case reduction within distribution learning is exactly the quantum analogue of the classical open road from $P \ne NP$ to OWFs, and Theorems 1.2 and 1.8 say such a reduction would have to
- My inference: because the classical collapse of improper to proper distribution-learning hardness runs through pseudorandom functions, and no construction of quantum PRFs (or their analogues) from OWPuzzs is known, the quantum proper-versus-improper question may genuinely separate; a proof that OWPuzzs imply only improper, not proper, hardness would mark a real divergence between classical and qua
- My inference: Theorem 1.1 reframes the hunt for concrete OWPuzzs as the hunt for explicitly hard families in proper quantum distribution learning — the quantum counterpart of how LPN and LWE grew out of classical learning hardness — so candidate families from random quantum circuits or IQP-type samplers are now testable starting points, since hardness of learning their output distributions would d
- My inference: the paper notes its $\Sigma_3^P$ oracle level in Theorem 5.3 is not known optimal; if a lower-order oracle (say NP, or no oracle) sufficed for agnostic statistical-distance learning, the implication to $SampBQP \ne SampBPP$ would hold against stronger adversaries, making the quantum-advantage assumption harder to evade.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper establishes equivalences between quantum cryptographic primitives and hardness of distribution learning. Theorem 1.1 states that OWPuzzs exist if and only if proper quantum distribution learning is average-case hard; this is proved in Section 3 via a reduction through non-uniform QPRGs. Theorem 1.3 states that PP ≠ BQP if and only if agnostic quantum distribution learning with respect to KL divergence is hard; the proof in Section 4 uses worst-case quantum maximum likelihood estimation as an intermediate notion. The paper also contains classical analogues (Theorems 3.16 and 4.12), an upper bound for agnostic classical distribution learning with respect to statistical distance using a Σ^P_3 oracle (Theorem 5.3), a quantum version using a Σ^{PP}_2 oracle (Theorem 5.4), and results connecting agnostic distribution learning to sampling-based quantum advantage (Theorems 5.9 and 5.11).
Significance. If the main results hold, they provide the first complete characterization of OWPuzzs by a standard learning-theoretic hardness notion, as well as a characterization of PP ≠ BQP by agnostic distribution learning. The paper is generous with technical detail in the central reduction of Theorem 3.3, including explicit claims and parameter choices, and it supplies new classical results, notably the proof of the missing direction in the Abe–Warmuth equivalence between NP ⊈ BPP and worst-case maximum likelihood hardness. The Stockmeyer-style upper bound in Theorem 5.3 is a useful contribution. However, two load-bearing steps are deferred to other papers, one of them a companion preprint by two of the authors, which prevents the manuscript from being fully self-contained at the present stage.
major comments (4)
- [§4.1, Lemma 4.6] Lemma 4.6 states that PP = BQP implies worst-case quantum maximum likelihood estimation is easy, and the proof is omitted with the remark that it follows from Lemma 4.2 of [HH24]. This is load-bearing for the 'if' direction of Theorem 4.4: Lemma 4.5 gives PP ≠ BQP ⇒ QML hard, but the converse direction QML hard ⇒ PP ≠ BQP needs Lemma 4.6. The lemma is not a purely formal consequence of PP = BQP: a BQP oracle for a PP language can estimate individual probabilities, but QML requires producing a hypothesis h that approximately maximizes Pr[x ← D(h)] over an exponentially large search space. The paper should include a self-contained proof of Lemma 4.6, or at minimum a detailed reduction with explicit handling of the search problem, rather than deferring to an unpublished companion paper by two of the authors.
- [Appendix B, Theorem 5.9] The proof of Theorem 5.9 is a chain of steps each labeled 'in the similar way as' and referencing [KT25], [CGG24], [HM24], and Lemma 3.5 of the present paper, without stating or proving the intermediate objects such as distributionally one-way puzzles and nuQEFI pairs secure against Σ^P_3-oracle algorithms. Since Theorem 5.9 is the basis of Theorem 1.4 and Remark 5.10, this is not just a presentation shortcut: the reader cannot verify that the relativized versions of the cited theorems hold with the same parameters and security notions. The appendix should either state and prove each step, or cite precise theorem numbers from the corresponding papers and describe the uniform translation of the oracles involved.
- [§4.2, Theorem 4.12] The proof of Theorem 4.12 is presented as a sketch, and the direction NP ⊈ BPP ⇒ worst-case classical maximum likelihood hardness is said to follow 'in the same way as Lemma 4.5', while the direction worst-case classical MLE hardness ⇒ NP ⊈ BPP is said to follow by replacing Lemma 4.6 with Theorem 2.2. Because Lemma 4.6 itself lacks a proof in this manuscript, the classical theorem is not independently verifiable from the text. Since Theorem 4.12 is advertised as completing an equivalence that was only attributed to a personal communication in [AW92], a full proof is needed here rather than a reference to the deferred quantum argument.
- [Theorem 1.2 and §5.2] The paper uses the phrase 'worst-case hardness of proper quantum distribution learning' in Theorem 1.2 and in Figure 1, but no formal definition of this notion appears in the paper. The proof sketch for Theorem 1.2 says it is 'straightforward' that this hardness implies hardness of agnostic quantum distribution learning with respect to statistical distance, and it then invokes Theorem 5.12, which concerns a different statement (agnostic QDL with respect to statistical distance being PP-hard). A formal definition of worst-case proper distribution learning and a proof of the implication to agnostic hardness are required, or the theorem should be restated in terms of the formally defined object.
minor comments (4)
- [§1.2] There is a typo in 'quantum ditribution learning' in the Related Works paragraph; it should be 'quantum distribution learning'.
- [§4, Definition 4.1] The notation in Definition 4.1 writes Opt_n := min_{a ∈ {0,1}^n} {D_KL(T(1^n)∥D(1^n,a))}, but the closing brace appears misplaced in the displayed formula; this is easy to fix but currently confusing.
- [§2.4, Assumption 2.10] The 'quantum advantage assumption' is referenced in two footnotes (footnotes 1 and 3) with the same explanation; one of them could be removed or made into a cross-reference.
- [Figure 1] The figure caption relies on red and black lines, which may not be accessible to color-blind readers; it would help to use line styles or labels in addition to color.
Circularity Check
Main equivalences are self-contained reductions; the only load-bearing gap is a deferred self-cited lemma for the reverse direction of Theorem 4.4.
-
self citation load bearing
[Section 4.1, proof block after Lemma 4.6.]
"Lemma 4.6 follows from Lemma 4.2 in [HH24]. Therefore, we omit the proof and refer it to [HH24]."
Lemma 4.6 is the exact converse needed to close Theorem 4.4: Lemma 4.5 only gives PP≠BQP implies worst-case QML hardness, and Lemmas 4.7 and 4.8 transfer QML hardness to agnostic KL hardness and back. The missing implication, QML hardness implies PP≠BQP, is the contrapositive of Lemma 4.6, which is not proved here but delegated to Lemma 4.2 of [HH24], a companion preprint by two of the authors. Since a BQP algorithm for PP languages need not include an efficient search over exponentially many candidate hypotheses h, the deferred lemma is doing real work. No machine-checked or independently reproduced proof is supplied, so the claimed 'if and only if' statement rests on an unverified self-citation at its load-bearing point.
full rationale
Walking the derivation chain: Theorem 1.1 is proved by explicit constructions in both directions, with Lemma 3.4 building a OWPuzz from a hard learning instance and Lemma 3.5 building a hard learning instance from a nuQPRG. Theorem 1.3's internal lemmas 4.5, 4.7, and 4.8 are self-contained reductions among PP≠BQP, worst-case QML hardness, and agnostic KL hardness. Theorems 5.3, 5.11, and 5.12 are direct upper-bound and contrapositive arguments. The only place where the claimed equivalence is not independently derived is Lemma 4.6: the omitted proof from [HH24] provides the QML-easy-under-PP=BQP direction that closes the equivalence. Because that citation is a companion preprint by two of the authors and no machine-checked or externally verified version is indicated, I treat it as a load-bearing self-citation rather than as a reduction-by-construction. Since the rest of the paper's reductions are between independent objects and none of the predictions is a renamed fit, the circularity score is 2 rather than higher.
Assumptions & free parameters
assumptions (6)
- standard math Hoeffding inequality and union bound
- standard math Stockmeyer approximate counting theorem (Theorem 2.2)
- standard math PP = PostBQP (Aaronson 2005)
- domain assumption OWPuzzs exist if and only if non-uniform QPRGs exist (Theorem 2.18, from [KT24, CGG24])
- domain assumption Lemma 4.2 of [HH24]: PP = BQP makes worst-case quantum maximum likelihood estimation easy
- domain assumption Quantum advantage assumption (Assumption 2.10)
Cite this review
Pith. "Pith review of Hardness of Quantum Distribution Learning and Quantum Cryptography." pith.science (2026). https://pith.science/paper/E2VPH5BC
@misc{pith2026250701292,
author = {Pith},
title = {Pith review of: Hardness of Quantum Distribution Learning and Quantum Cryptography},
year = {2026},
howpublished = {\url{https://pith.science/paper/E2VPH5BC}},
note = {Machine review of arXiv:2507.01292}
}
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^{\Sigma_3^P}$ learners implies $SampBQP \neq SampBPP$.
Figures
Reference graph
Works this paper leans on
-
[1]
Run DisPP ϵ (a,b,x i) for alli∈ [t(n)]
-
[2]
For alli∈ [t(n)], runXa,ri(2)←B PP(a;ri) and DisPP ϵ (a,b,X a,ri)
-
[3]
Output 1 if ⏐⏐⏐⏐⏐⏐ ∑ i∈[t(n)] DisPP ϵ (a,b,x i) t(n) − ∑ i∈[t(n)] DisPP ϵ (a,b,X a,ri) t(n) ⏐⏐⏐⏐⏐⏐ ≤ Optn +ω(n). (290) Otherwise, output0. 55 For any functionω, and anya1,...,a i∈{ 0, 1}i withi∈ N, let us define Lω,(a1,...,ai) (291) := { {xi,ri}i∈[t(n)]∈{ 0, 1}∗,n∈ N :∃a∈{ 0, 1}n−i such that∀b∈{ 0, 1}n, we have (292) 1←M PP ω (1n, (a1,...,a i),a,b, {xi,ri...
-
[5]
Quantum cryptography and meta-complexity
(Cited on page 2.) [HM24] Taiga Hiroka and Tomoyuki Morimae. Quantum cryptography and meta-complexity. arXiv:2410.01369, 2024. (Cited on page 8, 57.) [HN22] Shuichi Hirahara and Mikito Nanashima. On worst-case learning in relativized heuristica. In 62nd FOCS, pages 751–758. IEEE Computer Society Press, February 2022. (Cited on page 1.) [HN23] Shuichi Hira...
-
[7]
Cryptographic characterization of quantum advantage
(Cited on page 1, 4.) [MSY25] Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage. InProceedings of the 57th Annual ACM Symposium on Theory of Computing,STOC’25,page1863–1874,NewYork,NY,USA,2025.AssociationforComputing Machinery. (Cited on page 6.) 53 [MY22] Tomoyuki Morimae and Takashi Yamakawa. Qua...
work page 2025
-
[9]
One-way functions are necessary and sufficient for secure signatures
(Cited on page 1, 2, 4.) [Rom90] John Rompel. One-way functions are necessary and sufficient for secure signatures. In22nd ACM STOC, pages 387–394. ACM Press, May 1990. (Cited on page 1.) [SSHE21] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert. On the quantum versus classical learnability of discrete distributions.Quantum, 5:417, Mar...
work page 1990
-
[10]
Generalpropertiesofquantumbitcommitments(extendedabstract)
(Cited on page 1.) [Yan22] JunYan. Generalpropertiesofquantumbitcommitments(extendedabstract). InShwetaAgrawal and Dongdai Lin, editors,ASIACRYPT 2022, Part IV, volume 13794 ofLNCS, pages 628–657. Springer, Cham, December 2022. (Cited on page 1.) [Yat85] Yannis G. Yatracos. Rates of Convergence of Minimum Distance Estimators and Kolmogorov’s Entropy. The ...
work page 2022
-
[14]
Uniformly randomly sample{ri}i∈[t(n)]
Show all 16 references
-
[15]
For allI∈ [n], run the following. (a) Check if there existsaI+1,...,a n∈{ 0, 1}n−I such that ⏐⏐⏐⏐⏐ ∑ i∈[t(n)] DisPP ϵ (out1,..., outI−1, 1,aI+1,...,a n,b,x i) t(n) (294) − ∑ i∈[t(n)] DisPP ϵ (out1,..., outI−1, 1,aI+1,...,a n,b,X (out1,...,outI−1,1,aI+1,...,an),ri) t(n) ⏐⏐⏐⏐⏐ (...
-
[16]
Output out1,..., outn. We can show thatAΣPP 2 satisfies Pr [ SD(D(1n,h ),T (1n))≤ ( 3 + 1 ϵ(n) ) · Optn + 1 ϵ(n) : {xi}i∈[t(n)]←T (1n)⊗t(n) h←A ΣPP 2 (1n,{xi}i∈[t(n)]) ] ≥ 1− 1/δ(n) (297) forallsufficientlylarge n∈ N. Here,Optn := mina∈{0,1}n{SD(T (1n),D(1n,a ))}. Theanalysisi...
-
[1984]
Computational complexity of learning efficiently generatable pure states, 2024
(Cited on page 1.) [HH24] Taiga Hiroka and Min-Hsiu Hsieh. Computational complexity of learning efficiently generatable pure states, 2024. (Cited on page 6, 9, 29, 36.) 51 [HIL+23] Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. A duality b...
2024
-
[2001]
The hardness of learning quantum circuits and its cryptographic applications, 2025
(Cited on page 2, 3.) [FGSY25] Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The hardness of learning quantum circuits and its cryptographic applications, 2025. (Cited on page 6.) [FKM+18] Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura,...
2025
-
[2005]
The equivalence of sampling and searching.Theor
(Cited on page 12.) [Aar14] Scott Aaronson. The equivalence of sampling and searching.Theor. Comp. Sys., 55(2):281–298, August 2014. (Cited on page 13.) [ABK24] Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational ...
2014
-
[2006]
(Cited on page 1, 3.) [NY15] Moni Naor and Eylon Yogev
Association for Computing Machinery. (Cited on page 1, 3.) [NY15] Moni Naor and Eylon Yogev. Bloom filters in adversarial environments. In Rosario Gennaro and Matthew J. B. Robshaw, editors,CRYPTO 2015, Part II, volume 9216 ofLNCS, pages 565–584. Springer, Berlin, Heidelberg, ...
2015 arXiv
-
[2023]
Furst, Michael J
(Cited on page 1.) [BFKL94] Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor,CRYPTO’93, volume 773 ofLNCS, pages 278–291. Springer, Berlin, Heidelberg, August 1994. (...
1994
-
[2024]
Founding quantum cryptography on quantum advantage, or, towards cryptography from #P hardness
(Cited on page 1, 8, 14, 15.) [KT25] Dakshita Khurana and Kabir Tomer. Founding quantum cryptography on quantum advantage, or, towards cryptography from #P hardness. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 178–188, New York, NY, US...
2025
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.