When Does a Quantum Speedup Survive End-to-End?
Abstract
Primitive quantum speedups are interface-relative: they depend on the input access used to run the primitive and on the output contract used to consume its state or samples. This paper introduces a transcript-level admissibility relation AM⪯intAQ, defined relative to the declared implementation package of the quantum interface. It identifies which adaptive classical access transcripts that same package licenses, with all setup, transcript-generation, and precision overheads charged. The main application is an operational audit for normalized-Betti estimation in clique-complex TDA, separating three declared-interface regimes. Reversible indexed simplex interfaces certify matched classical simplex sampling and local Laplacian row access by evaluating their reversible routines on single computational branches. Membership-based preparations induce a rejection route of overhead binomnk+1/|Sk|. Abstract spectral or block-encoding interfaces require an accompanying implementation package, transcript reduction, or shared representation. Under the indexed certificate and interface closure, the end-to-end cost is fixed by the imported estimator's spectral dependence on the gap γ; the concretely realized bounded-treewidth family already admits exact poly(n) classical Betti computation by rank over ℚ. A low-rank separation supports the role of access and output contracts.
Related
- Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup
- Exponential speedup of polarization stabilization for long distance DWDM quantum networks
- Exponential quantum speedup for 𝔽3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
- Towards verifiable quantum advantage with random circuits: Observables that survive concentration
- Do Quantum Measurement Advantages Survive to Astrophysical Inference? Seven Benchmarks in Optical Interferometry and Imaging
BibTeX
@misc{gomez2026when,
title = {{When Does a Quantum Speedup Survive End-to-End?}},
author = {Pablo Herrero Gómez and Antonio Jimeno Morenilla and David Muñoz Hernández and Higinio Mora Mora},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09850},
eprint = {2609.09850},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09850},
}
RIS
TY - UNPB
TI - When Does a Quantum Speedup Survive End-to-End?
AU - Pablo Herrero Gómez
AU - Antonio Jimeno Morenilla
AU - David Muñoz Hernández
AU - Higinio Mora Mora
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09850
UR - https://arxiv.org/abs/2609.09850
AB - Primitive quantum speedups are interface-relative: they depend on the input access used to run the primitive and on the output contract used to consume its state or samples. This paper introduces a transcript-level admissibility relation A_M⪯_intA_Q, defined relative to the declared implementation package of the quantum interface. It identifies which adaptive classical access transcripts that same package licenses, with all setup, transcript-generation, and precision overheads charged. The main application is an operational audit for normalized-Betti estimation in clique-complex TDA, separating three declared-interface regimes. Reversible indexed simplex interfaces certify matched classical simplex sampling and local Laplacian row access by evaluating their reversible routines on single computational branches. Membership-based preparations induce a rejection route of overhead binomnk+1/|S_k|. Abstract spectral or block-encoding interfaces require an accompanying implementation package, transcript reduction, or shared representation. Under the indexed certificate and interface closure, the end-to-end cost is fixed by the imported estimator's spectral dependence on the gap γ; the concretely realized bounded-treewidth family already admits exact poly(n) classical Betti computation by rank over ℚ. A low-rank separation supports the role of access and output contracts.
ER -