{"id":"0aab3a36-a158-4126-bff7-afd907387ce2","arxiv_id":"2507.01292","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"One-way puzzles exist if and only if proper quantum distribution learning is average-case hard, and PP ≠ BQP if and only if agnostic quantum distribution learning with KL divergence is hard.","lead":"This paper proves that one-way puzzles, a quantum cryptographic primitive, exist exactly when a natural quantum distribution-learning problem is hard on average. It also shows that PP ≠ BQP is equivalent to hardness of a different learning problem, agnostic distribution learning with respect to KL divergence.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reverse direction of Theorem 4.4—that hardness of agnostic KL distribution learning implies PP≠BQP—rests entirely on Lemma 4.6, whose proof is omitted and deferred to the companion preprint [HH24].","rationale":"The reader's weakest-assumption analysis identifies exactly the same point: Lemma 4.6 is the one central step not proved in the manuscript. After reading the full proof, the rest of the main equivalence is largely self-contained: Lemma 3.5's construction from non-uniform QPRGs is written out, and Lemmas 4.5, 4.7, and 4.8 contain detailed arguments. The single unresolved load-bearing dependency is the imported [HH24, Lemma 4.2]. My concern is not that the result contradicts consensus; the lemma may well be true, but it is not independently established here, and the manuscript itself states that the proof is omitted. I also note that Appendix B is sketch-level, but it supports the secondary quantum-advantage results rather than the headline OWPuzz and PP/BQP characterizations. Given that this is a missing proof of a load-bearing lemma rather than a demonstrated falsehood, conditional acceptance is the appropriate disposition: the paper's main claims should be accepted only if [HH24, Lemma 4.2] is verified. My read therefore leaves the reader's CONDITIONAL verdict unchanged.","tokens_in":49933,"tokens_out":7595,"duration_ms":94123,"concrete_test":"Obtain or reconstruct a complete proof of [HH24, Lemma 4.2] and verify the critical search step: starting from a BQP algorithm that decides every PP language, construct a QPT algorithm that, on input x and a description of D, outputs h∈{0,1}^n with Pr[x←D(h)] ≥ max_z Pr[x←D(z)]/poly(n) while making only polynomially many queries and never enumerating all z. If the only available argument is an enumeration over z, the lemma is invalid as stated and the converse of Theorem 4.4 must be weakened. Re-run Theorem 4.4's proof with this lemma either proved in an appendix or explicitly imported as an unproved assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.6 states that PP=BQP makes worst-case quantum maximum-likelihood (QML) estimation easy, and the paper says this follows from [HH24, Lemma 4.2], omitting the proof. This is the load-bearing step for the 'if' direction of Theorem 4.4. Lemma 4.5 supplies only PP≠BQP ⇒ QML hard, while the converse (QML hard ⇒ PP≠BQP) needs exactly Lemma 4.6. Since Lemmas 4.7 and 4.8 transfer between QML hardness and agnostic KL hardness, Theorem 1.3 collapses to a one-way implication if Lemma 4.6 fails. The missing lemma is not a trivial consequence of PP=BQP: a BQP decision procedure for PP languages can estimate individual probabilities, but QML requires outputting a hypothesis h that approximately maximizes Pr[x←D(h)] over exponentially many h. A naive algorithm that enumerates all h∈{0,1}^n is not quantum polynomial time, so [HH24, Lemma 4.2] must provide a uniform polynomial-time search argument. The paper's own text flags the omission at Section 4.1, and no independent verification or machine-checked proof is supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":50204,"tokens_out":7001,"duration_ms":84324,"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":[{"comment":"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.","section":"§4.1, Lemma 4.6"},{"comment":"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.","section":"Appendix B, Theorem 5.9"},{"comment":"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.","section":"§4.2, Theorem 4.12"},{"comment":"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.","section":"Theorem 1.2 and §5.2"}],"minor_comments":[{"comment":"There is a typo in 'quantum ditribution learning' in the Related Works paragraph; it should be 'quantum distribution learning'.","section":"§1.2"},{"comment":"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.","section":"§4, Definition 4.1"},{"comment":"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.","section":"§2.4, Assumption 2.10"},{"comment":"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.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The main concern is completeness rather than novelty or correctness of the reductions that are actually proved. The reliance on [HH24, Lemma 4.2] for Lemma 4.6 is particularly important because [HH24] is a preprint by two of the present authors and the lemma addresses a non-trivial search-to-decision issue. I would encourage the editor to require either a self-contained proof of Lemma 4.6 or an explicit statement of the exact theorem from [HH24] with proof details, before the paper is accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper gives a fully written proof that proper quantum distribution learning is average-case hard iff OWPuzzs exist. That's new, and the construction from non-uniform QPRGs is clever; the claim that the learner must recover the bit b in the Good' set is spelled out. Second, the advertised equivalence between PP≠BQP and hardness of agnostic KL learning is not self-contained: the direction from hardness to PP≠BQP goes through Lemma 4.6, which is imported from [HH24] and not proved here.\n\nThe good part: the core of Theorem 1.1 is solid. The reduction is standard in outline but the details (sampling μ, b, and the Check subroutine) are written out, and I don't see a gap. The classical results in Section 3.2 are also a clear improvement: proper learning for OWFs is a real step beyond [HN23]'s improper case. The Σ3 upper bound in Section 5.3 is the right kind of contribution; even if not polished, it gives a concrete statement.\n\nThe soft spots. Lemma 4.6 is load-bearing for Theorem 1.3, and the stress-test note hits the right nerve. A BQP algorithm that decides PP languages can estimate probabilities, but maximum likelihood asks for a hypothesis in {0,1}^n maximizing that probability; enumeration over exponentially many candidates is not QPT. [HH24]'s Lemma 4.2 must be doing real work, and none of it appears here. The paper at least flags the omission in Section 4.1, but that doesn't make the result self-contained. The other concern is Appendix B: Theorem 5.9 is a chain of references rather than a proof; that's fine for a byproduct, but it should not be cited as a standalone result yet.\n\nIf I had to bet, I'd guess the HH24 lemma is true and the theorem survives. But 'bet' isn't proof. The paper should either include the proof or explicitly mark Theorem 1.3 as conditional on [HH24]. Those are exactly the things a referee should ask for.\n\nThis is a serious paper, worth a real referee. I'd send it to review, with a referee who knows both learning theory and quantum meta-complexity. If the import checks out, it's a strong paper; if not, the fix is localized but necessary.","headline":"Genuinely new OWPuzz–distribution-learning equivalence, but the PP≠BQP half is only as strong as an unproved companion lemma it leans on.","tokens_in":50744,"tokens_out":3291,"would_cite":true,"duration_ms":38317,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","81P68","94A60"],"pacs":["03.67.-a","03.67.Lx"],"model":"deepseek-v4-flash","headline":"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…","keywords":["one-way puzzles","quantum distribution learning","agnostic distribution learning","KL divergence","statistical distance","PP vs BQP","SampBQP vs SampBPP","learning-theoretic cryptography"],"falsifier":"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.","tokens_in":49753,"feed_emoji":"🧩","tokens_out":22162,"duration_ms":313208,"temperature":0.7,"pith_summary":"One-way puzzles (OWPuzzs) are the quantum analogue of one-way functions: a quantum-polynomial-time sampler outputs a public puzzle and a private answer, and no efficient quantum adversary can recover any valid answer from the puzzle alone. This paper proves the first complete characterization of OWPuzzs by a standard learning problem: OWPuzzs exist if and only if proper quantum distribution learning is average-case hard, meaning a learner given samples from an unknown distribution $D(z)$ cannot recover a hypothesis $z^*$ whose distribution is statistically close to $D(z)$. A second equivalence is proved at the complexity-theoretic level: $PP \\ne BQP$ holds if and only if agnostic quantum distribution learning with respect to KL divergence is hard — fitting an arbitrary unknown target distribution near-optimally by a distribution from a known QPT-generatable family — with worst-case hardness of quantum maximum likelihood estimation as the bridge between them. These results matter because in classical cryptography the link between one-way functions and learning hardness became the roadmap for basing cryptography on complexity assumptions, and no such link existed for the most fundamental quantum primitive. The paper also shows that the obvious next step, deriving worst-case hardness of proper distribution learning from $PP \\ne BQP$, would be extremely difficult: a black-box PP-hardness proof would imply sampling-based quantum advantage from the infiniteness of the polynomial hierarchy alone.","feed_headline":"One-way puzzles equal hard quantum distribution learning","feed_subtitle":"First complete characterization of one-way puzzles by learning hardness; PP≠BQP matches agnostic KL learning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduced one-way puzzles and showed classical OWPuzzs are equivalent to one-way functions; with [CGG24] it is the source of the OWPuzz–nuQPRG equivalence used in Lemma 3.5.","marker":"[KT24]"},{"why":"proved OWPuzz security amplification and the OWPuzz–nuQPRG equivalence (Theorems 2.16 and 2.18), the entry point for deriving hard distribution-learning families from OWPuzzs.","marker":"[CGG24]"},{"why":"established that OWPuzzs imply $PP \\ne BQP$ and that a PP oracle breaks OWPuzz security; this oracle separation is why distribution learning, rather than quantum PAC learning, is the right characterizing model.","marker":"[CGG+23]"},{"why":"constructed OWPuzzs from $PP \\ne BQP$ plus a quantum-advantage assumption, which poses the open question Theorem 1.1 addresses and supplies the proof template for Theorem 5.9.","marker":"[KT25]"},{"why":"supplies Lemma 4.2, from which Lemma 4.6 (PP = BQP makes worst-case QML easy) is imported; this is the load-bearing step for one direction of Theorem 4.4 and is not proved in the present paper.","marker":"[HH24]"},{"why":"proved the classical baseline that OWFs are equivalent to average-case hardness of improper classical distribution learning; Theorem 1.9 strengthens this to proper learning.","marker":"[HN23]"},{"why":"Stockmeyer counting — an NP oracle approximates classical probabilities within multiplicative error — is the engine of the $\\Sigma_3^P$-oracle agnostic learner in Theorem 5.3.","marker":"[Sto83]"},{"why":"shows a PP oracle can compute quantum probabilities, the basis of the $\\Sigma_2^{PP}$ upper bound in Theorem 5.4 and of the claim that PP breaks quantum distribution learning hardness.","marker":"[FR99]"},{"why":"source of the agnostic KL learning model and of the equivalence between its hardness and worst-case classical maximum likelihood estimation; Theorem 1.10 supplies the missing proof direction.","marker":"[AW92]"},{"why":"proves that even unbounded algorithms cannot beat approximation factor 3 in density estimation, fixing the $(3+1/\\epsilon)$ target in the statistical-distance definitions.","marker":"[BKM19]"}],"fun_headline_variants":["Hard distribution learning = one-way puzzles","PP≠BQP iff agnostic learning is hard","Quantum crypto from distribution learning hardness","One-way puzzles from average-case learning hardness","Distribution learning pins down quantum assumptions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hard distribution learning = one-way puzzles","PP≠BQP iff agnostic learning is hard","Quantum crypto from distribution learning hardness","One-way puzzles from average-case learning hardness","Distribution learning pins down quantum assumptions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1732,"prompt_tokens":1254,"completion_tokens":478,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":870,"completion_tokens_details":{"reasoning_tokens":414}},"tokens_in":870,"tokens_out":478,"duration_ms":6411,"temperature":1.0,"reasoning_tokens":414,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:56:08.204897+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}