Quantum speedup limits depend on input methods and output requirements
When Does a Quantum Speedup Survive End-to-End?
Computational Complexity
Summary
Quantum computers can sometimes solve problems faster than classical ones, but whether this speed advantage holds true depends on exactly how you feed data in and get answers out. The authors study how different ways of accessing and using a quantum routine affect its overall cost and speed, using a detailed model of interactions. They focus on a complex math problem called Betti number estimation, showing that some quantum speedups may disappear when considering the entire process, while others can survive with the right interfaces. Their work helps clarify when quantum speedups are meaningful from start to finish.
What this means in practice
- •For quantum algorithm developers: Assess the true end-to-end efficiency of quantum algorithms given specific input-output models and their overhead costs.
- •For topological data analysts: Choose appropriate classical or quantum methods for Betti number computation based on problem complexity and interface constraints.
A theory result. No direct application yet.
Authors
Pablo Herrero Gómez, Antonio Jimeno Morenilla, David Muñoz Hernández, Higinio Mora Mora
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 \(A_M\preceq_{\mathrm{int}}A_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 \(\binom{n}{k+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 \(\mathrm{poly}(n)\) classical Betti computation by rank over \(\mathbb{Q}\). A low-rank separation supports the role of access and output contracts.