# Claim crosswalk

Evidence tier: **source/proof crosswalk only**. The source below is arXiv
`2606.06287v1`, archive SHA-256
`fdb5c87290b4704450a4d830dd489ab42e79228b2bcf506ed55e50e76eb2216e`.
All five exact active claims are the anchored entries in
`evidence/claims-active.json`; their status remains `unverified` in the
official feed. “Supported” below means that the cited paper source states the
claim at the listed anchor, not that this package independently establishes it.

## 1. Quantum triangle-listing runtime

> The quantum triangle listing algorithm runs in time Õ(min(n^(5/4)t^(7/12) + n^(7/6)t^(7/9), m + m^(3/4)t^(1/2), n^(3/2)t^(1/2))) for a graph with n vertices, m edges, and t triangles (Theorem 1.3).

**Source anchor:** `main.tex` lines 133–136 (`thm:main-triangle`). The theorem
states the three-term Õ runtime for `Q-TriangleListing`, under query access,
with high probability. **Outcome:** source-stated / limited. The crosswalk does
not execute the algorithm or compare its runtime to a baseline.

## 2. Sparsifier size and runtime

> The quantum triangle cut sparsification algorithm constructs an epsilon-triangle cut sparsifier with Õ(n/epsilon^2) edges in time T_q-list + Õ(sqrt(mn)/epsilon), where T_q-list is the quantum triangle listing runtime (Theorem 1.2).

**Source anchor:** `main.tex` lines 117–121 (`thm:q-triangle_cut_spars`), with
the fuller implementation statement at lines 602–605. **Outcome:**
source-stated / limited. This only records the theorem statement and its stated
assumptions; no implementation, quantum hardware, simulator, or proof checker
was used.

## 3. Sparsifier-size lower bound

> Every epsilon-triangle cut sparsifier requires at least Omega(n/epsilon^2) edges, establishing the near-optimality of the algorithm's sparsifier size (Theorem 5.2).

**Source anchor:** `main.tex` lines 686–689 (`thm:triangle_cut_lb`), with the
near-tight interpretation at lines 693–698. **Outcome:** source-stated /
limited. The claim’s universal wording needs the theorem’s stated domain:
there exists an `n`-vertex graph for each eligible `n` and epsilon, rather than
every graph requiring that many edges. No proof verification was performed.

## 4. Listing techniques

> The quantum triangle listing algorithm combines a heavy-light vertex partition (using Grover search over light-vertex neighborhoods) with a quantum walk extension of Le Gall's triangle detection algorithm on Johnson graphs (Section on algorithmic techniques).

**Source anchor:** `main.tex` lines 162–166 describes the heavy--light and
Grover component; lines 484–486 state the combination of heavy--light, quantum
walk, and Grover approaches. **Outcome:** source-stated / limited. This package
does not validate the derivation, the Johnson-graph construction, or any
claimed advantage.

## 5. Post-sampling complexity reduction

> The post-sampling stage of the sparsification algorithm reduces complexity from Õ(m) to Õ(sqrt(mn)/epsilon) via an implicit random string encoding technique (Section on post-sampling).

**Source anchor:** `main.tex` lines 179–183 introduces implicit encoding and
the stated reduction; lines 602–605 give the resulting runtime under the
random-string oracle condition. **Outcome:** source-stated / limited. The
crosswalk does not construct random strings or measure post-sampling cost.

## Limits and expected judge category

This package is deliberately bounded to paper-source provenance. It is **not a
reproduction**, proof verification, author-code result, or independent
execution. Its likely value to a judge is a readable, pinned source/proof
crosswalk; its limitation is that it offers no runtime, output, or formal proof
evidence beyond the paper’s own source statements.