When Does a Quantum Speedup Survive End-to-End?

• Dense classical outputs can impose extraction costs even when a primitive remains fast, so output contracts also shape end-to-end inheritance.The paper contrasts dense output with compact scalar-observable contracts.Source: §1 · pp. 1–2
• The interface-admissibility framework places a matched classical route in the baseline when the quantum implementation package generates its access transcripts and all route overheads are charged.This makes the end-to-end comparison depend on the declared package, not just the primitive quantum behavior.Source: §1 · p. 2
• For clique-complex normalized-Betti estimation, abstract spectral access needs an implementation package or transcript reduction, membership preparation incurs inverse clique-density rejection overhead, and reversible indexed access certifies matched classical transcripts.The indexed certificate obtains simplex sampling and local Laplacian-row access by evaluating reversible routines on computational-basis branches.Source: §1 · p. 2
• Under the indexed certificate and interface closure, the classical comparison inherits the imported estimator’s spectral dependence on γ, while the realized bounded-treewidth family admits exact poly(n) Betti computation by rank over Q.The certificate’s scope is distinct from broader indexed families, which the paper evaluates under their own access certificates or lower bounds.Source: §1 · p. 2
• A low-rank separation illustrates that entrywise access can face a localization barrier while ℓ2 sample-and-query access exposes the relevant mass directly.The paper treats this as a supporting illustration of access-relative reducibility, not as its main applied certificate.Source: §1 · p. 2

• Prior end-to-end analyses note that data loading, oracle construction, precision, resource regime, and output extraction affect comparisons even when a primitive is asymptotically fast.Block-encoding and QRAM-like loading models likewise make the declared interface part of the algorithmic object [15].Source: §2 · pp. 2–3
• The paper adds a transcript-level admissibility rule: classical routes generated by the same declared implementation package enter the interface-closed baseline with their overheads charged.The rule complements rather than replaces resource estimates, oracle lower bounds, and application-specific cost models.Source: §2 · pp. 3–4
• Low-rank dequantization results motivate distinguishing declared access: sample-and-query methods can match some primitives [29] [14], with bounds refined for rank, conditioning, sampling assumptions, and precision [5].The paper asks whether supporting objects such as norm trees, unrank maps, or reversible routines are included in the declared package and charges their costs when they are.Source: §2 · p. 3
• The TDA application uses classical normalized-Betti and spectral-trace estimators as imported modules, and audits whether their required access follows from the quantum implementation package.Related homological-task analyses also treat access models and requested outputs as central to interpreting claims [16] [25].Source: §2 · p. 3
• The output-contract discussion distinguishes compact scalar-observable tasks from dense state reconstruction, whose extraction costs can change the end-to-end comparison.Table 1 separates the paper’s original interface-admissibility layer from imported estimator, dequantization, and readout modules.Source: §2 · p. 3, Table 1 · p. 4

3.1 Applied claims and output contracts

• An applied claim specifies an instance class, quantum and classical access models, an output contract, and a family of admissible classical baselines.Compact and dense output contracts distinguish transcript- or sample-based responses from requirements to produce or reconstruct many classical degrees of freedom.Source: §3.1 · pp. 4–5

3.2 Transcript-level interface admissibility

• Interface admissibility requires a classical transducer to generate valid adaptive transcripts using only the declared implementation package, public parameters, and its own randomness, with setup and transcript-generation costs charged.The transducer cannot use raw-instance access or uncharged preprocessing; approximate transcript generation charges precision conversion and amplification.Source: §3.2 · p. 5
• Abstract oracles need an implementation package, transcript reduction, or shared representation to certify matched access; an implemented interface is matched by a charged transducer, and a declared common model can certify both access types.A norm tree or unrank map can, for example, realize sample-and-query access or a uniform simplex sampler.Source: §3.2 · p. 6

3.3 Interface-closed baselines

• An interface-closed baseline includes classical algorithms using any admissible matched access model, with setup, access, reduction, and final-operation costs charged.Thus, the declared implementation package can change the admissible baseline even when the primitive-level quantum behavior is the same.Source: §3.3 · p. 6

3.4 Audit recipe

• When a matched route satisfies the output contract, interface closure admits its charged cost into the comparison; applying the rule requires an explicit admissibility certificate and overhead accounting.The audit identifies the implementation package, derives its transcripts, charges overheads, closes the baseline, and checks competitiveness under the requested output contract.Source: §3.3 · p. 7, §3.4 · p. 7

4.1.1 Task, promise, and output contract

• For clique-complex TDA, the advantage scale is vertex count n and spectral resolution 1/√γ; poly(N) equals poly(n) when N=poly(n), but scales separate when N=2Θ(n); advantage means quantum poly(n) versus classical nω(1).Source: §4.1.1 · p. 8

4.1.2 The no-free-simplex-register principle

• The TDA audit distinguishes abstract spectral interfaces, membership-based preparations, and reversible indexed implementations, each licensing different classical transcripts.Abstract interfaces license matched sampling or local-row access only when an implementation package, transcript reduction, or shared representation generates those transcripts with charged overhead.Source: §4.1.2 · pp. 8–9

4.1.3 Reversible indexed implementation and matched local access

• A reversible indexed package licenses near-uniform simplex sampling, local Laplacian-row transcripts, and normalization access through single-branch evaluation of its declared routines.The charged overhead is O(Tgen + d∆Trow + Tcount + polylog(1/ηsamp) + b); exact unranking has ηsamp = 0.Source: §4.1.3 · pp. 10–11

4.1.4 Imported normalized-Betti estimator and conditional competitiveness consequence

• Under the indexed certificate and interface closure, end-to-end classical cost inherits the imported estimator’s dependence on γ, with competitiveness conditional on its declared parameter regime.For constant γ the matched route runs in polylog(N); for γ = 1/poly(n), the imported estimator scales as n^Θ(1/√γ), and the matched route inherits that growth in N.Source: §4.1.4 · pp. 12–13

4.1.5 Membership-density obstruction

• Membership-based preparation induces rejection sampling with expected Rk(G) membership tests per accepted simplex, yielding a polylogarithmic matched sampler only when Rk(G) is polylogarithmic in N.Additional generative structure may support other classical algorithms, but must be declared and charged.Source: §4.1.5 · p. 13

4.1.6 Concrete adjudication of TDA access declarations

• Table 2 summarizes how concrete TDA access declarations are adjudicated by the interface audit and the transcripts they license.The classification concerns declared implementation interfaces, not complete quantum TDA algorithms.Source: Table 2 · p. 14, §4.1.6 · p. 14

4.1.7 Scope of the indexed certificate: bounded-treewidth realization

• A bounded-treewidth family is introduced as a realizable indexed-certificate witness with an exact bijection, while the certificate’s cheap-access condition forces the simplex count to be polynomial in n.The passage frames this as a boundary on the regime where the certificate operates.Source: §4.1.7 · p. 14
• For bounded-treewidth graphs, a reversible indexed generator bijects indices with k-simplices, yielding exactly uniform simplex sampling and zero sampling error.Membership-based preparation instead has a certified rejection route with inverse clique-density overhead unless additional generative structure is declared and charged.Source: §4.1.7 · pp. 15–16
• When this realization has polylogarithmic generation cost, its bounded-treewidth instances have polynomial-size boundary matrices and exactly computable Betti numbers in polynomial time over Q.The bounded-treewidth condition matters: the passage contrasts this implication with the clique complex of K_n, which has exponentially many simplices despite cheap unranking.Source: §4.1.7 · pp. 15–16

4.2.1 A block-sparse low-rank family

• The low-rank illustration contrasts entrywise coordinate queries with ℓ2 sample-and-query access, where sampling is paired with value queries and setup and sampling costs are charged.It uses a block-sparse low-rank family with unknown, disjoint row and column supports.Source: §4.2.1 · pp. 16–17

4.2.2 Recovery contracts

• Theorem 20 shows that the same block-sparse low-rank family and recovery contracts have different query complexities under entrywise and ℓ2 sample-and-query access.Entrywise access faces a localization barrier, while ℓ2 sampling exposes support directly.Source: §4.2 · p. 16, §4.2.2 · pp. 17–18
• Under ℓ2 sampling, one sample finds a nonzero witness, while component representatives can be obtained by sampling until all blocks are touched; entrywise access faces hidden-support localization.The entrywise lower bounds apply to randomized algorithms with constant success probability; the sampling upper bounds hold with the stated probabilities.Source: §4.2.2 · pp. 17–18

4.2.3 Interface-closure consequence

• A declared mass-exposing implementation package makes the sample-and-query algorithms part of the interface-closed classical baseline, whereas entrywise access leaves localization costs visible.The package must generate valid sample-and-query transcripts with charged overhead.Source: §4.2.3 · p. 19

5 Discussion and Conclusion

• The clique-complex TDA audit separates abstract spectral declarations, membership-based preparations, and reversible indexed implementations.Abstract spectral access needs an implementation package, transcript reduction, or shared representation; membership preparation exposes inverse clique-density overhead; indexed routines certify matched classical transcripts.Source: §5 · p. 20
• Reversible indexed routines certify matched simplex sampling, local Laplacian rows, and normalization information through single-branch evaluation.With an imported normalized-Betti estimator, this route is an admissible classical comparison; exact Betti numbers and dense outputs require separate analysis.Source: §5 · p. 20
• The same low-rank object can present a localization barrier under entrywise access yet admit a cheap reduction under ℓ2 sample-and-query access.Reducibility therefore depends on structural parameters together with the declared access model.Source: §5 · p. 20
• For covered low-rank QML and QLSA tasks, competitiveness requires certified matched sample-and-query access, compact output, an imported classical route, and an interface-closed baseline.Finite-size utility, polynomial improvements, and tasks governed by different reductions remain separate questions.Source: §5 · p. 20
• Dense classical outputs can add extraction costs, while compact contracts preserve the possibility of quantum advantage.Scalar expectations, samples, and local observables differ operationally from dense vectors or tomographic reconstructions.Source: §5 · p. 20
• Applied quantum-advantage claims should be audited using the declared interface, admissible baseline family, and operational output contract.Matched classical routes generated by the same declared package belong in the interface-closed baseline with their costs charged.Source: §5 · pp. 19–20

Proof scope

• The lower bounds count access queries only; arithmetic and output-writing costs can increase total cost.Randomized lower bounds use Yao’s minimax principle to convert a distributional deterministic bound into a worst-case randomized bound.Source: §A.1 · pp. 23–24

Witness recovery

• For witness recovery, entrywise access requires Ω(N^2/(rs^2)) queries, while one ℓ2 sample is a nonzero witness with probability one.The entrywise lower bound is worst-case over the stated class for randomized algorithms succeeding with probability at least 2/3.Source: §A.1 · pp. 23–24

Component recovery

• Component recovery costs Ω(N^2/s^2) entrywise queries, versus O(r log(r/δ)) ℓ2 samples under balanced sample-and-query access.The entrywise bound is for recovering a representative from every block; the sample bound meets the same component-representative contract.Source: §A.1 · p. 25

Structured factor recovery

• Structured factor recovery requires Ω(N^2/s^2) entrywise queries, while ℓ2 access costs O(r log(r/δ) + rs) under O(s) block-local recoverability.The contract requires the blocks, their row and column supports, and rank-one factors; the lower bound applies to that specified structured contract.Source: §A.1 · pp. 24–25

Output-contract bounds

• Scalar expectation estimation by independent sampling has ε^-2 log(1/δ) dependence; amplitude estimation can improve coherent query dependence under stronger oracle assumptions.For k observables, the direct union-bound estimate is O(kε^-2 log(k/δ)); classical-shadow bounds can improve dependence for suitable observable classes [20].Source: §A.2 · p. 25
• Table 3 summarizes conservative operational repetition or extraction costs, rather than output bit length alone.The table is presented as bounds used in the main text.Source: Table 3 · p. 26
• Dense vector output has an Ω(N) write-out lower bound, while distribution-estimation and tomography requirements depend on dimension or state class.Full distribution estimation over d outcomes has sample complexity linear in d up to metric-dependent precision factors; tomography bounds depend on the state class and metric.Source: §A.2 · p. 26

B Canonical Case Summary

• Table 4 is an orientation summary of canonical regimes, not an additional formal test.It records which of the two mechanisms in the main text is doing the work.Source: B Canonical Case Summary · p. 26

C Extended Canonical Case Analyses

• The appendix keeps the TDA analysis as the non-low-rank application that explicitly uses the admissibility criterion.The other non-TDA canonical cases are summarized in Table 4, with their evidence and citations carried in the notes.Source: C Extended Canonical Case Analyses · p. 26

C.4 TDA Betti estimation as the boundary case

• Reversible indexed simplex-generation and local Laplacian routines certify a matched classical route for normalized additive Betti output by single-branch evaluation; membership-only or hidden-algebraic regimes fall outside that certificate absent charged overheads.Any positive advantage claim still requires independent lower-bound evidence.Source: §C.4 · pp. 26–27

D.1 Access models

• Dense entrywise inputs typically require Θ(N^2) reads for representation, while sparse access does not imply low rank and ℓ2 sample-and-query access can make low-rank structure cheap to expose classically.Entrywise access is described as weak for detecting sparse hidden structure.Source: §D.1 · p. 27
• Block-encoding claims must charge construction/access cost and normalization, while QRAM or amplitude encoding must charge the assumptions needed to make the data structure available.A pre-existing amplitude oracle is not equivalent to entrywise classical data unless the baseline receives matched access.Source: §D.1 · p. 27

D.2 Output contracts

• Output contracts price the result actually needed: quantum-state return, classical-vector return, sampling, and dense probability-vector estimation are distinct requirements.Information-theoretic readout constraints begin with Holevo’s bound.Source: §D.2 · p. 27

D.3 Regime factors

• The regime multiplier ρ_R may include noise or trainability constraints in NISQ settings and physical fault-tolerance costs in later regimes; claims must declare it or cite an end-to-end estimate.The model does not prescribe a universal ρ_R.Source: §D.3 · pp. 27–28

D.4 Scaling conventions

• Use input length for exponential-versus-polynomial comparisons and log n for polynomial-versus-polynomial comparisons.Source: §D.4 · p. 28
• Use log(1/ε) for precision scaling and the relevant search-space scale for black-box search.Source: §D.4 · p. 28
• Changing the declared scale changes the reported claim.Source: §D.4 · p. 28