# Reproduction logbook — `paper-TBSyYj4VV6`

**Paper:** *Accelerating Regression Tasks with Quantum Algorithms* — Chenghua Liu, Zhengfeng Ji.
ICML 2026 Poster. OpenReview `TBSyYj4VV6`, arXiv `2509.24757` (submitted 2025-09-30).

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

The paper presents a unified quantum algorithm for GLM sparsification (Theorem 10) and applies
it to five regression variants (Corollaries 11, 12, 23, 25, 26). Every one of the six official
claims restates one of these six formal statements, each of which is quantified over **"any
`ε > 0`"** with no lower bound. This logbook shows — using nothing but the paper's own printed
algorithm, its own printed proof, and a subroutine the paper itself cites *verbatim* — that this
unrestricted quantifier is false: the algorithm's own second line sets a sample count that
violates the cited subroutine's own stated domain whenever `ε` is small relative to `n/m`, and
the paper's own prose (independently, in two places) confirms the missing restriction is real.
No quantum computer, simulator, or numerical experiment is required to see this: it is an
arithmetic substitution of the paper's own equations into its own cited theorem.

## The mechanism (applies identically to all six claims)

| Step | Where in the paper | What it says |
|---|---|---|
| 1 | Algorithm 2, line 2 (p.10) | `M ← Θ̃(n/ε²)` — the number of importance samples the algorithm draws |
| 2 | Algorithm 2, line 5 (p.10) | `ϑ ← MultiSample(Z, M)` — draws those `M` samples from a distribution over the `m` data points |
| 3 | Theorem 20 (p.22), restated verbatim from Hamoudi [2022] | **"Let `1 ≤ k ≤ n`."** — the requested count `k` cannot exceed the dimension of the sampled vector (here `m`) |
| 4 | Substitution | Algorithm 2 needs `M = Θ̃(n/ε²) ≤ m`, i.e. **`ε = Ω(√(n/m))`** |
| 5 | Paper's own prose, p.4 (right after Table 1) | *"Since the sparsifier has size `Õ(n/ε²)`, it must be smaller than `m` ... which requires `ε = Ω(√(n/m))`"* |
| 6 | Paper's own prose, Corollary 23 remark, p.24 | *"the sparsifier size is `m' = Õ(n/ε²)`, which is smaller than the original size `m`, implying `ε = Ω(√(n/m))`"* |
| 7 | But every formal theorem/corollary (10, 11, 12, 23, 25, 26) | states its hypothesis as **"and `ε > 0`"** — unrestricted, no lower bound |

Steps 5 and 6 prove the authors *know* the restriction exists. Step 7 proves it never made it
into any formal quantifier. `code/domain_gap_check.py` confirms with the paper's own headline
numbers (`n=2, m=16, ε=0.25` ⟹ `M=32 > m=16`) and with 20,000 randomized `(n,m,ε,r)` triples that
"`M ≤ m`" is exactly equivalent to "`ε ≥ √(n/m)`" and to "the claimed quantum leading term
`r√(mn)/ε` is actually ≤ the classical term `mr`" — i.e. below the missing threshold the
algorithm is not just unguaranteed by the cited black box, its own printed runtime formula is
**slower**, not quadratically faster, than the classical baseline.

## Claim pages

| # | Claim (abridged) | Verdict | The gap |
|---|---|---|---|
| [1](claim-1-theorem10-universal-epsilon/page.md) | Theorem 10: `Õ(r√(mn)/ε+poly(n))·log(smax/smin)` sparsifier time, quadratic speedup, for any `ε` | **FALSIFIED** | Proof invokes Theorem 20 outside its domain for `ε < √(n/m)` |
| [2](claim-2-corollary23-linear-regression/page.md) | Corollary 23: linear regression in `Õ(r√(mn)/ε+n³)`, any `ε>0` | **FALSIFIED** | Same gap; paper's own remark under Cor. 23 admits the missing restriction |
| [3](claim-3-corollary26-lasso-first-and-domain/page.md) | Corollary 26: "first" quantum Lasso algorithm, any `ε>0` | **FALSIFIED** | Same gap **+** paper's own p.4 text names a 2023 prior quantum Lasso algorithm |
| [4](claim-4-corollary25-ridge-regression/page.md) | Corollary 25: ridge regression in `Õ(r√(mn)/ε+n³)`, any `ε>0` | **FALSIFIED** | Same gap, inherited from Theorem 10 |
| [5](claim-5-corollary12-huber-regression/page.md) | Corollary 12: Huber/γ_p regression in `Õ(r√(mn)/ε)+poly(n,1/ε)`, any `ε>0` | **FALSIFIED** | Same gap, inherited from Theorem 10 |
| [6](claim-6-corollary11-lp-regression/page.md) | Corollary 11: ℓ_p regression, quadratic speedup in `m` dominating when `m≫n` | **FALSIFIED** | Same gap, inherited from Theorem 10 |

- [Executive summary](executive-summary/page.md) — the one gap, its numeric confirmation, and what is actually true
- [Conclusion](conclusion/page.md) — what the paper's algorithm actually establishes, and what it does not

## Reproducing this logbook

```bash
python3 code/domain_gap_check.py
```

No third-party dependencies. Runtime under a second. Raw JSON output is saved to
`outputs/domain_gap_results.json`; the full formal derivation with page/line citations for every
quoted formula is in each claim page below.

`icml2026-repro` · `paper-TBSyYj4VV6`