{"id":"387400ef-6301-4dda-b06a-2e2b3dc052ef","arxiv_id":"1908.06229","paper_version":8,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The divide-and-conquer LWE algorithm claims a NISQ-friendly polynomial speedup, but its success probability bound fails because the transformed noise scales with the superposed coefficient.","lead":"A quantum algorithm for the learning-with-errors problem splits the task into small subproblems and claims polynomial sample and time complexity with exponentially smaller quantum states. The paper's own error definition, however, contradicts the noise bound the proof relies on, so the claimed speedup is not established.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. S13 makes the divide-and-conquer samples noiseless for the shifted secret s+A^{-1}η, so the algorithm and its M-test recover the wrong vector; Eq. (7) does not bound true success.","rationale":"The reader's weakest_assumption identifies the correct load-bearing gap. In fact the situation is even cleaner than a failed uniform bound: Eq. (S13) turns every constructed pair, both the superposed sample and the deterministic test samples, into noiseless samples for s_j+(A^{-1}η)_j. The M-test is therefore self-consistent with the wrong secret and cannot detect the shift. The paper candidly notes several parameter restrictions, but this internal inconsistency is not one of them; it invalidates the derivation of Eq. (7), the false-acceptance bound Eq. (8), and the overall success bound Eq. (10). There is no machine-checked proof or numerical experiment to lean on. A tiny explicit instance already shows failure, so the rejection is warranted.","tokens_in":11340,"tokens_out":9749,"duration_ms":104427,"concrete_test":"Fix q=101, n=2, ξ=1, s=(0,0), A=[[1,1],[0,1]], η=(1,0). Then A^{-1}η=(1,-1 mod 101). For j=1, c_1=1; Eq. (S13) gives labels a'_1·1 for a'_1 ∈ F_101, i.e., a noiseless code for s_1+c_1=1. Run the paper's algorithm: BV(|ψ_1⟩) outputs \\tilde s_1=1, and the M-test with deterministic samples t_j=1,2,3,... accepts \\tilde s_1=1 with probability 1, while \\tilde s_1=0 is rejected by a sample with t_1=20 (|20-0|=20>ξ'=8). This contradicts the claimed 1-δ success probability for true s and shows Eq. (7) cannot hold for the actual η'_j. A symbolic check: substitute η'_j=a'_j c_j into Eq. (S17); the Fourier peak is at k_j=-(s_j+c_j)k*, not k_j=-s_j k*.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof breaks at the relation between Eq. (S13) and Eq. (7). Eq. (S13) defines the reduced error as η'_j = a'_j (A^{-1}η)_j, so each reduced pair is (a'_j, a'_j s_j + a'_j c_j) with c_j=(A^{-1}η)_j. Thus the quantum state of Eq. (2) is not a bounded-noise sample for s_j; it is a noiseless sample for the shifted secret s_j+c_j. The derivation of Eq. (7)/S20 requires |η'_j| ≤ ξ' uniformly over v_j, but since |v_j|=O(q) means v_j is a positive fraction of F_q, a'_j takes values of size Θ(q), making η'_j = a'_j c_j as large as Θ(q) ≫ ξ' whenever c_j ≠ 0. More importantly, this is not a missing bound that a better calculation could repair: BV(|ψ_j⟩) returns s_j+c_j (up to the usual 1/q failure), and the M-test uses deterministic samples built by the same Gaussian elimination, so it checks consistency with the same shifted secret. It accepts \\tilde s_j = s_j+c_j when c_j is small, and otherwise fails or accepts an arbitrary shifted value; in neither case does it certify s_j. Nothing in the paper forces c_j=0; for random bounded η and invertible A, c_j is nonzero with probability 1-O(ξ/q) and is not concentrated in [-ξ', ξ']. The algorithm therefore reconstructs s+A^{-1}η, not s, and the claimed polynomial complexity for learning s is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a divide-and-conquer quantum algorithm for the learning-with-errors (LWE) problem with bounded error |η| ≤ ξ = αq. It uses Gaussian elimination to create n reduced single-coordinate samples, superposes over data values a'_j in a subset v_j ⊆ F_q, applies a Bernstein-Vazirani QFT kernel, and verifies candidates with an M-trial test. The paper claims polynomial quantum-sample complexity O(nκξ log(n/δ)) and poly(n) time for q polynomial in n and κ = O(n^3), with superposition size O(q) instead of O(q^n), and argues this gives a tangible or NISQ-compatible quantum speedup.","tokens_in":11767,"tokens_out":5622,"duration_ms":53798,"significance":"If the central claim were sound, the contribution would be significant: it would improve the superposition-size and QRAM-call overheads relative to the earlier quantum LWE algorithm of Grilo et al., and it would give one of the few concrete quantum speedup proposals tailored to near-term devices. The paper also contains a useful comparison with classical BKW-type algorithms and an unusually honest statement of limitations, including the need for O(n^2 q) classical samples and the restriction to polynomial q. However, the central noise analysis is invalid: the reduced noise is not uniformly bounded over the superposition, and Gaussian elimination deterministically shifts the secret that the algorithm learns. The stated polynomial complexity is therefore unsupported.","major_comments":[{"comment":"The supplement defines η'_j = a'_j (A^{-1}η)_j in Eq. (S13), and the main text's Eq. (2) uses this quantity in the state |ψ_j>. Consequently each reduced sample is exactly (a'_j, a'_j(s_j+c_j)) with c_j=(A^{-1}η)_j; this is a noiseless sample for the shifted secret s_j+c_j, not a bounded-error sample for s_j. The assertion in the paragraph after Eq. (2) that |η'_j| ≤ ξ' = κξ uniformly for all a'_j ∈ v_j is therefore false whenever |v_j| = O(q) and c_j ≠ 0, because v_j then contains elements of size Θ(q). For random bounded η and invertible A, c_j ≠ 0 with probability 1 - O(ξ/q), so the uniform bound is not a minor technicality.","section":"Supplement Eq. (S13); main Eq. (2)"},{"comment":"The derivation of P(s̃_j = s_j) uses Re(ω^{η'_j k*}) ≥ cos(2πγη'_j/ξ') ≥ cos(2πγ) with k* ≤ γq/ξ', which requires |η'_j| ≤ ξ' for every a'_j ∈ v_j. As shown above, |η'_j| can be Θ(q)|c_j|, so the phase condition fails for large a'_j and Eq. (7) is not a valid lower bound. The probability estimated in Eq. (7) is at best the probability of measuring the shifted secret s_j+c_j; it does not quantify success for s_j. In particular, choosing v_j with small |a'_j| to restore boundedness would give |v_j| = O(ξ'), not O(q), which destroys the polynomial bound and contradicts the paper's own requirement |v_j| = O(q).","section":"Eqs. (5)-(7) and Supplement Eqs. (S17)-(S20)"},{"comment":"The deterministic test samples in T.1 are constructed by the same Gaussian-elimination procedure, so their labels are t_j(s_j+c_j) rather than t_j s_j + η'_j with bounded η'_j. For the shifted candidate s̃_j = s_j+c_j, ∆_j = 0 and the test accepts the wrong value; for the true s_j, ∆_j = |t_j c_j| can exceed ξ', so the true value can be rejected. Thus the M-test does not certify the original secret, and the failure-probability bound in Eq. (3) does not apply to the event described.","section":"M-trial test, T.1-T.2; Eq. (3)"},{"comment":"Since Eqs. (3) and (7) are the only ingredients for the overall success probability Prob(i) ≥ 1 - δ and for the quantum-sample bound O(nκξ log(n/δ)), the claimed polynomial sample and time complexities are unsupported. The structural reason is the deterministic shift s → s + A^{-1}η introduced by Gaussian elimination; this is not an error that can be bounded away by a better concentration estimate within the algorithm's current design.","section":"Analysis, Eqs. (8)-(10); sample complexity"}],"minor_comments":[{"comment":"The title of this arXiv version ('Tangible Quantum Speedup in Learning-With-Errors Problem') and the abstract in the submission ('Quantum solvability of noisy linear problems...') describe different claims; the title and abstract should be aligned.","section":"Title and abstract"},{"comment":"In Eq. (2), 'fo' should be 'for' in the sentence introducing the less-superposed quantum sample.","section":"Eq. (2)"},{"comment":"Reference numbering is inconsistent: the main text's reference [1] (Arute et al.) and the supplemental reference [1] (Giovannetti et al.) duplicate the label, and the supplementary bibliography contains its own numbered entries [2]-[7] that do not belong to the main numbering.","section":"References"},{"comment":"The sentence after Eq. (3) stating that 'O(κα) does not decay faster than O(q^{-1}) because α ≪ κ^{-1}' is confusing and appears to state the opposite of the intended relation; please rephrase with explicit inequalities.","section":"Eq. (3)"},{"comment":"Eq. (7) introduces a free parameter γ ∈ [0,1/4) and the cutoff '⌊γq/ξ'⌉' without defining the rounding; state the precise summation range. In the Acknowledgments, 'Marcin Paw/suppress lowski' appears to be a corrupted name.","section":"Eq. (7) and Acknowledgments"}],"recommendation":"reject","confidential_remarks":"The central claim fails because the reduced samples are noiseless for a shifted secret, and the error term is a function of the data register value, so the uniform bound in Eq. (7) is structurally invalid. The flaw is not a missing lemma; constraining |η'_j| forces |v_j| to be small, which destroys the polynomial quantum-sample claim. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real algorithmic idea, and the main claim doesn't survive contact with the authors' own Eq. (S13).\n\nWhat's genuinely nice: the divide-and-conquer reduction from O(q^n) to O(q) superpositions is not in the cited Grilo et al. or classical BKW literature. Pairing Gaussian elimination with a Bernstein-Vazirani kernel on one-dimensional reduced samples is a new combination. The complexity table is useful, and the discussion is candid about not solving LWE in general and about the κξ ≪ q condition. The writing is clear, and the citation pattern looks clean.\n\nThe problem is at the center. In the supplement, Eq. (S13) defines the reduced error as η'_j = a'_j (A^{-1}η)_j. The authors say this is 'still bounded between -ξ and ξ,' but a'_j runs over v_j with |v_j| = O(q), so η'_j scales with a'_j. For random v_j, that means η'_j is typically Θ(q) times the original error, not bounded by ξ' = κξ. The success probability bound in Eq. (7) and in Eq. (S20) requires |η'_j| ≤ ξ' uniformly. That condition is false.\n\nWorse, this isn't a gap that a sharper bound could fill. If you write the reduced sample as (a'_j, a'_j s_j + a'_j c_j) with c_j = (A^{-1}η)_j, then the quantum state is actually noiseless for the shifted secret s_j + c_j. The BV kernel will return s_j + c_j (up to the usual 1/q failure), and the M-test uses deterministic samples built by the same Gaussian elimination, so it tests consistency with the same shifted secret. It will accept the wrong vector whenever c_j is nonzero, and nothing forces c_j to be zero. The algorithm therefore reconstructs s + A^{-1}η, not s. The polynomial sample/time claim is unsupported.\n\nThe parameter restrictions the authors do flag (κξ ≪ q, q polynomial) are honest, but they don't touch this issue. The flaw is internal: the paper's own definition of η'_j contradicts the bounded-error assumption used in the main proof.\n\nBottom line: this is for someone working on quantum LWE who wants a novel starting point or a cautionary example about error propagation in Gaussian-eliminated samples. It deserves a serious referee because the idea is original and the failure mode is instructive, but as is it should not be accepted. If I were editing, I'd send it out, then ask the referee whether a different reduction—one that doesn't multiply the error by a'_j—could rescue the approach.","headline":"A genuinely new divide-and-conquer idea for quantum LWE, but the main proof is undone by the authors' own error transformation, which shifts the recovered secret by A^{-1}η.","tokens_in":12274,"tokens_out":3513,"would_cite":false,"duration_ms":33356,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a divide-and-conquer quantum algorithm solves bounded-error learning-with-errors with polynomial sample and time complexity while using an exponentially smaller superposition.","keywords":["learning with errors","quantum algorithm","divide and conquer","BV kernel","bounded error model","quantum sample complexity","NISQ","Gaussian elimination"],"falsifier":"Set $n=1$, choose $v_1=\\mathbb{F}_q$ with $q$ prime and fixed nonzero noise $\\eta$, and compute the exact success probability $P(\\tilde{s}_1=s_1)=\\frac{1}{q^2|v_1|}\\sum_{k_\\star\\in\\mathbb{F}_q}\\left|\\sum_{a\\in v_1}\\omega^{a\\eta k_\\star}\\right|^2$. If this is $O(1/q)$ rather than the claimed lower bound $\\gamma |v_1|\\cos^2(2\\pi\\gamma)/(\\xi' q)$, or if the accepted value is $s_1+\\eta$ rather than $s_1$, the central polynomial-complexity claim is contradicted.","tokens_in":11176,"feed_emoji":"🔐","tokens_out":12870,"duration_ms":117685,"temperature":0.7,"pith_summary":"This paper claims that the learning-with-errors problem with bounded noise $|\\eta|\\le\\xi=\\alpha q$, $\\alpha\\ll 1$, and $q$ at most polynomial in $n$, can be solved by a quantum divide-and-conquer algorithm using $O(n\\kappa\\xi\\log(n/\\delta))$ quantum samples and $\\mathrm{poly}(n,\\log(n/\\delta))$ time, with a superposition of only $O(q)$ states per coordinate instead of $O(q^n)$. The strategy splits the $n$-dimensional linear structure into one-dimensional subproblems by Gaussian elimination, prepares a small superposed quantum sample for each coordinate, and extracts the secret with a two-QFT Fourier kernel followed by a deterministic M-trial test. If correct, the result would put a quantum speedup for a cryptographically central problem within reach of near-term devices, exponentially reducing both sample-state size and QRAM cost relative to the earlier quantum approach. The claimed regime is $\\xi=\\mathrm{poly}(n)$ with $q$ polynomial in $n$ and $\\kappa\\xi\\ll q$, where $\\kappa=O(n^3)$ is the error amplification from elimination.","feed_headline":"Divide-and-conquer cuts quantum LWE sample cost to polynomial","feed_subtitle":"The algorithm needs only O(q)-sized superpositions and polynomially many samples, whereas earlier approaches need O(q^n).","key_machinery":"The machinery is the one-coordinate Fourier kernel: applying $QFT_q$ to both the data and answer registers of the state $\\frac{1}{\\sqrt{|v_j|}}\\sum_{a'_j\\in v_j}|a'_j\\rangle_D|a'_j s_j+\\eta'_j\\rangle_A$ produces a correlation through $k_j=-s_j k_\\star$ plus a phase $\\omega^{\\eta'_j k_\\star}$. The paper lower-bounds the probability of reading the correct correlation by $\\gamma |v_j|\\cos^2(2\\pi\\gamma)/(\\xi' q)$; with $|v_j|=O(q)$ and $L=O(\\xi'\\ln(n/\\delta))$ trials per coordinate, this supports the polynomial sample bound. The M-trial test is what turns a noisy single-shot candidate into a certified value, using deterministic samples to reject any $\\tilde{s}_j$ that does not match within $\\xi'$ on M independent trials.","core_discovery":"The paper's central claim is that the learning-with-errors problem with $|\\eta|\\le\\xi=\\alpha q$, $\\alpha\\ll 1$, and $q$ at most polynomial in $n$, can be solved by a quantum divide-and-conquer algorithm in $O(n\\kappa\\xi\\log(n/\\delta))$ quantum samples and $\\mathrm{poly}(n,\\log(n/\\delta))$ time, with success probability at least $1-\\delta$. The method first uses Gaussian elimination to turn $n$-dimensional samples into $n$ independent coordinate pairs $(a'_j,\\,a'_j s_j+\\eta'_j)$, where the new noise is bounded by $\\xi'=\\kappa\\xi$ with $\\kappa=O(n^3)$; it then prepares a superposition over $O(q)$ values of $a'_j$ and runs a two-QFT Fourier kernel on that single coordinate. The measurement yields a candidate $\\tilde{s}_j$, and an M-trial deterministic test accepts only candidates that agree with M fresh samples within $\\xi'$, bounding the chance of accepting a wrong secret by $L(2\\kappa\\alpha)^M$. In the regime $\\kappa\\xi\\ll q$, the superposition size, sample complexity, and time complexity are all polynomial, whereas the earlier quantum approach needed $O(q^n)$-sized superpositions.","pith_inferences":["The error formula $\\eta'_j=a'_j(A^{-1}\\eta)_j$ implies the success bound in Eq. (7) depends on a uniform error bound that is not automatic when $v_j$ spans essentially all of $\\mathbb{F}_q$; a quick numerical test for $n=1$ would reveal whether the central premise holds.","A natural repair direction is to restrict each superposition set to coefficients small enough that $|\\eta'_j|\\le\\xi'$ still holds, but then $|v_j|$ shrinks and the claimed sample-complexity gain must be recomputed; the paper does not analyze this trade-off.","The M-test as written certifies consistency with transformed samples; if those samples are consistent with a shifted secret, the test cannot distinguish the shift, so the stated failure bound $L(2\\kappa\\alpha)^M$ applies only when the uniform error bound is available."],"forward_implications":["For $\\xi=\\mathrm{poly}(n)$ and $q$ at most polynomial in $n$ with $\\kappa\\xi\\ll q$, the algorithm learns the secret with probability at least $1-\\delta$ using $O(n\\kappa\\xi\\log(n/\\delta))$ quantum samples and $\\mathrm{poly}(n,\\log(n/\\delta))$ time.","The per-coordinate superposition size is $O(q)$ instead of $O(q^n)$, and the QRAM call cost drops from exponential to polynomial in the primitive model and to $O(\\log q)$ operations in the bucket-brigade model.","Each coordinate is processed independently, so a single wrong candidate can be rejected by the M-trial test, and the overall failure probability can be pushed below $\\delta$ by repeating each coordinate $L=C\\xi'\\ln(n/\\delta)$ times.","In the noiseless limit the protocol identifies each coordinate with probability close to 1 using $O(q/(q-1)\\,n)$ samples and $O(\\mathrm{poly}(n))$ time, matching classical linear solving."],"supporting_citations":[{"why":"It defines the LWE problem and its cryptographic hardness, which frames the task the algorithm addresses.","marker":"[13]"},{"why":"It supplies the hardness background that makes the claimed polynomial quantum solution significant.","marker":"[14]"},{"why":"It is the earlier quantum algorithm needing $O(q^n)$-sized superpositions, the main baseline the divide-and-conquer approach claims to improve.","marker":"[15]"},{"why":"It supplies the Gaussian elimination preprocessing that produces isolated coordinate pairs $(a'_j,b'_j)$.","marker":"[16]"},{"why":"It provides the QRAM model whose operation count is compared in the claimed exponential reduction.","marker":"[21]"},{"why":"It supplies the bounded-error parameter regime used to choose $\\xi=\\alpha q$ and $\\alpha\\ll\\kappa^{-1}$.","marker":"[23]"},{"why":"It supplies the two-QFT Fourier kernel used to extract each secret coordinate from the superposed sample.","marker":"[24]"},{"why":"It supplies the $O(n^3)$ linear-algebra cost for the matrix inversion in the elimination step.","marker":"[28]"}],"fun_headline_variants":["Polynomial samples: quantum divide-and-conquer solves noisy linear problems","Divide-and-conquer shrinks quantum sample size for noisy equations","Quantum algorithm tames noisy linear problems with polynomial samples","From exponential to polynomial: quantum LWE via divide-and-conquer","Quantum divide-and-conquer makes noisy linear solving efficient"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm's success bound assumes the transformed noise stays below a fixed small bound for every coefficient appearing in the quantum superposition, even though the noise formula makes that transformed noise proportional to the coefficient itself.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial samples: quantum divide-and-conquer solves noisy linear problems","Divide-and-conquer shrinks quantum sample size for noisy equations","Quantum algorithm tames noisy linear problems with polynomial samples","From exponential to polynomial: quantum LWE via divide-and-conquer","Quantum divide-and-conquer makes noisy linear solving efficient"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000615,"raw_usage":{"total_tokens":2909,"prompt_tokens":1046,"completion_tokens":1863,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":1779}},"tokens_in":662,"tokens_out":1863,"duration_ms":11855,"temperature":1.0,"reasoning_tokens":1779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:53:13.612427+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $n=1$, choose $v_1=\\mathbb{F}_q$ with $q$ prime and fixed nonzero noise $\\eta$, and compute the exact success probability $P(\\tilde{s}_1=s_1)=\\frac{1}{q^2|v_1|}\\sum_{k_\\star\\in\\mathbb{F}_q}\\left|\\sum_{a\\in v_1}\\omega^{a\\eta k_\\star}\\right|^2$. If this is $O(1/q)$ rather than the claimed lower bound $\\gamma |v_1|\\cos^2(2\\pi\\gamma)/(\\xi' q)$, or if the accepted value is $s_1+\\eta$ rather than $s_1$, the central polynomial-complexity claim is contradicted.","supporting_citations":[{"cited_title":"Regev, Journal of the ACM (JACM) 56, 34 (2009)","cited_arxiv_id":null,"evidence_quote":"It defines the LWE problem and its cryptographic hardness, which frames the task the algorithm addresses."},{"cited_title":"Regev, in Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity (2010), CCC ’10, pp","cited_arxiv_id":null,"evidence_quote":"It supplies the hardness background that makes the claimed polynomial quantum solution significant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It is the earlier quantum algorithm needing $O(q^n)$-sized superpositions, the main baseline the divide-and-conquer approach claims to improve."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the Gaussian elimination preprocessing that produces isolated coordinate pairs $(a'_j,b'_j)$."},{"cited_title":"Brakerski and V","cited_arxiv_id":null,"evidence_quote":"It supplies the bounded-error parameter regime used to choose $\\xi=\\alpha q$ and $\\alpha\\ll\\kappa^{-1}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the $O(n^3)$ linear-algebra cost for the matrix inversion in the elimination step."}],"review_version":1}