{"id":"2e85e8a0-7670-4016-a790-884f378c7b9d","arxiv_id":"2504.15343","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Secure quantum cryptography (one-way state generators, signatures, commitments, encryption) is constructed from new conjectures about the hardness of learning and cloning random quantum circuit outputs.","lead":"This paper proposes that learning or cloning the output of a random quantum circuit is computationally hard, and shows that if true, this hardness can be used to build secure quantum cryptography like digital signatures, bit commitments, and encryption. It gives oracle-based evidence and sketches how the schemes might run on noisy quantum devices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exact 1-design assertion in Claim 4.9 is justified by a false Pauli-invariance argument, but the underlying claim is true via a simpler first-layer depolarization argument, so the central theorems survive with a proof repair.","rationale":"After reading the construction, the main risk is whether Protocol 4.8 is a valid commitment. The reader flagged the exact 1-design claim. That concern is partially correct: the proof's Pauli-invariance step is invalid. But the conclusion is independently true: a product of independent random 1-designs on disjoint pairs is a 1-design, so a single brickwork layer already depolarizes the input if it covers all qubits, and two layers suffice for any parity. Thus the correctness lemma is true and the central claim survives. The binding proof has a direction/notation issue (the cloner is V†, not V) but the argument is standard Uhlmann plus Jensen and is repairable. The statistical hiding proof similarly relies on a coherent shadows algorithm whose expected fidelity is bounded by Corollary 2.3; no fatal gap appears. The NISQ-related computational Chernoff bound is only sketched and depends on imported [IK10] lemmas, but it is not part of Theorems 4.5/4.12. Overall the paper's central claims are plausible and the identified concern does not overturn them; a conditional verdict with proof revisions remains appropriate.","tokens_in":34293,"tokens_out":47158,"duration_ms":450638,"concrete_test":"One check that settles whether Claim 4.9's conclusion is sound: compute the average of C|0^n><0^n|C^† over the first two brickwork layers analytically. For each gate, use the two-qubit Clifford 1-design identity E_U U|00><00|U^† = I_4/4; averaging a full layer gives I/2^n on the covered qubits, and after two layers all qubits are covered. If the resulting average equals I/2^n for all n, the claimed 2^{-n} correctness bound holds and only the Pauli-invariance wording in the proof needs replacement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most delicate point in the central commitment construction is Claim 4.9, whose proof asserts that the uniform distribution over Cn is invariant under appending a layer of random Pauli operators. For a fixed-depth brickwork ensemble, appending a layer changes the depth, so the invariance statement is false as written. This is a genuine proof gap in the correctness argument. The conclusion, however, is true for a different reason: the circuit ensemble is a product distribution over layers, each two-qubit gate is uniform over the Clifford group (a 1-design on two qubits), and one full brickwork layer of independent 1-design gates is a completely depolarizing channel on all qubits it covers. If the first layer leaves boundary qubits idle, the second layer covers them; since d=log^2 n is at least 2, E_C[C|0><0|C^†] = I/2^n exactly. Therefore |⟨ψ0|ψ1⟩|^2 ≤ 2^{-n}, so correctness is not endangered. The proof of Claim 4.9 needs to be rewritten, but the central theorems 4.5 and 4.12 do not rest on a false lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two concrete average-case hardness assumptions about learning or cloning output states of random quantum circuits: the Computational No-Learning Assumption (Conjecture 1.1) and the Computational No-Cloning Assumption (Conjecture 1.2). Under these assumptions it constructs a one-way state generator from random circuits (Section 4.1), a quantum bit commitment scheme (Section 4.2), and, under an additional threshold direct-product-type bound, NISQ-friendly OWSGs and digital signature schemes (Section 5). It also proves a black-box lower bound for cloning in a state preparation oracle model (Section 3) and discusses evidence and relations to concurrent work.","tokens_in":34614,"tokens_out":24061,"duration_ms":224061,"significance":"If the paper's assumptions and proofs are made rigorous, the results would be a valuable step toward concrete quantum cryptographic primitives that do not rely on classical one-way functions. The commitment construction from the No-Cloning Assumption is direct and conceptually appealing, and the black-box lower bound in Section 3 is a clean contribution that gives real evidence for the proposed hardness assumptions. The NISQ-friendly framing is also timely. At the same time, the OWSG construction is essentially a restatement of the No-Learning Assumption, and the paper candidly notes this equivalence; the novelty lies in the commitment, signature, and NISQ-oriented consequences. Two load-bearing proof points currently need repair: the exact 1-design assertion used for commitment correctness and the quantum adaptation of the Impagliazzo-Kabanets threshold direct product theorem used for the NISQ-friendly constructions.","major_comments":[{"comment":"The correctness proof of the commitment scheme relies on the assertion that the uniform distribution over the fixed-depth brickwork ensemble C_n is an exact 1-design, justified by invariance under appending a layer of random Pauli operators. This justification is not valid as written: adding a Pauli layer changes the circuit depth, so the ensemble of depth-d circuits is not invariant under that operation, and merely having a gate set that 'includes' the Clifford group does not imply that uniform sampling from the gate set gives the exact twirling channel. This is load-bearing because the bound |<ψ0|ψ1>|^2 ≤ 2^{-n} is exactly what gives the correctness property of Protocol 4.8. The underlying claim may be salvageable by a different argument, for example by using the first brickwork layer of independently random two-qubit Clifford gates as an exact depolarizing channel, but the manuscript must supply a correct proof or modify the ensemble definition.","section":"Section 4.2, Claim 4.9"},{"comment":"The computational Chernoff bound for OWSGs is not actually proved. The proof delegates the core technical work to [IK10] with the statements that the arguments go through 'essentially unchanged' or 'can be checked' in the quantum setting, but this is not demonstrated. The Impagliazzo-Kabanets threshold direct product theorem is formulated for classical randomized algorithms with a classical predicate, whereas here the verification procedure is a quantum measurement; conditioning on its acceptance can disturb the state and entangle the output with the verification register. A formal reduction is required because Corollary 5.5 and the NISQ-friendly digital signature scheme of Section 5.2 depend on this lemma. As written, the claimed security of the threshold repetition is unsupported.","section":"Appendix A, Lemma A.1 and Claims A.3/A.5"},{"comment":"The proof of the amplification lemma ends by claiming that after switching flavors once more the final commitment satisfies 'negl(n)-statistical hiding and negl(n)-statistical binding'. This contradicts the impossibility of statistically hiding and statistically binding quantum commitments [BCMS97], and it also contradicts the lemma statement, which promises statistical hiding and computational binding. The preceding steps appear to yield the correct conclusion if the last flavor switch is described as producing computational binding; the text should be corrected to avoid this internal inconsistency.","section":"Lemma 4.14, final sentence"}],"minor_comments":[{"comment":"The notation 'log2n' (for example in the definition of C_n and in Theorem 4.5) is ambiguous; it should be typeset as log^2 n so that the claimed polynomial parameter choices are clear.","section":"Throughout"},{"comment":"In the overlap computation after applying V†, the inner product with <0^r|⊗<C|^{⊗k} appears to be a typo: since V acts on k−1 copies of |C>, the factor should be <0^r|⊗<C|^{⊗(k−1)}. The final expression is correct with this replacement, but the displayed formula as written is dimensionally inconsistent.","section":"Section 4.2, Claim 4.10"},{"comment":"The definition of correctness for a noninteractive quantum commitment is nonstandard: it is stated as orthogonality of |ψ0> and |ψ1> rather than as the success probability of an honest opening/verification procedure. Since later arguments cite standard parallel repetition and flavor-switching theorems, the authors should clarify how this definition connects to the standard correctness notion used in those theorems.","section":"Definition 4.7"},{"comment":"The proof of Corollary 1.3 is only a sketch and refers to a calculation 'virtually identical' to Claim 4.10. Because the corollary is used to position the No-Cloning Assumption as stronger than No-Learning, a complete proof or an explicit pointer to a full proof would improve the paper.","section":"Corollary 1.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope and likely to be influential, and the two main proof gaps appear repairable rather than fatal. The most serious risk is the unproven quantum adaptation of the Impagliazzo-Kabanets threshold direct product theorem; if that cannot be proved, the NISQ-friendly claims in Section 5 should be restated as conditional on an explicit new conjecture. The exact 1-design issue in Claim 4.9 should also be repaired before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Tom,\n\nThe paper does something worth paying attention to: it turns the plausible statement 'random circuit output states are hard to learn/clone' into concrete quantum cryptographic primitives, and it isolates a clean black-box lower bound. The OWSG from No-Learning is essentially a restatement, as the authors admit and as Hiroka-Hsieh independently noticed. The commitment from No-Cloning is the real new piece, and the direct analysis in Claims 4.10 and 4.11 is neat. Theorem 1.5 is a solid standalone result: the hybrid argument is standard but clean, and the Werner bound closes it.\n\nThe soft spots are real but patchable. Claim 4.9's proof is wrong as written: the uniform distribution over fixed-depth brickwork circuits is not invariant under appending a random Pauli layer, because that changes the depth. The stress-test note is right that the conclusion is still true: each layer of independent two-qubit Clifford gates is a 1-design, and over two layers every qubit is depolarized, so the average of |C><C| is I/2^n. The authors need to rewrite that proof, but the theorem doesn't fall. The computational Chernoff bound in Appendix A is only sketched, leaning on an [IK10] adaptation to quantum verification that is asserted rather than proved. I'd want that expanded before publication; it is load-bearing for the NISQ-friendliness section. The claim that improper learners don't break the OWSG because 'honest parties can detect mismatch in depth' looks wrong on the face of it—the verification procedure never checks depth, and an adversary could output a deeper circuit with high-fidelity output—but the core security proof is against proper learners, so this is a side remark that needs fixing, not a structural flaw.\n\nOverall, the central thesis holds up: assuming the conjectures, you get commitments and signatures without one-way functions, and the lower bound gives real evidence. Some parameter choices (d = log^2 n) are ad hoc, but that is acknowledged. This paper deserves a serious referee and, after a round of revision, will likely be a useful reference for the growing literature on quantum cryptography from native quantum assumptions. I would take it to the reading group and would probably cite it when discussing concrete instantiations. Send it to review.","headline":"A promising, genuinely useful paper whose main theorems survive a proof repair in Claim 4.9, but whose appendix and one side argument need real work before it is fully rigorous.","tokens_in":35069,"tokens_out":3646,"would_cite":true,"duration_ms":34300,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that if it is computationally hard to learn or clone the output state of a random quantum circuit, then that hardness alone yields secure quantum cryptography—one-way state generators, digital signatures, bit commitments…","keywords":["quantum cryptography","one-way state generators","quantum bit commitments","random quantum circuits","computational no-learning assumption","computational no-cloning assumption","classical shadows","NISQ-friendly cryptography"],"falsifier":"Compute or bound $\\mathbb{E}_{C \\gets \\mathcal{C}_n}\\big[C^{\\otimes 2}|0\\rangle\\langle 0|^{\\otimes 2}(C^\\dagger)^{\\otimes 2}\\big]$ for the $n$-qubit 1D brickwork ensemble of depth $\\log^2 n$ with the Clifford-containing gate set; if this differs from the projector onto the symmetric subspace of $(\\mathbb{C}^2)^{\\otimes 2}$, the ensemble is not an exact 1-design and Claim 4.9's correctness derivation fails as written.","tokens_in":34060,"feed_emoji":"🔐","tokens_out":8482,"duration_ms":70577,"temperature":0.7,"pith_summary":"This paper tries to establish that two concrete, average-case hardness assumptions about random quantum circuits can serve as the foundation for quantum cryptography. The Computational No-Learning Assumption says a polynomial-time adversary, given copies of $|C\\rangle = C|0^n\\rangle$ for a random circuit $C$, cannot output a circuit $D$ whose state approximates $|C\\rangle$; the Computational No-Cloning Assumption says it cannot produce an extra approximate copy. The paper proves that the first assumption yields a cryptographically secure one-way state generator, and the second yields a quantum bit commitment with statistical hiding and computational binding, both amplifiable to negligible error. It gives black-box evidence for both assumptions and constructs noise-tolerant versions suitable for near-term quantum devices. A sympathetic reader would care because these are concrete instantiations of quantum cryptography whose security may hold without one-way functions.","feed_headline":"Hardness of learning random circuits yields quantum cryptography","feed_subtitle":"Two concrete quantum hardness assumptions give commitments, signatures, and one-way state generators.","key_machinery":"The load-bearing objects are the random circuit ensemble $\\mathcal{C}_n$—$n$-qubit 1D brickwork circuits of depth $d = \\log^2 n$ with a gate set that includes the Clifford group—and their output states $|C\\rangle = C|0^n\\rangle$. The No-Learning Conjecture (1.1) posits that no QPT algorithm can turn $\\mathrm{poly}(n)$ copies of $|C\\rangle$ into a circuit $D \\in \\mathcal{C}_n$ with $|\\langle C|D\\rangle|^2 \\ge \\varepsilon$ with probability larger than $\\delta$; the No-Cloning Conjecture (1.2) posits that no QPT algorithm can turn $k$ copies into a $(k+1)$-copy state with fidelity at least $\\varepsilon$ with probability larger than $\\delta$. The proofs run on three pieces of machinery: the classical shadows protocol of Huang–Kueng–Preskill, which supplies the inefficient learner used as an upper bound and as a coherent sub-routine in the hiding proof; parallel repetition plus the computational Chernoff bound, which amplifies weak security; and Werner's optimal-cloning bound, which is the base case of the black-box lower bound. For the NISQ-friendly variant, threshold repetition replaces full parallel repetition, with a computational Chernoff bound showing that inverting noticeably more than a $\\gamma$ fraction of blocks is hard.","core_discovery":"The central claim is that hardness of learning and cloning random-circuit output states is not merely a learning-theoretic curiosity but a usable cryptographic foundation. Theorems 4.5 and 4.12 (with Claims 4.9–4.11) state that, under the $\\varepsilon$-No-Learning Assumption for any $\\varepsilon \\le 1 - 1/\\mathrm{poly}(n)$, the random circuit OWSG—key is a circuit description $C$, output is $|C\\rangle$—can be amplified by parallel repetition to a cryptographically secure OWSG; and under the $\\delta$-No-Cloning Assumption, the superposition-over-circuits commitment (Protocol 4.8) satisfies correctness, $4\\varepsilon$-statistical hiding, and $(2-\\delta)\\delta$-computational binding, which a further amplification chain makes negligible in both parameters. The paper also proves Theorem 1.5: in a state-preparation-oracle model, any $T$-query algorithm given $k$ copies of a Haar-random target state has cloning fidelity at most $2^{-n/4}(2T + k + 1)$, exponentially small unless both $T$ and $k$ are exponential. All of these results are conditional on the two conjectures, and the conjectures themselves are what the paper offers as its new foundational assumptions.","pith_inferences":["If the exact 1-design claim in Claim 4.9 turns out to fail for fixed-depth brickwork circuits, the commitment's correctness proof needs a replacement; an approximate 1-design or a modified ensemble with random Pauli layers could restore the argument, and this is directly testable.","The paper's black-box model with Haar-random states can be adapted to distinguish no-learning from no-cloning: a separation would require an oracle where cloning is easy but learning a classical description remains hard, extending the discussion near Corollary 1.3.","The threshold repetition technique suggests a more general recipe: any cryptographic primitive with a gap between honest noisy correctness and adversarial success probability can be amplified by a computational Chernoff bound, which might apply to other NISQ-friendly primitives beyond signatures.","The finite-size estimates in Section 5, such as a roughly 4,000-qubit public key for $n=20$ and depth $20$, should be re-derived for different noise models and circuit architectures before drawing conclusions about near-term feasibility; the paper itself flags this dependence on noise assumptions."],"forward_implications":["If $\\varepsilon$-No-Learning holds for any $\\varepsilon \\le 1 - 1/\\mathrm{poly}(n)$, then a cryptographically secure one-way state generator exists, and cryptographic tasks known to follow from OWSGs—including quantum digital signatures and commitments via existing reductions—can be instantiated concretely from random circuits.","If $\\delta$-No-Cloning holds, Protocol 4.8 is a quantum bit commitment with negligible hiding and binding error after the amplification chain of Lemma 4.14, giving a direct route from a native quantum hardness assumption to commitments.","The black-box lower bound (Theorem 1.5) means that in the oracle model, cloning a Haar-random state from $k$ copies requires $2^{\\Omega(n)}$ queries or copies, so shadow-tomography-style attacks cannot be efficient in that model.","Under an inverse-polynomial-fidelity noise model, the threshold-repeated OWSG and the digital signature scheme of Protocol 5.8 remain correct on noisy hardware while remaining secure against noiseless polynomial-time adversaries.","Because No-Cloning implies a weak No-Learning assumption (Corollary 1.3), the two conjectures form a hierarchy: the stronger cloning assumption buys the simpler commitment construction, while the weaker learning assumption already buys OWSGs."],"supporting_citations":[{"why":"Supplies the state-of-the-art learning algorithm for shallow circuits; its superpolynomial time and sample complexity at depth $d = \\log^2 n$ is the main evidence for the No-Learning conjecture and motivates the parameter choice.","marker":"[LL24]"},{"why":"Provides the classical shadows protocol, which gives the exponential-time polynomial-sample learner in Corollary 2.3 and is used coherently inside the commitment hiding proof of Claim 4.10.","marker":"[HKP20]"},{"why":"Gives the optimal cloning fidelity of Haar-random states, used as the base case in the black-box lower bound Theorem 1.5.","marker":"[Wer98]"},{"why":"Defines one-way state generators and proves the parallel-repetition hardness amplification used to turn the weak OWSG of Lemma 4.4 into the cryptographically secure OWSG of Theorem 4.5.","marker":"[MY22a]"},{"why":"Introduces the OWSG-to-digital-signature construction that Protocol 5.8 instantiates with the random-circuit OWSG.","marker":"[MY22b]"},{"why":"Provides the quantum parallel repetition theorem used in Lemma 4.14 to amplify the binding error of the commitment scheme.","marker":"[BQSY24]"},{"why":"Provides the flavor-switching transformation for quantum commitments (Lemma 4.13) used in the amplification chain of Lemma 4.14.","marker":"[HMY23]"},{"why":"Supplies the threshold direct product theorem and constructive Chernoff bound that underpin the computational Chernoff bound for OWSGs in Lemma 5.4 and Appendix A.","marker":"[IK10]"}],"fun_headline_variants":["Random circuit learning hardness yields quantum cryptography","No-learning and no-cloning assumptions forge quantum crypto","Unlearnable quantum states ground new crypto primitives","Hardness of learning circuits bakes in quantum security","From circuit-state hardness to OWSGs and commitments"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The commitment's correctness rests on the claim that the uniform distribution over the fixed-depth 1D brickwork circuit ensemble is an exact 1-design, justified only by invariance under a final random Pauli layer; if that ensemble is not a 1-design, the negligible-overlap bound between commitments to 0 and 1 is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Random circuit learning hardness yields quantum cryptography","No-learning and no-cloning assumptions forge quantum crypto","Unlearnable quantum states ground new crypto primitives","Hardness of learning circuits bakes in quantum security","From circuit-state hardness to OWSGs and commitments"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000825,"raw_usage":{"total_tokens":3641,"prompt_tokens":1016,"completion_tokens":2625,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":2552}},"tokens_in":632,"tokens_out":2625,"duration_ms":17979,"temperature":1.0,"reasoning_tokens":2552,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:29:41.274839+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute or bound $\\mathbb{E}_{C \\gets \\mathcal{C}_n}\\big[C^{\\otimes 2}|0\\rangle\\langle 0|^{\\otimes 2}(C^\\dagger)^{\\otimes 2}\\big]$ for the $n$-qubit 1D brickwork ensemble of depth $\\log^2 n$ with the Clifford-containing gate set; if this differs from the projector onto the symmetric subspace of $(\\mathbb{C}^2)^{\\otimes 2}$, the ensemble is not an exact 1-design and Claim 4.9's correctness derivation fails as written.","supporting_citations":[],"review_version":1}