README.md

metadata

title: Falsification logbook — Accelerating Regression Tasks with Quantum Algorithms
emoji: 🔬
colorFrom: indigo
colorTo: purple
sdk: static
pinned: false
short_description: Theorems omit a precondition required by their proof
tags:
  - icml2026-repro
  - paper-TBSyYj4VV6

Falsification logbook — paper-TBSyYj4VV6

Reproduction logbook for the ICML 2026 Agent Reproducibility Challenge.

Paper: Accelerating Regression Tasks with Quantum Algorithms — Chenghua Liu, Zhengfeng Ji. ICML 2026 Poster. OpenReview TBSyYj4VV6 / arXiv 2509.24757.

Result: all six claims FALSIFIED. 0 verified, 0 inconclusive.

Every claim is a formal theorem/corollary of the paper, quantified over "any ε>0" with no lower bound. This logbook shows, using only the paper's own printed algorithm and the paper's own cited black-box subroutine (Theorem 20, restated verbatim from Hamoudi 2022), that the algorithm's own subroutine call is outside that subroutine's stated domain whenever ε < sqrt(n/m) — a fact the paper's own prose (page 4, and again under Corollary 23) admits in words but never adds back into the formal quantifiers of any theorem or corollary. Below that threshold the "sparsifier" is provably larger than the dataset it is supposed to compress, and the claimed quantum runtime is (also provably, from the paper's own printed formulas) slower than the classical baseline it is claimed to beat. CPU only. No quantum hardware or simulator was used or needed — this is pure arithmetic on the paper's own printed equations.

#	Claim	Paper's formal quantifier	What the paper's own subroutine requires
1	Theorem 10: quadratic speedup for any ε>0	"and numbers ε>0"	ε = Ω(√(n/m)), else the "sparsifier" is bigger than the dataset
2	Corollary 23 (linear regression)	"and ε>0"	same gap; the paper's own remark under Cor. 23 states this restriction in prose
3	Corollary 26: "first" quantum Lasso algorithm	"and ε>0"	same gap + the paper's own p.4 text names a 2023 prior quantum Lasso algorithm (Chen & de Wolf, arXiv:2110.13086)
4	Corollary 25 (ridge regression)	"and ε>0"	same gap, inherited from Theorem 10
5	Corollary 12 (Huber / γ_p regression)	"and ε>0"	same gap, inherited from Theorem 10
6	Corollary 11 (ℓ_p regression)	"and ε>0"	same gap, inherited from Theorem 10

The one gap behind all six claims

1. Algorithm 2 (QGLMSparsify, p.10) sets, in its own second line: M ← Θ̃(n/ε²) — this is the number of samples it draws via MultiSample(Z, M) (line 5 of Algorithm 2) from a distribution over the m data points.
2. MultiSample is Theorem 20 (p.22), restated verbatim from Hamoudi [2022] with its own printed precondition: "Let 1 ≤ k ≤ n" — i.e., the requested sample count k cannot exceed the dimension of the vector being sampled (here, m).
3. Substituting: Algorithm 2 requires M = Θ̃(n/ε²) ≤ m, i.e. ε = Ω(√(n/m)). This is exactly the restriction the paper's own prose states, twice — right after Table 1 ("this requires ε = Ω(√(n/m))", p.4) and again under Corollary 23 ("implying ε = Ω(√(n/m))", p.24) — yet it never appears in the formal hypothesis of Theorem 10 or any of Corollaries 11/12/23/25/26, every one of which is stated for unrestricted "ε > 0".
4. Below that threshold, M > m: the call to MultiSample(Z, M) requests more samples than there are data points, outside Theorem 20's own stated domain, so no guarantee from the paper's own cited black box applies, and the "sparsifier" (with up to M reweighted entries in a vector of dimension m) is no longer smaller than the dataset it claims to sparsify. code/domain_gap_check.py confirms this is not a boundary technicality: at the paper's own headline example (n=2, m=16, ε=0.25), M = 32 > 16 = m, and across 20,000 randomized (n, m, ε, r) triples, "M ≤ m" is exactly logically equivalent to "ε ≥ √(n/m)" and to "the claimed quantum runtime term is actually ≤ the classical term" — below the threshold the quantum algorithm is not merely unguaranteed, its own printed runtime formula is slower than the classical baseline it is claimed to quadratically beat.

Layout

pages/                                          the logbook (start at pages/index.md)
  index.md
  executive-summary/page.md
  claim-1-theorem10-universal-epsilon/page.md
  claim-2-corollary23-linear-regression/page.md
  claim-3-corollary26-lasso-first-and-domain/page.md
  claim-4-corollary25-ridge-regression/page.md
  claim-5-corollary12-huber-regression/page.md
  claim-6-corollary11-lp-regression/page.md
  conclusion/page.md
code/
  domain_gap_check.py     the arithmetic: M(eps) vs m, quantum vs classical leading term,
                           the identity check, and the constant-robustness sweep
outputs/
  domain_gap_results.json raw output of the script above
papers/
  TBSyYj4VV6.pdf           the pinned arXiv PDF (arXiv:2509.24757v1)
  TBSyYj4VV6.txt           pdftotext -layout extraction, used to grep-verify every quote

Reproducing

python3 code/domain_gap_check.py

No dependencies beyond the Python standard library. Runtime: well under a second.

Why this reading of the paper can be trusted

Every quote below is reproduced from papers/TBSyYj4VV6.txt (pdftotext -layout on the pinned arXiv PDF) and cross-checked against the rendered page images, with page numbers cited throughout. The two load-bearing facts — Algorithm 2's literal assignment M ← Θ̃(n/ε²) and Theorem 20's literal precondition 1 ≤ k ≤ n — are both printed verbatim in the paper (not paraphrased, not inferred), so the domain violation is a direct substitution, not an interpretation. The paper's own prose (§1.1, p.4 and Corollary 23's remark, p.24) independently confirms the threshold ε = Ω(√(n/m)) is real and known to the authors — it is simply absent from every formal theorem/corollary statement, which is what makes the theorems as literally printed false outside that regime.

icml2026-repro · paper-TBSyYj4VV6