{"id":"cb7f3810-d3f8-427a-9ec9-223713300451","arxiv_id":"2505.23978","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors construct proofs of quantumness whose soundness is unconditional against memory-bounded classical adversaries, using Raz's parity-learning lower bound and bounded-storage interactive hashing.","lead":"This paper designs two protocols that let a classical computer verify that a quantum machine is really quantum, without relying on unproven computational hardness assumptions. Instead, the security rests on a physical assumption: the adversarial classical machine has limited memory.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Soundness of Protocol 1 rests on a time-free reading of Raz's parity-learning bound; Raz's theorem is a time-space tradeoff, so unbounded-time small-memory adversaries are not excluded.","rationale":"The reader's weakest assumption was exactly the correctness of Lemma 5; I agree. The validity of both Theorems 1 and 15 hinges on this. The paper's own abstract emphasizes 'no restrictions on runtime,' and Section 2.1 defines memory-bounded algorithms without time bound. The proof imports Raz's result as a black box. If Raz's actual statement is a time-space tradeoff, then the adversary model in the paper is too strong: a small-memory adversary may take exponential time, which the protocol permits. No part of the analysis in Section 3 addresses this. The concrete check is straightforward and decisive.","tokens_in":29012,"tokens_out":40601,"duration_ms":416047,"concrete_test":"Locate the statement of Raz's main theorem in 'Fast Learning Requires Good Memory' (FOCS 2016 / JACM 2018) and check whether it contains a time hypothesis such as T ≤ 2^{delta n} or a constraint ST ≥ n^2/20. If it does, Lemma 5 is misstated; the soundness proof of Lemma 17 must be re-run with a polynomial-time classical adversary or a genuinely time-independent incompressibility argument. If the theorem is time-free, the concern is vacuous and no change is needed.","verdict_should_be":"REJECT","load_bearing_attack":"The paper's central claim is that soundness holds unconditionally against any classical prover whose memory is below n^2/20, with no runtime restriction (Theorem 1, Section 1.1; Protocol 1; Lemma 17). The only cryptographic ingredient is Lemma 5, attributed to Raz [Raz18], which states exactly this time-free memory lower bound. However, the published Raz result is a time-space tradeoff: for parity learning with n variables, any algorithm using memory S and time T requires either S ≥ n^2/20 or T ≥ 2^{Omega(n)}. It does not assert that a small-memory algorithm with unbounded time cannot learn. Since Section 2.1 explicitly allows the adversary's runtime to be unbounded, Lemma 5 is not derivable from the cited theorem. The reduction in Lemma 17 constructs a parity learner A whose memory is space(P*) + O(n log n) but whose runtime is inherited from P* and may be unbounded; it therefore only contradicts the time-free Lemma 5, not Raz's actual tradeoff. If an adversary can spend 2^{Omega(n)} time with O(n) memory (which the tradeoff leaves open), it can recover s, compute t=(s,-1), determine the hidden bit c from r·t, and answer the CHSH test with probability 1, destroying the claimed constant gap. Thus the central theorem is unsupported as stated. This is not an internal inconsistency in the protocol's algebra; it is a load-bearing assumption about the external result that the paper neither proves nor states accurately.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes two proofs of quantumness (PoQ) in the bounded-storage model, where soundness is claimed unconditionally against adversaries whose memory is bounded but whose runtime is unrestricted. Protocol 1 (Section 3) is a CHSH-type protocol built on the linear function x↦Ax with A=(V,Vs); the verifier streams the rows of A one at a time and the prover coherently evaluates them. The paper claims completeness cos^2(π/8) and soundness 3/4+ε against any classical prover with less than n^2/20 bits of memory, based on Lemma 5, attributed to Raz. Protocol 2 (Section 4) uses interactive hashing and a stitching amplification to achieve an exponential gap, with classical soundness against m-bit-memory provers and quantum soundness against m-qubit provers; an appendix sketches how the quantum soundness leads to classical verification of BQP. The paper is clearly written and the high-level template is appealing, but the soundness proof of Protocol 1 rests on a misreading of the cited memory lower bound.","tokens_in":29364,"tokens_out":48020,"duration_ms":506645,"significance":"If the results are established, this would be a notable conceptual advance: PoQ protocols whose soundness does not rely on computational conjectures, only on a memory bound on the prover, with a very simple honest prover for Protocol 1 and an exponential gap for Protocol 2. The coherent implementation of interactive hashing and the stitching argument are elegant, and the quantum-soundness lemma (Lemma 29) together with the BQP-verification appendix indicate a promising route to classical verification of quantum computations in the bounded-storage model. The main caveat is the unsupported time-free parity-learning lower bound; this is fixable in principle but is currently load-bearing for the paper's central claim.","major_comments":[{"comment":"Lemma 5 is attributed to [Raz18] as a time-free memory lower bound for parity learning, but the published result is a time-space tradeoff: for memory S < n^2/20, the required time is 2^{Ω(n)}, and the theorem does not bound the success probability of an adversary with small memory when runtime is unrestricted. Since Section 2.1 explicitly allows the adversary's runtime to be unbounded, and the reduction in Lemma 17 constructs a parity learner whose runtime is inherited from P* and may therefore be unbounded, the soundness of Protocol 1 (Theorem 15) is not established by the cited theorem. The authors should either prove a genuine one-pass streaming memory lower bound for parity learning with the claimed constant, cite a correct source for such a bound, or change the adversary model to include a runtime restriction (which would weaken the advertised 'unconditional' claim). As written, this is a load-bearing gap.","section":"Section 3, Lemma 5 and Theorem 15"},{"comment":"The set B^j_ω is defined in terms of W_post, which includes the interactive-hashing transcript and therefore depends on the indices v^j_0, v^j_1 that are outputs of that transcript, whereas Definition 21's (α,β)-security is stated for a fixed set B chosen before the protocol. The proof invokes Theorem 22 on this data-dependent set with the sentence 'Thus, by Theorem 22', but the applicability is not immediate. The authors should either explicitly prove that the interactive-hashing transcript is conditionally independent of U^j given W_pre^j, so that conditioning on W_post does not alter the relevant entropies, or provide a direct argument for adaptive sets. This step is needed for the classical soundness of Protocol 2 and deserves a complete justification.","section":"Section 4.4, Claim 27"}],"minor_comments":[{"comment":"The text says an attempt of the 1-bit claw generation succeeds with probability 1/k^2, but for a uniformly random 2-to-1 hash the probability that a fixed distinct pair {v_0,v_1} is the preimage pair is 1/(k-1), not 1/k^2. The stated O(λk^3) runtime is therefore conservative, but the calculation should be corrected.","section":"Section 4.3, complexity calculation"},{"comment":"Lemma 24 states that the residual state is the claw state 'with probability 1', but the protocol may abort in Step 1.3 and restart; the statement should condition on the protocol not aborting.","section":"Lemma 24, correctness statement"},{"comment":"There are several typos and inconsistencies, including 'paramter' in Protocol 1, 'execution execution' in Theorem 2, 'apriori' in Section 1.2, and the abstract's 'Raz's memory lower bound for matrix inversion' versus the 'learning parities' terminology used in Section 3.","section":"Throughout"},{"comment":"The definition of memory-bounded algorithms should state explicitly whether the memory bound counts the transcript/input and how it applies to quantum registers; this matters for comparing the honest prover's n+2 qubits with an adversary's m qubits or bits.","section":"Section 2.1"},{"comment":"The BQP-verification appendix is a proof sketch; the paper should clearly mark which reductions are fully formal and which require additional work, particularly the memory-preservation claims and the transition from inverse-polynomial to negligible claw-finding soundness.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The main reason for not recommending reject is that the Raz issue is potentially repairable: a one-pass communication-complexity lower bound for parity learning with the stated parameters would restore Theorem 1, and the high-level framework is sound. However, the current text is not acceptable as is, and the 'unconditional' framing should be carefully qualified. I would ask the authors to consult the exact statement of Raz's result and to either prove or correctly cite a time-free streaming lower bound, and to clarify the adaptive-set issue in Claim 27 before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. The paper has a genuinely new idea: in the bounded-storage model, replace the trapdoor claw-free function in a proof-of-quantumness with a random linear map that is 2-to-1 and memory-hard for parity learning, and use a row-span trick so the verifier never has to invert the matrix. That is a clever workaround and the protocol is remarkably simple. The second thing is less pleasant: the main soundness theorem, Theorem 1, is not supported by the cited mathematics. The paper's Lemma 5 states Raz's parity-learning lower bound as a time-free memory bound. Raz's actual FOCS 2016 result is a time-space tradeoff. It says any parity-learning algorithm needs either about n^2/20 memory or 2^{Omega(n)} time; it does not rule out an O(n)-memory algorithm that runs in exponential time. The paper's model explicitly allows unbounded runtime, so such an adversary is allowed. That adversary can recover s in 2^{O(n)} time with O(n) memory, compute t = (s, -1), determine the hidden bit from r·t, and answer the CHSH test with probability 1. The constant gap between completeness and soundness evaporates. This is not a gap in a sub-claim; it is the load-bearing assumption for Protocol 1.\n\nThe second protocol is in better shape. Its classical soundness follows the DQW23 incompressibility framework, which is genuinely time-free, and the coherent interactive-hashing lemma generalizes Morimae-Yamakawa cleanly. The quantum-soundness analysis is dense and I have not verified every step, but the approach looks sound. The appendix on BQP verification is explicitly a sketch, so treat it as such. The abstract's 'exponential gap' also overclaims: the honest prover uses polylog(n) qubits and the adversary is bounded by n bits, so the gap is n/polylog(n), which is super-polynomial but not exponential in n unless you parameterize by log n.\n\nAll that said, this is a paper worth engaging with. The ideas are novel, the writing is clear, and the citations are honest. But Theorem 1 cannot survive without either a time-free memory lower bound or a model that restricts runtime. I would send it to peer review with a specific request to check Lemma 5 against Raz's paper, and to weigh whether Protocol 1 can be repaired or should be removed. Protocol 2 alone is a solid contribution.","headline":"Novel bounded-storage proof-of-quantumness constructions, but Theorem 1 rests on a misreading of Raz's time-space tradeoff; Protocol 2 is the salvageable half.","tokens_in":29877,"tokens_out":5155,"would_cite":true,"duration_ms":52915,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","94A60"],"pacs":["03.67.-a","03.67.Lx"],"model":"deepseek-v4-flash","headline":"This paper constructs proofs of quantumness whose security holds unconditionally as long as the malicious prover's memory is bounded, with one protocol requiring just n+2 qubits for the honest prover.","keywords":["proof of quantumness","bounded storage model","claw generation","interactive hashing","parity learning","memory lower bound","quantum verification","unconditional soundness"],"falsifier":"To refute Protocol 1's soundness, exhibit a classical algorithm that uses just over $n^{2}$/20 bits of memory and finds s from the parity samples with probability significantly better than O($2^{{-alpha n}}$), or find a constant-factor violation of Raz's lower bound. For Protocol 2, a classical or quantum adversary that stores more than m bits and can still output both claw values with non-negligible probability would falsify the claimed claw-finding hardness; concretely, one could attempt to compress the streamed random bits so that the two indices and their values are recoverable from m-bit storage.","tokens_in":1920,"feed_emoji":"🔬","tokens_out":2303,"duration_ms":47827,"temperature":0.7,"pith_summary":"This paper proposes two proofs of quantumness (PoQ) in which a classical verifier checks that a quantum device performed a computation infeasible for any classical machine, with soundness that does not rely on computational assumptions. Instead, security holds unconditionally against any classical adversary whose persistent memory is bounded below a stated threshold, while the honest prover needs only a small quantum memory (n+2 qubits in the first protocol, polylog qubits in the second). The first protocol is a simple parity-based construction whose soundness follows from Raz's memory lower bound for learning parities, giving a quadratic gap between honest and adversarial memory. The second protocol, built from interactive hashing in the bounded-storage model, achieves an exponential gap and also yields claw generation with quantum soundness. If correct, these are the first PoQ protocols whose security is not conditional on computational conjectures, and they provide a path toward classically verifying quantum computation in the bounded-memory setting.","feed_headline":"Quantumness can be verified against memory-limited cheaters","feed_subtitle":"New protocols let a classical verifier test a small quantum device while classical attackers are limited only by memory.","key_machinery":"The load-bearing mechanism is claw generation: an interactive protocol at the end of which the honest prover holds a superposition (|x0> + |x1>)/sqrt(2) of two values that the verifier knows but any memory-bounded adversary cannot recover both of. For Protocol 1, the claw-free function is the linear map x -> Ax with A = (V, Vs); the verifier streams rows of A one at a time and uses a random linear combination of rows to compute inner products without storing the whole matrix, while soundness reduces to Raz's memory lower bound for parity learning. For Protocol 2, the claw is produced through coherent interactive hashing over a streamed random bitstring, combined with a stitching operation that turns many \"1-bit claws\" into a single hard claw; soundness follows from the interactive-hashing security and an incompressibility argument against memory-bounded adversaries.","core_discovery":"The central claim is that a classical verifier can reliably distinguish a quantum prover from any classical prover, provided the classical prover's memory is strictly bounded, with no other restriction on its runtime. For Protocol 1, an honest quantum prover using n+2 qubits makes the verifier accept with probability $cos^{2}$(pi/8), while any classical attacker using fewer than $n^{2}$/20 memory bits succeeds with probability at most 3/4 + O($2^{{-n}}$); thus there is a constant completeness-soundness gap. Protocol 2 amplifies the gap to exponential (soundness 3/4 + 2^{-$\\Omega$($\\lambda$)}) while the honest parties use only polylog memory, assuming the attacker stores less than m bits. The paper also proves quantum soundness for the claw-generation protocol underlying Protocol 2, showing that a quantum attacker with bounded memory cannot output both preimages of the generated claw, and sketches how this yields classical verification of BQP computations that is unconditionally secure in the bounded-storage model.","pith_inferences":["The security guarantee is conditional on the adversary's memory being genuinely capped, including the inability to offload information to external storage outside the model; a device that can write to a large classical disk would break the soundness threshold.","Protocol 1's reliance on Raz's bound suggests that memory-hardness, not just time complexity, can be a practical resource for quantum advantage; a natural testable extension is to benchmark quantum devices against classical solvers with tightly capped memory in the parity-learning task.","The protocols could inspire a new class of verifiable quantum experiments where the verifier does not need to trust any computational hardness assumption, analogous to how the bounded-storage model was used for unconditionally secure cryptography.","The exponential-gap protocol indicates that even a tiny honest memory (polylog qubits) can certify quantumness against adversaries with much larger but still bounded memory, which may be relevant for device certification with minimal hardware requirements."],"forward_implications":["If the protocols are sound as claimed, they supply PoQ schemes whose security does not depend on unproven computational conjectures, only on a memory bound for the adversary.","The first protocol can be implemented with one-qubit Hadamard and CNOT gates plus a single non-Clifford gate, making it potentially feasible on near-term small quantum devices.","The second protocol demonstrates that the gap between honest and adversarial memory can be made exponential, with honest parties using only polylogarithmic memory.","Quantum soundness of the claw-generation protocol offers a route to classically verifying arbitrary BQP computations in the bounded-storage model, without computational assumptions.","The completeness and soundness gaps are constant (or tunable via repetition), so the protocols can be repeated to amplify confidence while preserving the memory-based security guarantee."],"supporting_citations":[{"why":"Supplies the classical memory lower bound for learning parities that underlies the soundness of Protocol 1.","marker":"[Raz18]"},{"why":"Provides the bounded-storage-model techniques and incompressibility arguments used to build Protocol 2 with exponential gap.","marker":"[DQW23]"},{"why":"Establishes the general claw-generation-to-PoQ template and the soundness analysis that Protocol 2 instantiates.","marker":"[BGK+23]"},{"why":"Shows the implication from claw generation with quantum soundness to classical verification of BQP, which the paper adapts for memory-bounded adversaries.","marker":"[BK24]"},{"why":"Provides the coherent implementation of interactive hashing that lets a quantum prover maintain a superposition during the claw-generation protocol.","marker":"[MY23]"},{"why":"Supplies the constant-round interactive hashing protocol used as the building block for interactive hashing in Protocol 2.","marker":"[DHRS04]"},{"why":"Introduces interactive hashing with the 2-to-1 hash and security properties that the protocol relies on.","marker":"[NOVY92]"},{"why":"Provides the Goldreich-Levin extractor used to convert an advantage in predicting an inner product into recovery of the hidden value with only O(l log l) memory overhead.","marker":"[GL89]"},{"why":"Supplies the plug-in lemma used in the quantum-soundness analysis to bound the trace distance when substituting uniformly random bits for streamed bits.","marker":"[BBK22]"}],"fun_headline_variants":["Memory-bounded classical attackers can't fake quantumness","Quantumness test: only memory bound on classical prover","Unconditional quantumness check vs memory-limited cheaters","Classical verifier, quantum prover: memory bound suffices","Quantumness proven unconditionally when prover's memory is bounded"],"cache_read_input_tokens":32000,"weakest_assumption_plain":"The security statements collapse if the adversary can store information outside the declared memory cap, or if the memory cap is even slightly larger than $n^{2}$/20 in Protocol 1; the proofs assume the adversary's persistent state is strictly bounded and that Raz's parity-learning lower bound holds as stated.","fun_headline_variants_meta":{"raw":{"variants":["Memory-bounded classical attackers can't fake quantumness","Quantumness test: only memory bound on classical prover","Unconditional quantumness check vs memory-limited cheaters","Classical verifier, quantum prover: memory bound suffices","Quantumness proven unconditionally when prover's memory is bounded"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001912,"raw_usage":{"total_tokens":7496,"prompt_tokens":957,"completion_tokens":6539,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":6457}},"tokens_in":573,"tokens_out":6539,"duration_ms":42610,"temperature":1.0,"reasoning_tokens":6457,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:41:19.825707+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To refute Protocol 1's soundness, exhibit a classical algorithm that uses just over $n^{2}$/20 bits of memory and finds s from the parity samples with probability significantly better than O($2^{{-alpha n}}$), or find a constant-factor violation of Raz's lower bound. For Protocol 2, a classical or quantum adversary that stores more than m bits and can still output both claw values with non-negligible probability would falsify the claimed claw-finding hardness; concretely, one could attempt to compress the streamed random bits so that the two indices and their values are recoverable from m-bit storage.","supporting_citations":[],"review_version":1}