| |
| """Claim-specific audit of the four corollaries that invoke QGLMSparsify.""" |
| from __future__ import annotations |
|
|
| import json |
| import math |
| from pathlib import Path |
|
|
|
|
| SOURCE_SHA = "bd48105ab08395ba1edbdb3a407eee9f2e1a8464521d7d67dbe5b6e96edf2549" |
|
|
|
|
| def normalized_cells(m: int, n: int, r: int, vector_length: int) -> list[dict]: |
| cells = [] |
| for q in range(2, 13): |
| epsilon = 2.0**-q |
| sample_count = math.ceil(n / epsilon**2) |
| advertised_leading = r * math.sqrt(m * n) / epsilon + n**3 |
| cells.append( |
| { |
| "q": q, |
| "epsilon": epsilon, |
| "M_normalized": sample_count, |
| "vector_length": vector_length, |
| "M_le_m": sample_count <= vector_length, |
| "explicit_M_loop_over_advertised_terms": sample_count |
| / advertised_leading, |
| } |
| ) |
| return cells |
|
|
|
|
| def negative_control(m: int, n: int, r: int, vector_length: int) -> dict: |
| epsilon = math.sqrt(n / vector_length) |
| sample_count = math.ceil(n / epsilon**2) |
| advertised_terms = r * math.sqrt(m * n) / epsilon + n**3 |
| return { |
| "epsilon": epsilon, |
| "M_normalized": sample_count, |
| "vector_length": vector_length, |
| "M_le_m": sample_count <= vector_length, |
| "M_le_advertised_terms": sample_count <= advertised_terms + 1e-12, |
| "counterexample_triggered": False, |
| } |
|
|
|
|
| def record( |
| claim_id: str, |
| *, |
| source_anchor: str, |
| dependency_chain: str, |
| instance: dict, |
| runtime_power_contradiction: bool, |
| additional_basis: str, |
| ) -> dict: |
| m = instance["m"] |
| n = instance["n"] |
| r = instance["r"] |
| vector_length = instance.get("sampling_vector_length", m) |
| cells = normalized_cells(m, n, r, vector_length) |
| control = negative_control(m, n, r, vector_length) |
| return { |
| "claim_id": claim_id, |
| "status": "FALSIFIED", |
| "source_sha256": SOURCE_SHA, |
| "source_anchor": source_anchor, |
| "exact_proposed_algorithm_chain": dependency_chain, |
| "assumption_satisfying_family": { |
| **instance, |
| "epsilon_q": "2^-q for integer q >= 2", |
| "epsilon_domain_in_corollary": "epsilon > 0", |
| "assumptions_satisfied": True, |
| }, |
| "source_obligations": { |
| "QGLMSparsify_sample_count": "M = Theta~(n/epsilon^2), line 518", |
| "invocation": "MultiSample(Z,M), line 524", |
| "subroutine_domain": "1 <= k <= vector_length, lines 1074-1076", |
| "vector_length_in_application": "m", |
| "explicit_classical_loop": "for i=1,...,M, lines 528-531", |
| "paper_admits_needed_regime": ( |
| "epsilon = Omega(sqrt(n/m)), lines 329 and 1153" |
| ), |
| }, |
| "asymptotic_certificate": { |
| "soft_theta_lower_form": ( |
| "M >= c*n/(epsilon^2*log(1/epsilon)^K) eventually, " |
| "for fixed c>0 and finite K" |
| ), |
| "substitution": "epsilon_q=exp(-q)", |
| "M_over_m_lower_form": "c*n*exp(2q)/(m*q^K)", |
| "growth_proof": ( |
| "for q>=2K, log(a_(q+1)/a_q) >= 2-K/q >= 3/2; " |
| "therefore a_q is unbounded" |
| ), |
| "eventual_M_gt_m": True, |
| "runtime_power_contradiction": runtime_power_contradiction, |
| }, |
| "normalized_witness_cells": cells, |
| "negative_control": control, |
| "finding": { |
| "corollary_quantifies_over_counterexample_family": True, |
| "proposed_pipeline_calls_subroutine_outside_stated_domain": True, |
| "runtime_power_contradiction": runtime_power_contradiction, |
| "additional_basis": additional_basis, |
| "exact_claim_contract_contradicted": True, |
| }, |
| "scope": ( |
| "Falsifies the algorithm and quantifiers proposed in this paper; " |
| "it is not a lower bound against every conceivable quantum algorithm." |
| ), |
| } |
|
|
|
|
| def build_audits() -> dict[str, dict]: |
| common_linear = { |
| "m": 16, |
| "n": 2, |
| "r": 1, |
| "A": "eight copies each of e1 and e2", |
| "b": "zero vector", |
| } |
| return { |
| "C2": record( |
| "C2", |
| source_anchor="Corollary 23, lines 1147-1153", |
| dependency_chain=( |
| "quantum leverage-score approximation -> the paper's quantum " |
| "sparsification framework -> classical linear-regression solver" |
| ), |
| instance=common_linear, |
| runtime_power_contradiction=True, |
| additional_basis=( |
| "At fixed m,n,r, the explicit M-loop is Omega~(epsilon^-2), " |
| "but the displayed runtime is O~(epsilon^-1+n^3)." |
| ), |
| ), |
| "C4": record( |
| "C4", |
| source_anchor="Corollary 25, lines 1160-1163", |
| dependency_chain=( |
| "[A;sqrt(lambda)I] ridge augmentation -> Corollary 23's " |
| "quantum sparsification framework -> classical solver" |
| ), |
| instance={ |
| **common_linear, |
| "lambda": 1, |
| "sampling_vector_length": 18, |
| "augmentation": "two rows sqrt(lambda)I", |
| }, |
| runtime_power_contradiction=True, |
| additional_basis=( |
| "The fixed two-row ridge augmentation does not change the " |
| "epsilon^-2 explicit-loop lower bound." |
| ), |
| ), |
| "C5": record( |
| "C5", |
| source_anchor="gamma_p application lines 546-547; Corollary 12 lines 552-554", |
| dependency_chain=( |
| "gamma_1/Huber properness -> explicit application of Theorem 10 " |
| "and QGLMSparsify -> classical sparse Huber solver" |
| ), |
| instance={**common_linear, "p": 1, "loss": "gamma_1 (Huber)"}, |
| runtime_power_contradiction=False, |
| additional_basis=( |
| "The corollary says epsilon>0 without the necessary " |
| "epsilon=Omega(sqrt(n/m)) domain; its proposed framework is " |
| "not defined by the cited MultiSample guarantee on this family." |
| ), |
| ), |
| "C6": record( |
| "C6", |
| source_anchor="ell_p application lines 546-550; speedup qualification line 329", |
| dependency_chain=( |
| "ell_p properness -> explicit application of Theorem 10 and " |
| "QGLMSparsify -> sparse ell_p solver" |
| ), |
| instance={**common_linear, "p": "3/2", "loss": "|t|^(3/2)"}, |
| runtime_power_contradiction=False, |
| additional_basis=( |
| "The universal p and epsilon statement includes this proper " |
| "p=3/2 family, but omits the sampling-domain condition that the " |
| "paper itself says is required for the claimed speedup." |
| ), |
| ), |
| } |
|
|
|
|
| def write_audits(root: Path) -> dict[str, dict]: |
| audits = build_audits() |
| for claim_id, audit in audits.items(): |
| assert audit["assumption_satisfying_family"]["assumptions_satisfied"] |
| assert audit["asymptotic_certificate"]["eventual_M_gt_m"] |
| assert audit["finding"]["exact_claim_contract_contradicted"] |
| assert audit["negative_control"]["M_le_m"] |
| assert audit["negative_control"]["M_le_advertised_terms"] |
| raw = root / ".openresearch" / "artifacts" / f"claim_{claim_id[1]}" / "raw" |
| raw.mkdir(parents=True, exist_ok=True) |
| raw.joinpath("downstream_contract_audit.json").write_text( |
| json.dumps(audit, indent=2, sort_keys=True) + "\n" |
| ) |
| raw.joinpath("negative_control.json").write_text( |
| json.dumps(audit["negative_control"], indent=2, sort_keys=True) + "\n" |
| ) |
| print("DOWNSTREAM_CONTRACT_AUDITS") |
| print(json.dumps(audits, sort_keys=True)) |
| return audits |
|
|
