code/domain_gap_check.py

"""
Independent recomputation of the epsilon-domain gap in
"Accelerating Regression Tasks with Quantum Algorithms" (Liu & Ji, arXiv:2509.24757,
ICML 2026, orid TBSyYj4VV6).

This script does NOT run any quantum hardware or simulator. It performs pure
arithmetic on quantities the paper itself prints, to check whether the paper's
formal theorem/corollary statements (which quantify over "any epsilon > 0" with
no lower bound) are consistent with:
  (a) the paper's own stated requirement, printed in prose immediately after
      Table 1 (p.4) and again in the remark under Corollary 23 (p.24), that
      "the sparsifier size Otilde(n/eps^2) must be smaller than m ... which
      requires eps = Omega(sqrt(n/m))"; and
  (b) the stated precondition "1 <= k <= n" of Theorem 20 (Multiple Quantum
      State Preparation, restated from Hamoudi 2022), which Algorithm 2 invokes
      with sample count k = M = Theta-tilde(n/eps^2) on a vector living in R^m
      (so the theorem's own precondition requires M <= m).

All numbers below (M formula, Table-1 leading terms, the n=2/m=16/eps=0.25
example) are taken verbatim from the paper's printed algorithm/theorem text,
quoted with page/line references in pages/claim-1.../page.md.
"""
import json
import math

def M_sparsifier_size(n, eps, const=1.0):
    """Algorithm 2, line 2: 'M <- Theta-tilde(n/eps^2)'. const absorbs the
    hidden Theta-tilde constant/polylog factor; we sweep const in {0.5,1,2,4}
    below to show the qualitative conclusion does not depend on which hidden
    constant the authors intended."""
    return const * n / eps**2

def quantum_leading_term(r, m, n, eps):
    """Table 1 / Theorem 10: leading quantum time term r*sqrt(mn)/eps."""
    return r * math.sqrt(m * n) / eps

def classical_term(m, r):
    """Table 1: classical term m*r (the term the paper compares against for
    the 'quadratic speedup in m' claim)."""
    return m * r

def epsilon_threshold(n, m, const=1.0):
    """Solve M(eps) = m for eps: const*n/eps^2 = m  =>  eps = sqrt(const*n/m)."""
    return math.sqrt(const * n / m)

results = {}

# --- 1. The peer's own headline numeric example, recomputed independently ---
n, m, eps = 2, 16, 0.25
M = M_sparsifier_size(n, eps, const=1.0)
results["headline_example"] = {
    "n": n, "m": m, "eps": eps,
    "M_formula": "M = n/eps^2 (Algorithm 2 line 2, const=1)",
    "M_value": M,
    "m": m,
    "M_exceeds_m": M > m,
    "note": "Theorem 20 requires 1<=k<=n(dim); here dim=m=16, k=M=32>16, "
            "outside the theorem's own stated domain.",
}
assert M == 32.0 and M > m

# --- 2. Algebraic identity (const=1, i.e. the literal formula 'M <- n/eps^2'
# printed in Algorithm 2 line 2, and the literal leading terms r*sqrt(mn)/eps
# vs m*r printed in Table 1 / Theorem 10 -- no hidden constants involved in
# either formula as printed): M(eps)<=m  <=>  eps>=sqrt(n/m)  <=>  quantum<=classical.
# Note r cancels out of the quantum-vs-classical comparison, so this holds for
# every r<=n, confirming it is not an artifact of a particular sparsity choice.
import random
random.seed(0)
all_consistent = True
n_checks = 20000
for _ in range(n_checks):
    n_ = random.randint(1, 2000)
    m_ = random.randint(n_, 200000)  # m>=n as required by the paper's own setting r<=n<=m
    eps_ = 10 ** random.uniform(-4, 0.3)
    r_ = random.randint(1, n_)
    M_ = M_sparsifier_size(n_, eps_, const=1.0)
    thr = epsilon_threshold(n_, m_, const=1.0)
    q = quantum_leading_term(r_, m_, n_, eps_)
    c = classical_term(m_, r_)
    cond_M_le_m = M_ <= m_
    cond_eps_ge_thr = eps_ >= thr
    cond_quantum_faster = q <= c
    if not (cond_M_le_m == cond_eps_ge_thr == cond_quantum_faster):
        all_consistent = False

results["identity_check"] = {
    "n_trials": n_checks,
    "claim": "With the literal (no-hidden-constant) formulas printed in the paper "
             "(Algorithm 2 line 2: M=n/eps^2; Table 1: quantum leading term "
             "r*sqrt(mn)/eps vs classical m*r), the three conditions "
             "'M<=m', 'eps>=sqrt(n/m)', and 'quantum_term<=classical_term' "
             "are exactly logically equivalent for every sampled (n,m,eps,r).",
    "all_consistent": all_consistent,
}
assert all_consistent

# --- 2b. Robustness: even with a generous (0.1x-10x) hidden constant slack on
# the sparsifier-size formula alone, a finite nonzero crossover eps* always
# exists below which M>m -- the domain gap is not an artifact of one constant
# choice, only its exact location shifts by a constant factor. ---
robustness_rows = []
for const_ in [0.1, 0.5, 1.0, 2.0, 10.0]:
    n_, m_ = 50, 100000
    thr_ = epsilon_threshold(n_, m_, const=const_)
    robustness_rows.append({"const": const_, "eps_threshold": thr_,
                             "finite_and_positive": 0 < thr_ < float("inf")})
results["constant_robustness_check"] = robustness_rows
assert all(row["finite_and_positive"] for row in robustness_rows)

# --- 3. Concrete crossover table for a fixed, realistic (n, m) pair ---
n_, m_ = 50, 100000  # n<<m, the regime the paper markets as its main use case
r = 4  # arbitrary fixed sparsity r<=n; cancels out of the quantum/classical ratio
thr = epsilon_threshold(n_, m_, const=1.0)
table = []
for eps_ in [0.001, 0.005, thr / 2, thr, thr * 2, 0.1, 0.5, 1.0]:
    M_ = M_sparsifier_size(n_, eps_)
    q = quantum_leading_term(r, m_, n_, eps_)
    c = classical_term(m_, r)
    table.append({
        "eps": eps_,
        "M=n/eps^2": M_,
        "M>m (sparsifier bigger than dataset)": M_ > m_,
        "quantum_term_r*sqrt(mn)/eps": q,
        "classical_term_m*r": c,
        "quantum_beats_classical": q < c,
    })
results["crossover_table_n50_m100000"] = {
    "n": n_, "m": m_, "threshold_eps=sqrt(n/m)": thr, "rows": table
}

# --- 4. Sanity check against the paper's own worked instance in Corollary 23 ---
# Corollary 23 remark (p.24): "the sparsifier size is m' = Otilde(n/eps^2) ...
# implying eps = Omega(sqrt(n/m))." We confirm this is exactly our formula.
results["corollary23_remark_matches_formula"] = True  # by construction, see epsilon_threshold()

with open("/Users/sshpro/icml-queue/newbook-TBSyYj4VV6/outputs/domain_gap_results.json", "w") as f:
    json.dump(results, f, indent=2)

print(json.dumps(results, indent=2))