{"id":"245b8fa6-2784-40a9-9c5a-3d5ed497b870","arxiv_id":"2411.11805","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Witness cloning is hard unless BQP contains NP, assuming a new conjecture that cloning hidden maximally entangled states reveals a circuit for the hidden subspace.","lead":"The paper builds quantum verification circuits whose unique accepted witnesses are hidden maximally entangled states defined by Kronecker coefficients, and shows that an efficient cloner for these states would, under a new conjecture, imply a quantum algorithm for an NP-hard problem. This gives a conditional route to proving that witness cloning is hard unless BQP contains NP.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main hardness theorem (Thm 8) is conditional on Conjecture 2, which is unproven and explicitly acknowledged as unfinished; since [NZ24] rules out black-box proofs, the conjecture may be false, and without it the cloning-to-generation step collapses.","rationale":"The reader's weakest-assumption analysis identifies Conjecture 2 as the load-bearing point, and I agree. Theorem 8 is the paper's central claim, and its proof has exactly one non-black-box gap: the step from an efficient cloner for a hidden maximally entangled state to an efficient generator for its support. The paper itself labels the work unfinished and cites [NZ24] showing that no relativizing proof can fill this gap. This makes Conjecture 2 not merely unproven but potentially false, and no amount of correct representation theory repairs that. The secondary issue with Eq. 30 is real but likely repairable, so it does not change the conditional verdict. The honest assessment is that the paper proves an unconditional hardness-of-generation result and a conditional hardness-of-cloning result whose condition is currently unsupported. That matches the reader's CONDITIONAL verdict, so no verdict change is warranted.","tokens_in":22871,"tokens_out":30884,"duration_ms":308644,"concrete_test":"Attempt to construct a counterexample to Conjecture 2: for a small symmetric group (say S_4), pick a subspace Π=Ξ_λ with a=1, write the verification circuit explicitly, and use numerical search over small quantum circuits to find a cloner C for |Φ_Π> that does not contain an efficient generating circuit for Π. If such a C exists, Conjecture 2 is false and Theorem 8 fails; if the search exhausts the space and finds no such C, the conjecture's core step is supported. Separately, recompute Lemma 4's Eq. 30 with the standard phase-estimation formula to confirm the soundness bound; if the bound exceeds 8/9, the constructed verifier does not satisfy the hypotheses of Conjecture 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 8: assuming Conjecture 2 and BQP ⊉ NP, no efficient algorithm clones the states passing the (μ⊗ν,λ)-verification algorithm when a_{μνλ}=1. The entire force of the theorem rests on Conjecture 2 (§6.2), which asserts that an efficient cloner for a hidden maximally entangled state |Φ_Π> uniquely accepted by a verification circuit can be transformed into an efficient circuit producing a state in Π. The paper gives no proof of this conjecture. Section 7.1 explicitly describes the work as 'unfinished' and offers only intuition: a cloner must disentangle the original registers, and running the disentangler backwards would generate a state in Π. The paper also cites Nehoran–Zhandry [NZ24], who construct a quantum oracle relative to which cloning of verifiable states is easy while state generation is hard; this rules out any black-box proof of Conjecture 2 and leaves open the possibility that the conjecture is false in the real world. If Conjecture 2 fails, a cloner might exist for the Kronecker-coefficient verifier even though BQP ⊉ NP, so Theorem 8 would not follow. A secondary defect is that the verification circuits used in Theorem 8 are asserted to have soundness ≤8/9, but the proof of Lemma 4 relies on the phase-estimation acceptance formula 1/2 + 1/2 |⟨φ|U|φ⟩|² (Eq. 30), which is not the standard 1-bit phase-estimation probability (1/2 + 1/2 Re⟨φ|U|φ⟩); the soundness bound is thus not rigorously derived as written, though it is likely repairable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational hardness of cloning witnesses for quantum verification circuits. It constructs a family of verification algorithms based on weak Fourier sampling for representations of the symmetric group, whose accepting states are maximally entangled states over hidden subspaces associated with Kronecker coefficients. The main result, Theorem 8, shows that, assuming an unproven conjecture (Conjecture 2) about cloning such hidden maximally entangled states and assuming BQP ⊉ NP, no efficient quantum algorithm can clone the witnesses of these verification circuits when the relevant Kronecker coefficient equals 1. The paper also proves conditional hardness of state generation for this family, connecting to NP-hardness of Kronecker coefficient positivity.","tokens_in":23201,"tokens_out":26534,"duration_ms":231314,"significance":"If the technical gaps are repaired, the paper would provide a novel complexity-theoretic reduction: hardness of witness cloning follows from a concrete conjecture about maximally entangled states over hidden subspaces, rather than from cryptographic assumptions or oracles. The connection between quantum state complexity and representation-theoretic multiplicities is interesting, and the verification construction via weak Fourier sampling is elegant. The paper is commendably transparent about the unproven Conjecture 2 and the non-relativizing barrier from [NZ24]. However, the correctness of the verification analysis currently has gaps, and the main theorem remains conditional, so the impact is contingent on both the conjecture and the repair of the technical arguments.","major_comments":[{"comment":"The acceptance probability for the 1-bit phase estimation circuit is stated as 1/2 + 1/2 |⟨ψ|V|ψ⟩|², but the standard formula for the circuit described (ancilla in |0⟩, Hadamard, controlled-V, Hadamard, measure) is 1/2 + 1/2 Re⟨ψ|V|ψ⟩. Since V is unitary and not necessarily Hermitian, the two formulas differ. Lemma 4's proof uses Eq. (30) to translate the acceptance probability into a bound on 1−|⟨B,E(B)⟩|²; with the correct formula the bound would be on 1−Re⟨B,E(B)⟩. Because E is an orthogonal projection under the Hilbert–Schmidt inner product, Re⟨B,E(B)⟩ = ⟨B,E(B)⟩ = ‖E(B)‖² ≥ 0, so the qualitative closeness conclusion can likely be recovered, but the proof as written is incorrect and needs to be revised.","section":"§5.2, Eq. (30)"},{"comment":"The proof asserts that the (μ⊗ν,λ)-verification algorithm has completeness 1 and soundness ≤ 8/9, citing Corollary 5. Corollary 5 is a closeness statement saying that states passing with probability 1−ε are close to the accepting subspace; it does not by itself yield the spectral gap required by Definition 1 for soundness 8/9. The authors need to derive an explicit upper bound on the acceptance probability of states orthogonal to the accepting subspace, accounting for the rejection in the weak Fourier sampling step and the internal state test. The constant 8/9 is used in Conjecture 2, so this is load-bearing.","section":"§6.2, Theorem 8 proof"},{"comment":"The claim that the accepting subspace has dimension exactly a_{μνλ} is inconsistent with the characterization in Lemma 4 and Corollary 5, where the accepting states are of the form |E⟩⊗|Φ+⟩ with |E⟩ ∈ C^{a²}, giving dimension a². For a=1 the two statements agree, so Theorem 8's uniqueness may be unaffected, but Theorem 6's dimension statement is incorrect as written. Please correct the dimension and the definition of D_λ in Eq. (12), which currently spans only the diagonal block states.","section":"§6.1, Theorem 6 and §5.2, Corollary 5"},{"comment":"The statement that deciding whether a_{μνλ} is 0 or 1 (promised one of the two) is UNIQUE−NP-hard is used for the Valiant–Vazirani reduction in the proofs of Corollary 7 and Theorem 8, but no proof or reference is given. The cited NP-hardness of positivity [IMW17] does not automatically yield hardness of the promise problem; a parsimonious reduction or a separate argument is needed. Please provide a reference or proof.","section":"§6.1, Theorem 6 and Corollary 7 proof"}],"minor_comments":[{"comment":"The phrase 'BQP does not equal QMA' is used in the abstract and introduction, but the paper's actual assumption is BQP ⊉ NP; these are not equivalent statements, and the wording should be aligned with the formal results.","section":"Abstract and §1"},{"comment":"The definition of D_λ as the span of the block-wise maximally entangled states and its stated dimension a_{ρ→λ} are inconsistent with Lemma 4, which allows arbitrary superposition of blocks. Please align the notation and clarify what subspace is actually characterized.","section":"§5.2, Eq. (12)"},{"comment":"The footnote text appears incomplete in the manuscript ('one.sup'); please provide the full sentence.","section":"Footnote 1"},{"comment":"The circuit diagram in the proof of Fact 1 is difficult to parse; please redraw it for clarity.","section":"Appendix B, proof of Fact 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about Conjecture 2 being unproven and appropriately cites the non-relativizing barrier from [NZ24]. The main technical concerns are the incorrect phase-estimation probability in Eq. (30), the unsubstantiated soundness claim in Theorem 8, and the dimension inconsistency between Theorem 6 and Lemma 4. These are likely repairable without changing the overall approach, but they are load-bearing and require a careful rewrite. The UNIQUE−NP-hardness claim for the promise version of Kronecker positivity also needs a supporting reference or proof. If the authors can fix these points, the paper could make a nice contribution to the witness-cloning literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: the genuinely solid part is the unconditional hardness of state generation for their representation-theoretic verifier. The cloning hardness is a well-designed but explicitly unfinished conditional theorem resting on Conjecture 2, which the authors openly admit they cannot prove.\n\nWhat's new: they connect NP-hardness of Kronecker coefficients to a family of hidden maximally entangled states, building a verification circuit whose unique accepting states are exactly such states when the Kronecker coefficient is 1. Theorems 6 and 7 follow from known hardness and are clean. That part is a real, citable contribution.\n\nSoft spots, in order of severity. First, Conjecture 2 is the load-bearing step for Theorem 8, and there's no proof, only intuition about disentangling. The authors themselves call the work unfinished and cite NZ24, which rules out any black-box proof, so the conjecture requires a genuinely non-relativizing argument. If it fails, the cloning-to-generation reduction collapses. Second, the claimed soundness of the verification algorithm is asserted as ≤8/9 without a derivation, and the acceptance probability in Eq. (30) has 1/2 + 1/2|⟨B, G(B)⟩|², which does not match standard 1-bit phase estimation; that should involve the real part, not the squared magnitude. This looks repairable and probably doesn't sink the construction, but it needs a fix before the bounds are credible.\n\nCitation pattern is fine. The self-citations to BCG+24 and LH24 are to published work used as ingredients, not as a crutch. Nobody is fitting parameters or assuming the target result.\n\nThis paper is for quantum complexity people and quantum money types. It deserves a serious referee: the state-generation result is worth publishing even if Conjecture 2 stays open, and the conjecture itself is a sharp, well-motivated target for future work. A referee should ask for a corrected derivation of the soundness gap and a careful discussion of what evidence beyond intuition supports Conjecture 2. I would send it to peer review rather than desk reject, but the main theorem's status should be presented honestly as conditional.","headline":"Honest, well-scoped note: the Kronecker-based state-generation hardness is solid, but the headline cloning theorem is conditional on a believable yet unproven conjecture, and there's a likely typo in the phase-estimation formula that needs fixing.","tokens_in":23753,"tokens_out":2108,"would_cite":true,"duration_ms":22302,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","20C30","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This note shows that, assuming an unproven conjecture about cloning hidden maximally entangled states, efficient witness cloning would put NP inside BQP.","keywords":["witness cloning","no-cloning theorem","Kronecker coefficients","hidden subspace","maximally entangled state","weak Fourier sampling","BQP vs NP","symmetric group representation"],"falsifier":"Find an efficient quantum circuit that clones the specific hidden maximally entangled states $|\\Phi_\\Pi\\rangle$ constructed in the paper while provably failing to generate any state in $\\Pi$; such a circuit would falsify Conjecture 2 and remove the main theorem's premise.","tokens_in":22655,"feed_emoji":"⚛️","tokens_out":8182,"duration_ms":71779,"temperature":0.7,"pith_summary":"This note tries to prove that efficiently cloning a quantum witness—a state accepted by a verification circuit—is as hard as solving NP problems, rather than merely hard for information-theoretic reasons. The authors build a family of verification circuits from representations of the symmetric group, whose unique accepted states are maximally entangled states over hidden subspaces. Deciding whether the relevant Kronecker coefficient is positive is NP-hard, so generating these states is hard unless BQP contains NP. Their main theorem shows that an efficient cloner for this family would also generate states in the hidden subspace, provided Conjecture 2 holds; combined with the Valiant–Vazirani reduction, this would imply BQP ⊇ NP. If correct, the paper reduces the hardness of witness cloning to a single, explicitly stated conjecture about maximally entangled states over hidden subspaces.","feed_headline":"Under a new conjecture, cloning a quantum witness means NP lies in BQP","feed_subtitle":"One unproven conjecture stands between witness cloning and a collapse of NP into BQP.","key_machinery":"The load-bearing object is the weak Fourier sampling projector $\\Xi_\\lambda^{(\\rho)} = \\frac{d_\\lambda}{|G|}\\sum_{g\\in G} \\chi_\\lambda(g)^* \\rho(g)$, which projects onto the $\\lambda$-isotypic component of a representation $\\rho$. For $\\rho = \\rho_\\mu \\otimes \\rho_\\nu$ of $S_n$, its nonzero-ness coincides with positivity of the Kronecker coefficient $a_{\\mu\\nu\\lambda}$, and the paper adds an 'internal state testing' step that forces the accepted state to be a maximally entangled state across each block. Together these tests produce a verification circuit whose unique accepting state is the hidden maximally entangled state $|\\Phi_\\Pi\\rangle$ whenever $a_{\\mu\\nu\\lambda}=1$. This is the mechanism that converts NP-hardness of Kronecker coefficients into a candidate hard-to-clone family.","core_discovery":"The central discovery is a reduction from witness cloning to state generation over hidden subspaces, routed through representation theory. For the symmetric group $S_n$, the weak Fourier sampling projector $\\Xi_\\lambda$ associated with the representation $\\rho_\\mu \\otimes \\rho_\\nu$ has dimension $a_{\\mu\\nu\\lambda} d_\\lambda$, and it is nonzero exactly when the Kronecker coefficient $a_{\\mu\\nu\\lambda}$ is positive. Because deciding positivity is NP-hard, the subspace is hidden, and the state $|\\Phi_\\Pi\\rangle$ defined as the maximally entangled state over $\\Pi$ is the unique state accepted by the constructed $(\\mu\\otimes\\nu,\\lambda)$-verification algorithm when $a_{\\mu\\nu\\lambda}=1$. Theorem 8 states that, assuming Conjecture 2 and BQP ⊉ NP, no efficient algorithm clones these states; otherwise an efficient cloner would yield a circuit generating a state in $\\Pi$, hence a BQP algorithm for UNIQUE-NP, and by Valiant–Vazirani, BQP ⊇ NP.","pith_inferences":["If Conjecture 2 holds, this construction yields the first worst-case complexity-theoretic evidence that witness cloning is hard, complementing existing average-case cryptographic and oracle results.","The template generalizes: any family of projectors whose positivity is NP-hard and whose accepting states are maximally entangled over hidden subspaces would give the same cloning-hardness reduction.","A natural testable extension is to compute small Kronecker coefficient instances and search for explicit cloning circuits for the associated $|\\Phi_\\Pi\\rangle$; a successful cloner that does not reveal a state in $\\Pi$ would falsify Conjecture 2.","If average-case hardness of Kronecker coefficients were ever established, the same measurement over $|\\Phi_+\\rangle$ could be turned into a quantum lightning construction, as the paper notes as a possibility."],"forward_implications":["If the main theorem holds, an efficient cloner for the constructed family would put NP inside BQP, so witness cloning is at least as hard as deciding NP under the stated assumptions.","The verification circuits for $a_{\\mu\\nu\\lambda}=1$ have completeness 1 and soundness $\\le 8/9$, making them valid verifiers whose unique witnesses are hidden maximally entangled states.","A proof of Conjecture 2 cannot be a black-box reduction; any successful proof must exploit the circuit description of the verifier.","The result reduces the hardness of witness cloning to the hardness of generating states in hidden subspaces, narrowing the problem to a single structural conjecture.","For the family with $a_{\\mu\\nu\\lambda}=1$, state generation is already impossible under BQP ⊉ NP (Corollary 7), and the new result extends this to cloning."],"supporting_citations":[{"why":"Supplies the NP-hardness of deciding whether the Kronecker coefficient is positive, which drives the hardness of state generation.","marker":"[IMW17]"},{"why":"Establishes Kronecker coefficients as #BQP quantities and motivates the representation-theoretic approach.","marker":"[BCG+24]"},{"why":"Proves no black-box proof of Conjecture 2 is possible, showing why the conjecture needs non-relativizing techniques.","marker":"[NZ24]"},{"why":"Gives the randomized reduction from NP to UNIQUE-NP used to conclude BQP ⊇ NP.","marker":"[VV86]"},{"why":"Provides the efficient quantum Fourier transform over $S_n$, needed for the efficient verification circuit.","marker":"[Bea97]"},{"why":"Supplies the generalized phase estimation method that implements weak Fourier sampling.","marker":"[Har05]"},{"why":"Gives a prior oracle separation showing query hardness of cloning subset states, providing context and a baseline.","marker":"[AC12]"}],"fun_headline_variants":["Cloning quantum witnesses could collapse NP into BQP","New conjecture ties witness cloning to NP vs BQP","Hidden subspace cloning blocked by Kronecker complexity","Efficient witness cloning would put NP in BQP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Conjecture 2: if an efficient cloner exists for a hidden maximally entangled state uniquely accepted by a verification circuit, then an efficient circuit exists for generating a state in the support of the hidden subspace; the paper gives intuition but no rigorous derivation, and notes that no black-box proof can exist.","fun_headline_variants_meta":{"raw":{"variants":["Cloning quantum witnesses could collapse NP into BQP","New conjecture ties witness cloning to NP vs BQP","Hidden subspace cloning blocked by Kronecker complexity","Efficient witness cloning would put NP in BQP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000237,"raw_usage":{"total_tokens":1471,"prompt_tokens":871,"completion_tokens":600,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":538}},"tokens_in":487,"tokens_out":600,"duration_ms":5892,"temperature":1.0,"reasoning_tokens":538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:09:00.587781+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find an efficient quantum circuit that clones the specific hidden maximally entangled states $|\\Phi_\\Pi\\rangle$ constructed in the paper while provably failing to generate any state in $\\Pi$; such a circuit would falsify Conjecture 2 and remove the main theorem's premise.","supporting_citations":[],"review_version":1}