Research map / Learning theory and algorithms / Prediction and decision losses

Topological data analysis on noisy quantum computers

ICLR 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments · 12 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes NISQ-TDA, a short-depth hybrid quantum-classical algorithm for estimating normalized Betti numbers of Vietoris-Rips complexes that avoids data loading and fault tolerance, and demonstrates it on Quantinuum H1 hardware and noisy simulators.

Problem

Computing Betti numbers (topological data analysis) classically is computationally prohibitive for high-order features, and the original quantum TDA algorithm requires fault-tolerant quantum computing and suffers from data-loading costs.

Approach

Encodes the full fermionic boundary operator as a sum of Pauli operators, injects the data-defined complex via multi-qubit control gates in a repeatable projector P_Gamma (with mid-circuit measurement and rejection sampling), and estimates Betti numbers via stochastic trace estimation with random Hadamard vectors and Chebyshev polynomial approximation of the step function (qubitization), so data i

Key results

• Circuit depth for the Laplacian scales linearly with number of vertices on Quantinuum H1 (12-qubit trapped-ion) hardware and simulators.
• In noisy simulations with n=8, the mean Betti number estimate converges to about 1.84 versus true beta_0=2, with variance decreasing as the number of random vectors increases.
• Theory gives a total complexity of O((1/eps^2) max{n log(1/eps)/sqrt(delta), n/zeta_k}) with depth O~(n/sqrt(delta)).

Measured effects reported in the paper

Surprising findings

• Noisy simulations show the estimate tolerates noise levels with mean error below the 0.5 rounding threshold, suggesting robustness despite hardware errors.

Limitations

• Speedup is only provable under restrictive conditions (simplex-dense complexes, 1/poly(n) spectral gap, large Betti numbers); exact Betti number estimation for clique complexes is QMA1-hard.
• Experiments are limited to small complexes (up to 8 vertices) that are classically simulable; quantum advantage not demonstrated.
• Projection onto the complex on sparsely connected devices needs O(n) depth sorting networks and repeat-until-success overhead of 1/zeta_k.

Experimental setup

Datasets: synthetic simplicial complexes (edge, square, cube, small point sets) CMB data (preliminary, in appendix)

Benchmarks: Betti number estimation on small complexes (edge, square, cube)

Metrics: Betti number estimate error circuit depth probability histograms vs simulator

Baselines: QTDA (Lloyd et al. 2016) GUDHI

Builds on: Quantum TDA (Lloyd, Garnerone, Zanardi) Jordan-Wigner transformation qubitization stochastic trace estimation

Closest papers by meaning

• QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design (NeurIPS 2025 · similarity 0.85)
• A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.84)
• SSL4Q: Semi-Supervised Learning of Quantum Data with Application to Quantum State Classification (ICML 2024 · similarity 0.83)
• Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · similarity 0.83)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms (NeurIPS 2024 · similarity 0.83)
• Neural Auto-designer for Enhanced Quantum Kernels (ICLR 2024 · similarity 0.83)