{"id":"20f603e0-b60e-4b43-ac5a-2ae996b8f339","arxiv_id":"2510.08473","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Using two-level amplitude amplification over random-product-code center points, 3-tuple lattice sieving runs in quantum time 2^{0.2846d} with memory 2^{0.1887d}, improving the previous 2^{0.3098d}.","lead":"Lattice sieving is how cryptanalysts estimate the real cost of breaking post-quantum crypto. This paper lowers the quantum cost of one flavor of sieving from 2^{0.3098d} to 2^{0.2846d}, making it the fastest known bounded-memory quantum attack on the Shortest Vector Problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 3.1 uses a numerical bound on W(θ,α|α) that contradicts Lemma 2.8; the claimed 2^{0.284551d} exponent is not established as written.","rationale":"The reader's weakest_assumption identifies the uniform heuristic as the main concern, but the paper is explicit about that being heuristic and separates it from Theorem 3.1. The more load-bearing issue for the paper's central rigorous claim is the numerical inconsistency in the proof of Theorem 3.1: the displayed bound W(θ,α|α) ≥ 2^{−0.136318d} appears incompatible with Lemma 2.8 for the stated constants. If this is a genuine error, the proof does not establish the claimed time exponent, even if the algorithm idea is sound. The reader did note this inconsistency in the rationale, so there is partial agreement. The appropriate verdict remains CONDITIONAL: the authors should correct the numerical analysis or adjust the parameter claims. A concrete recomputation of Equation (4) with correct values would settle whether the headline exponent survives.","tokens_in":41660,"tokens_out":17864,"duration_ms":114791,"concrete_test":"Independently recompute W(θ,α|α) and W(θ′,α′|α′) using Lemma 2.8 for the stated constants (cosθ=1/3, cosθ′≈1/√3, cosα=0.347606, cosα′=0.427124). Substitute the true values into Equation (4) with m=(27/16)^{d/4+o(d)} and ℓ=(pα/W)(pα′/W′)2^{o(d)}, and determine the resulting exponent. If the exponent is ≤0.284551d, Theorem 3.1 survives with corrected constants; otherwise, the claimed time bound is false and the optimization over (α,α′) must be redone.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is an internal inconsistency in the proof of Theorem 3.1, not the explicitly disclosed uniform heuristic. In the final paragraph of the proof, the authors claim that for cos(α)=0.347606 and cos(θ)=1/3, W(θ,α|α) ≥ 2^{−0.136318d+o(d)}. But Lemma 2.8 gives W(θ,α|α) = (1 − 2cos^2α/(1+cosθ))^{d/2} up to poly(d). Substituting the stated constants: 2cos^2α ≈ 0.24166, 1+cosθ = 4/3, so the base is 1 − 0.18124 = 0.81876; log2(0.81876) ≈ −0.2885, so W ≈ 2^{−0.1443d}. This is smaller than the claimed 2^{−0.1363d}, so the displayed lower bound is false. This bound is used in Lemma 3.16 to verify condition (II) and to evaluate the time complexity in Equation (4). With the correct W, the exponent in Equation (4) may shift; the claimed 2^{0.284551d+o(d)} is not justified by the written proof. A similar numerical check should be performed for the other quoted exponents (pα, pα′, W(θ′,α′|α′)). This is a correctness risk for the paper's main theorem, separate from the acknowledged heuristic gap in the SVP application.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a quantum algorithm for 3-tuple lattice sieving, targeting the k-list problem (Problem 1): given a list of m i.i.d. uniform samples on the unit sphere, find m triples (x,y,z) with ||x−y−z|| ≤ 1. The main result (Theorem 3.1) is a quantum algorithm solving this random-list problem for m = (27/16)^{d/4+o(d)} = 2^{0.1887d+o(d)} in time 2^{0.2846d+o(d)}, using QCRAM and 2^{o(d)} qubits. This improves the previous 2^{0.3098d} quantum exponent for 3-tuple sieving. The algorithm combines nested amplitude amplification with locality-sensitive filtering based on random product codes (RPCs). The SVP application (Heuristic Claim 1) relies on the standard uniform heuristic, which the paper explicitly acknowledges to be technically false but widely used in heuristic sieving. The core theorem for the random-list problem is proved rigorously with detailed pseudocode and a chain of lemmas.","tokens_in":42065,"tokens_out":21362,"duration_ms":137224,"significance":"If the result holds, it is a concrete improvement in the quantum time exponent for low-memory 3-tuple sieve, and it gives the fastest known heuristic quantum SVP algorithm in the 2^{0.1887d}-memory regime. The paper's strengths include: full pseudocode for every subroutine, machine-checkable lemmas for the random-list problem, explicit parameter choices, and a clear separation between the rigorous Theorem 3.1 and the heuristic SVP claim. The use of only 2^{o(d)} qubits is a practical advantage over quantum-walk approaches that need exponential qubit memory. The improvement, while modest, is in line with recent progress in the area.","major_comments":[{"comment":"I checked the numerical concern raised by the stress-test about the bound W(θ,α|α) ≥ 2^{−0.136318d}. The apparent contradiction with Lemma 2.8 stems from a misreading of the three-argument notation. Here W(θ,α|α) means cap angles θ and α with center separation α, not the α=β special case of Lemma 2.8. Using the general formula in Lemma 2.8 with cosθ=1/3 and cosα=0.347606 gives W(θ,α|α) ≈ 2^{−0.13636d}, consistent with the claimed bound. The other quoted exponents (pα, pα′, mW(θ′,α′|α′)) also match direct numerical evaluation up to the stated o(d) terms. The stress-test concern does not land.","section":"§3.6, proof of Theorem 3.1"},{"comment":"The statement of Lemma 3.16 lists the assumption mpθ′ = 2^{o(d)}. For the parameters used in Theorem 3.1, mpθ′ is actually 2^{−Θ(d)} (about 2^{−0.1038d}), not 2^{o(d)}. The proof, however, only needs the weaker condition mpθ′ ≤_d 1, which does hold. This is a wording error in the lemma statement, not a flaw in the argument, but it should be corrected for precision.","section":"§3.6, Lemma 3.16"}],"minor_comments":[{"comment":"The notation W(α,β|θ) with three angular arguments is easy to misread, as happened in review. Consider adding a remark that W(θ,α|α) denotes cap angles θ and α with center separation α, not a permutation of the arguments.","section":"§2.4"},{"comment":"The phrase 'cos(θ′) is so close to 1/√3 that we will without loss of generality assume they are equal' is informal. Since the difference is subexponential, a short justification using the definition of equality up to 2^{o(d)} would strengthen the exposition.","section":"§3.6, proof of Theorem 3.1"},{"comment":"Heuristic 1 is explicitly acknowledged as 'technically incorrect'. This is appropriately candid, but the SVP claim in Heuristic Claim 1 should perhaps be phrased as a conjecture under the uniform heuristic to avoid any ambiguity that it is a theorem.","section":"§4.2"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution to heuristic lattice sieving. The main theorem for the random-list problem appears correct; the only concerns are local and presentational. The stress-test's numerical inconsistency does not survive a careful reading of the W(·) notation. The heuristic nature of the SVP claim is consistent with the state of the art and is disclosed transparently."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper has a real new algorithmic structure for 3-tuple sieving, and the exposition is unusually honest about what is rigorous and what is heuristic. But the proof of the main theorem contains a numerical claim that contradicts the paper's own Lemma 2.8, so the 2^{0.2846d} exponent is not justified as written.\n\nWhat's good: The nested two-level amplitude amplification over precomputed RPC center-point relations is a genuinely new combination. The authors clearly separate the random-list theorem (Theorem 3.1) from the heuristic SVP application (Heuristic Claim 1), and they explicitly flag the uniform heuristic as technically incorrect. The detailed pseudocode and the chain of lemmas around the search phase look careful. This is competent work in an active niche, and the claimed exponent would be a real record if the proof checks out.\n\nThe soft spot is not the heuristic; it's an internal inconsistency in the proof of Theorem 3.1. In the final paragraph, the authors claim W(θ, α|α) ≥ 2^{−0.136318d+o(d)} for cos α = 0.347606 and cos θ = 1/3. Lemma 2.8 gives W = (1 − 2cos²α/(1+cosθ))^{d/2}. Plugging in the constants gives 2cos²α ≈ 0.24166 and 1+cosθ = 4/3, so the base is 0.81876, and log2(0.81876) ≈ −0.2885. That yields W ≈ 2^{−0.1443d}, which is smaller than the claimed 2^{−0.1363d} by a factor 2^{0.008d}. The proof uses this bound to verify condition (II) and to evaluate the time in Equation (4), so the stated complexity does not follow. The same numerical check should be run for p_α, p_α′, and W(θ′,α′|α′). The headline exponent might survive a recomputation, but the written proof does not establish it.\n\nA minor note: the proof of Theorem 3.1 also says cos(θ′) is so close to 1/√3 that they can be treated as equal; that is probably harmless but would merit a line of justification. The uniform heuristic is a domain assumption, not a hidden fitting of the result, and the paper's handling of it is fair.\n\nRecommendation: send it to peer review, but with a clear instruction that the authors must fix the numerical bound and recompute the exponent. The algorithm idea is worth referee time; the current write-up is not correct.","headline":"Genuinely new two-level amplitude amplification for 3-tuple sieving, but the main theorem's proof has a numerical bound contradicted by its own Lemma 2.8; the stated 2^{0.2846d} is not established as written.","tokens_in":42594,"tokens_out":2854,"would_cite":false,"duration_ms":60642,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"A quantum algorithm for 3-tuple lattice sieving runs in 2^{0.2846d} time, improving on the previous 2^{0.3098d}, with memory capped at 2^{0.1887d}.","keywords":["Shortest Vector Problem","lattice sieving","3-tuple sieving","quantum algorithm","amplitude amplification","random product codes","QCRAM","post-quantum cryptography"],"falsifier":"Simulate one sieving round with m = (27/16)^{d/4} random unit vectors and count triples (x,y,z) with ||x−y−z|| ≤ 1; if the observed count is far below the predicted m for d around 100–200, or if correlations among outputs from shared parents reduce the next round's yield, the 2^{0.2846d} attack fails. More directly, test whether the stronger property ⟨x,y⟩ ≈ 1/3 and ⟨(x−y)/||x−y||,z⟩ ≈ √(1/3) holds for m triples at this list size.","tokens_in":41554,"feed_emoji":"🔐","tokens_out":7186,"duration_ms":54588,"temperature":0.7,"pith_summary":"This paper aims to show that the quantum time cost of 3-tuple lattice sieving can be reduced from 2^{0.3098d} to 2^{0.2846d} while keeping the memory requirement at the minimal 2^{0.1887d}. The improvement matters because the Shortest Vector Problem (SVP) in high-dimensional lattices underpins post-quantum public-key cryptography; faster attacks help calibrate security parameters. The algorithm solves the 'find many triples' subproblem: given a list of m uniform unit vectors, find m triples (x,y,z) with ||x−y−z|| ≤ 1. It does so with nested two-level amplitude amplification, guided by random product codes that preassociate each list vector with nearby center points. If correct, this is the fastest known quantum SVP algorithm when total memory is limited to 2^{0.1887d}.","feed_headline":"Quantum 3-tuple sieve runs in 2^{0.2846d} time","feed_subtitle":"New nested amplitude amplification cuts the previous exponent from 0.3098, shrinking the cost of post-quantum lattice attacks.","key_machinery":"The central mechanism is nested amplitude amplification run in three layers, applied to a two-oracle search: first find R-collisions (pairs of list vectors sharing a center point c under relation R), refine to pairs with inner product about cos(θ), then for each pair search z among vectors sharing an R′-collision with the normalized difference, flagging triples that satisfy the norm bound. The efficiency comes from random product codes (RPCs), structured random subsets of the sphere that are efficiently decodable yet behave like uniform random sets for collision probabilities; preprocessing stores the induced relations in a QCRAM data structure to allow fast superpositions. The two-stage nea","core_discovery":"The paper's central claim is Theorem 3.1: with a list of m = (27/16)^{d/4+o(d)} vectors drawn uniformly from the unit sphere, a quantum algorithm can find m triples with ||x−y−z|| ≤ 1 in time 2^{0.284551d+o(d)}, using 2^{0.1887d} classical and QCRAM bits and 2^{o(d)} qubits. Because these triples yield shorter lattice vectors in each sieving round, the theorem translates, under the paper's uniform heuristic, into a heuristic quantum SVP algorithm with the same exponent. The key is to search not over all triples but over pairs that share a nearby 'center point' from a random product code, and then over z close to the normalized difference x−y; a nested amplitude amplification replaces the nai","pith_inferences":["A direct numerical test is to simulate the 'find many triples' step with random unit vectors at intermediate dimensions and measure whether m triples satisfying ||x−y−z|| ≤ 1 appear at list size (27/16)^{d/4}; if correlations cut the yield, the practical exponent worsens.","The same recipe—nested amplitude amplification with RPC-preprocessed center points—could be tried for 4-tuple sieving or the approximate k-list problem, potentially lowering memory-limited exponents further.","For a rigorous worst-case SVP guarantee, one would need to replace the uniform heuristic by perturbation or discrete Gaussian sampling; the gap between the heuristic exponent and a provable one remains to be quantified."],"forward_implications":["Assuming the uniform heuristic, 3-tuple sieving becomes faster in quantum time than the best classical 2-tuple sieving while using less memory.","At a memory cap of 2^{0.1887d}, this is the fastest heuristic quantum SVP algorithm currently known.","The algorithm avoids quantum-readable quantum-writable quantum memory: it needs only 2^{o(d)} qubits and QCRAM, a more conservative hardware assumption.","For cryptographic parameter setting, the modest exponent drop does not overturn security estimates, since these already budget for a quadratic quantum speedup."],"fun_headline_variants":["Quantum 3-tuple sieve time exponent cut to 0.2846","Nested amplitude amplification speeds up quantum lattice sieve to 2^0.2846d","3-tuple sieve quantum exponent drops from 0.3098 to 0.2846","Fastest quantum SVP with 2^{0.1887d} memory uses new sieve"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The SVP claim rests on the uniform heuristic—that after each sieving round the list is, up to rescaling, an i.i.d. uniform sample from a thin spherical annulus; the paper concedes this is technically false because output vectors like x+y and x+z are correlated.","fun_headline_variants_meta":{"raw":{"variants":["Quantum 3-tuple sieve time exponent cut to 0.2846","Nested amplitude amplification speeds up quantum lattice sieve to 2^0.2846d","3-tuple sieve quantum exponent drops from 0.3098 to 0.2846","Fastest quantum SVP with 2^{0.1887d} memory uses new sieve"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000695,"raw_usage":{"total_tokens":3034,"prompt_tokens":855,"completion_tokens":2179,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":2085}},"tokens_in":599,"tokens_out":2179,"duration_ms":15660,"temperature":1.0,"reasoning_tokens":2085,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T10:44:28.527020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate one sieving round with m = (27/16)^{d/4} random unit vectors and count triples (x,y,z) with ||x−y−z|| ≤ 1; if the observed count is far below the predicted m for d around 100–200, or if correlations among outputs from shared parents reduce the next round's yield, the 2^{0.2846d} attack fails. More directly, test whether the stronger property ⟨x,y⟩ ≈ 1/3 and ⟨(x−y)/||x−y||,z⟩ ≈ √(1/3) holds for m triples at this list size.","supporting_citations":[],"review_version":1}