Thesis
QTDA — computing the Betti numbers of a simplicial complex via quantum projection onto the kernel of a combinatorial Laplacian — was the canonical example of an exponential-speedup quantum algorithm for a 'natural' data-analysis task. Lloyd–Garnerone–Zanardi (2014) and follow-ups give an O(poly log N) routine for a problem whose best classical algorithms scale polynomially in N. The question of whether this represents a true Shor-level breakthrough hinges entirely on the dequantization frontier: Apers–Gribling, Gharibian–Le Gall and others have classical algorithms with overlapping regimes, while Quantinuum's 2023–2024 H-series demonstrations show end-to-end QTDA on real hardware. The most likely outcome is a 'conditional Shor': a real exponential separation on data structures with high Betti-to-simplex ratio that classical sampling cannot exploit.
Scoring
Genuine candidate for end-to-end exponential separation, but threatened by ongoing classical sampling improvements. Resource-cost-favourable (small qubit counts work meaningfully), and the only family in this dashboard with a working hardware demo at modest scale.
Open problems
- ·Identifying datasets with provably high Betti-to-simplex ratio resistant to classical sampling.
- ·Closing the gap between Lloyd-style heuristic speedup and Berry-style provable speedup.
- ·Block-encoding the boundary operator efficiently for sparse complexes.
- ·QTDA on persistence (filtration of complexes), not just a single complex.
- ·Hardware demonstrations beyond ~20-simplex toys.
Demo · pre-computed on the Selene emulator
QTDA — SWAP-test fidelity matrix and Vietoris-Rips graph
Each cell is the inner-product fidelity between two amplitude-encoded patient states, estimated from 1000 Selene shots per pair. Edges form when fidelity ≥ threshold; Betti-0 counts connected components. A canonical hardware demonstration ran a 28-pair version on the H-series (Akhalwaya et al. 2023).
Key papers (8)
arXiv:1408.3106The original QTDA paper. Claims exponential speedup for Betti number estimation over the best then-known classical algorithms.
arXiv:2209.12887First QTDA algorithm with rigorous, end-to-end speedup analysis — clarifies the regime where quantum is genuinely faster.
arXiv:2303.01492Provides classical algorithms matching QSVT-based QTDA under sampling access — bounds where QTDA's exponential edge actually survives.
arXiv:2206.02639Resource-estimates QTDA on near-term and early-FT devices; identifies instance families with concrete quantum advantage.
arXiv:2209.13581Argues that high-Betti-number regimes resist all known classical sampling attacks — likely home of any future QTDA quantum advantage.
arXiv:2209.14286Shows that Betti-number estimation in the worst case is #P-hard, so any exponential speedup must come from structure — not from the problem class alone.
arXiv:2211.12489Methodologically representative end-to-end FT resource analysis applied to data problems — the same lens being used for QTDA.
arXiv:2209.09371End-to-end NISQ QTDA demonstration on IBM hardware — small but real evidence that the pipeline runs. Accepted at ICLR 2024.