README.md

---
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

```bash
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`