pith. sign in

arxiv: 2209.12887 · v3 · submitted 2022-09-26 · 🪐 quant-ph

A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits

Sam McArdle , Andr\'as Gily\'en , Mario Berta This is my paper

Pith reviewed 2026-05-24 11:32 UTC · model grok-4.3

classification 🪐 quant-ph
keywords topological data analysispersistent Betti numbersquantum algorithmquantum-inspired classical algorithmpersistent homologycomplexity analysismachine learning
0
0 comments X

The pith

Improved quantum algorithm for persistent Betti numbers uses exponentially fewer qubits but a classical power method scales nearly as well.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a quantum algorithm for topological data analysis that computes persistent Betti numbers with large polynomial time improvements and an exponential reduction in qubit count over earlier quantum methods. Subject to gap dependencies, it delivers an almost quintic speedup versus the best known rigorous classical algorithms for constant additive error. The authors also introduce a quantum-inspired classical power method whose scaling is only quadratically worse than their quantum algorithm. This leads to the conclusion that there is currently no evidence for exponential quantum speedups on tasks of practical interest.

Core claim

The central claim is that a streamlined quantum algorithm achieves polynomial time improvements and exponential space savings over existing quantum algorithms for persistent Betti numbers, while a newly introduced quantum-inspired classical power method has provable scaling only quadratically worse than the quantum one, implying that exponential quantum speedups are not currently supported for computing these topological invariants to constant additive error.

What carries the argument

The streamlined quantum algorithm for persistent Betti numbers that reduces qubit requirements, paired with the quantum-inspired classical power method.

If this is right

  • Persistent Betti numbers can be computed with polynomial time speedups in the quantum setting over prior quantum methods.
  • Exponential savings in the number of qubits become available for topological data analysis.
  • A rigorous classical algorithm exists whose scaling is only quadratically worse than the quantum version.
  • No exponential quantum advantage is evidenced for computing persistent Betti numbers to constant additive error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Quantum-inspired classical methods could be applied to other proposed quantum algorithms to test for hidden exponential advantages.
  • Topological data analysis tasks in machine learning may be addressable with classical resources at comparable cost.
  • Empirical checks of the gap assumptions on real datasets would determine whether the claimed speedups materialize.
  • Strong classical baselines should be developed alongside new quantum proposals in related areas.

Load-bearing premise

The speedups and space savings hold only under gap dependencies such as sufficient spectral gaps in operators or data separation.

What would settle it

A concrete dataset where the classical power method requires more than quadratic overhead relative to the quantum algorithm or where the quantum algorithm fails to deliver the polynomial improvements because gaps are too small.

Figures

Figures reproduced from arXiv: 2209.12887 by Andr\'as Gily\'en, Mario Berta, Sam McArdle.

Figure 1
Figure 1. Figure 1: FIG. 1. An example subset of datapoints arising from an [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. A standard QSVT circuit template. See Ref. [ [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Recompiling a block of the above QSVT circuit using an additional ancilla qubit. [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Implementing the C [PITH_FULL_IMAGE:figures/full_fig_p030_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. A layer of the QSVT implementation of fixed-point amplitude amplification used to implement the projected unitary [PITH_FULL_IMAGE:figures/full_fig_p033_5.png] view at source ↗
read the original abstract

Topological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over previously known rigorous classical algorithms for computing the persistent Betti numbers to constant additive error - the salient task for applications. However, we also introduce a quantum-inspired classical power method with provable scaling only quadratically worse than the quantum algorithm. This gives a provable classical algorithm with scaling comparable to existing classical heuristics. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence for this being the case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript presents a quantum algorithm for computing persistent Betti numbers in topological data analysis that uses exponentially fewer qubits than prior quantum methods, together with an end-to-end complexity analysis. It claims large polynomial time improvements and, subject to gap dependencies, an almost quintic speedup in the number of datapoints over known rigorous classical algorithms for constant additive error. The paper also introduces a quantum-inspired classical power method whose scaling is only quadratically worse than the quantum version and concludes that there is currently no evidence for exponential quantum speedups on tasks of practical interest.

Significance. If the gap assumptions hold, the work supplies tighter resource estimates for quantum TDA and shows that a simple classical power method can match the scaling of existing heuristics while remaining rigorously analyzed. The explicit end-to-end analysis and the side-by-side quantum-classical comparison are strengths that help clarify the practical prospects for quantum advantage in this domain.

major comments (3)
  1. [§4] §4 (end-to-end complexity analysis): the quintic speedup claim over classical algorithms is conditioned on gap dependencies of the boundary operators, yet no explicit lower bounds on these gaps are derived from standard TDA input assumptions (e.g., minimum separation or sampling density of the point cloud). Without such bounds it is unclear whether the gaps remain inverse-polynomial in the number of points for generic data, which is load-bearing for the headline comparison.
  2. [§3.2] §3.2 (quantum algorithm description): the exponential qubit saving is stated relative to prior quantum TDA algorithms, but the precise qubit count scaling (including the dependence on the filtration parameter and the number of simplices) is not compared equation-by-equation with the earlier constructions; this makes the magnitude of the improvement difficult to verify.
  3. [§5] §5 (classical power method): the claimed quadratic gap between the quantum and classical power-method scalings relies on the same gap assumptions; if those gaps are only inverse-polylogarithmic, the classical method would lose its claimed near-competitiveness with the quantum runtime.
minor comments (2)
  1. Notation for the persistent Betti numbers and the filtration parameter is introduced without a compact reference table; adding one would improve readability.
  2. Several complexity expressions in the abstract and introduction use big-O notation without explicitly listing the hidden polylog factors; making these explicit would help readers compare with prior work.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address each major comment below, providing clarifications and committing to revisions where appropriate to improve the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (end-to-end complexity analysis): the quintic speedup claim over classical algorithms is conditioned on gap dependencies of the boundary operators, yet no explicit lower bounds on these gaps are derived from standard TDA input assumptions (e.g., minimum separation or sampling density of the point cloud). Without such bounds it is unclear whether the gaps remain inverse-polynomial in the number of points for generic data, which is load-bearing for the headline comparison.

    Authors: We agree that the quintic speedup is conditional on the spectral gaps and that the manuscript does not derive new explicit lower bounds from TDA input assumptions. The paper already qualifies all claims with 'subject to gap dependencies.' Under standard assumptions such as minimum point separation (common in TDA to ensure non-degenerate complexes), existing results from random matrix theory and simplicial Laplacian perturbation bounds imply inverse-polynomial gaps; we will add a short clarifying paragraph with references in §4 to make this connection explicit without claiming a new derivation. revision: partial

  2. Referee: [§3.2] §3.2 (quantum algorithm description): the exponential qubit saving is stated relative to prior quantum TDA algorithms, but the precise qubit count scaling (including the dependence on the filtration parameter and the number of simplices) is not compared equation-by-equation with the earlier constructions; this makes the magnitude of the improvement difficult to verify.

    Authors: We thank the referee for this observation. We will insert an explicit side-by-side comparison (new table or aligned equations) in §3.2 that lists qubit counts for our algorithm versus prior constructions (Lloyd et al., 2016 and subsequent works), showing the precise dependence on n (datapoints), filtration value, and number of simplices for both state preparation and phase estimation steps. This will make the exponential saving transparent. revision: yes

  3. Referee: [§5] §5 (classical power method): the claimed quadratic gap between the quantum and classical power-method scalings relies on the same gap assumptions; if those gaps are only inverse-polylogarithmic, the classical method would lose its claimed near-competitiveness with the quantum runtime.

    Authors: The quadratic separation is indeed governed by the same gap parameter that appears in both runtimes. Our statement is that, under identical gap assumptions, the classical power method is only quadratically slower than the quantum version. We will revise §5 to restate this conditional comparison more explicitly and add a short remark on the practical implication if gaps prove smaller than inverse-polynomial. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central claims rest on an end-to-end complexity analysis that explicitly conditions all speedups on gap dependencies (spectral gaps or data separation), introduces an independent quantum-inspired classical power method, and compares against prior rigorous classical algorithms without reducing any prediction or uniqueness claim to a fitted parameter or self-citation chain. No equations or steps are shown to be equivalent to inputs by construction, and the gap condition is presented as an external assumption rather than internally derived. The derivation therefore remains self-contained with independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the gap dependencies are stated as conditions rather than derived quantities.

pith-pipeline@v0.9.0 · 5704 in / 1199 out tokens · 31522 ms · 2026-05-24T11:32:02.718126+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes

    quant-ph 2025-06 unverdicted novelty 8.0

    Quantum algorithms achieve polylogarithmic complexity for Betti number estimation and homology testing via block-encoded Laplacians and cohomological projections, claiming exponential speedups under sparsity assumptions.

  2. Efficient Quantum Algorithms for Higher-Order Coupled Oscillators

    quant-ph 2026-04 unverdicted novelty 7.0

    Quantum algorithms achieve polynomial advantage for synchronization estimation and super-polynomial advantage for no-phase-locking certification in higher-order simplicial Kuramoto models under stated assumptions.

  3. Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis

    quant-ph 2025-08 unverdicted novelty 6.0

    Hybrid quantum-classical method for Betti number estimation that combines classical simplex enumeration with quantum processing and claims polynomial-to-exponential speedups over existing quantum algorithms at the cos...

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 3 Pith papers

  1. [1]

    number of k-holes present at i still present at j) C i,j k+1(Sj) The subgroup of ( k + 1)-chains in Ck+1(Sj) mapped to k-chains in Ck(Si) by ∂j k+1

    Computing persistent Betti numbers Symbol Meaning Hi,j k The (j− i)-th persistent k-th Homology group βi,j k The (j− i)-th persistent k-th Betti number (i.e. number of k-holes present at i still present at j) C i,j k+1(Sj) The subgroup of ( k + 1)-chains in Ck+1(Sj) mapped to k-chains in Ck(Si) by ∂j k+1. ∂i,j k+1 The boundary operator ∂k+1 restricted to ...

    work page

  2. [2]

    the k-cycles Ker(∂i k))

    Counting all the k-holes and k-boundaries in Si (i.e. the k-cycles Ker(∂i k))

    work page

  3. [3]

    Removing those k-cycles in Si that are k-boundaries in Sj (this is given by Ker( ∂i k)∩ Im(∂j k+1) [19]) We do not have to worry about double-counting the k-boundaries in Si and Sj, as all k-boundaries in Si are also k-boundaries in Sj, because all simplices in Si are also in Sj. Formally, we can define the ( j− i)-th persistent k-th homology group as [19]...

    work page

  4. [4]

    Theorem 2: Formal version and proof We will prove a formal version of Theorem 2, which we state here: Consider the orthogonal projectors Π ⊆ ˜Π, with rank(Π) := dg, rank( ˜Π) := d. If we treat Π as an observable and ρ := ˜Π/rank( ˜Π) as a quantum state, then the ratio of the ranks rank(Π) rank(˜Π) equals Π’s expectation value when evaluated on the mixed s...

    work page

  5. [5]

    Corollary 2.1: Applying Theorem 2 to estimate persistent Betti numbers As discussed in the main text, we can estimate persistent Betti numbers using the following expression βi,j k = dim ( Ker(∂i k) ) − dim ( Ker(∂i k)∩ Im(∂j k+1) ) . (B9) We estimate the dimensions of projectors ΠKer and ΠKer∩Im, where ΠKer projects onto Ker(∂i k) and ΠIm projects onto I...

    work page

  6. [6]

    Given a projector Π = ∑dg i=1|πi⟩⟨ πi|, define|ψ⟩ as a purified maximally mixed state over a d dimensional basis (with d≥ dg), such that Π has full support on |ψ⟩

    Technical Lemmas Lemma 2. Given a projector Π = ∑dg i=1|πi⟩⟨ πi|, define|ψ⟩ as a purified maximally mixed state over a d dimensional basis (with d≥ dg), such that Π has full support on |ψ⟩. We can express |ψ⟩ = √ dg d|ψg⟩ +|φ⊥⟩, where|ψg⟩ ,|φ⊥⟩ are defined by their action under Π, such that Π acts as|ψg⟩⟨ ψg| in the 2D subspace spanned by |ψg⟩ ,|φ⊥⟩. Proof. ...

    work page

  7. [7]

    The membership oracle acts as Oi mk|sk⟩| a⟩ =|sk⟩| a⊕ m(sk)⟩ (C1) where we have defined the membership function m(sk) = { 1 if sk∈ Si k 0 if sk /∈ Si k

    Membership oracle construction As discussed in the main text, the algorithm makes regular calls to a membership oracle Oi mk which determines if a simplex is present in the complex at scale i (or not) based on the positions of the vertices {⃗ rα}, and the length scale µi considered. The membership oracle acts as Oi mk|sk⟩| a⟩ =|sk⟩| a⊕ m(sk)⟩ (C1) where w...

    work page

  8. [8]

    A summary of our results are present in Table XI

    Boundary operator implementation In this section we determine the resource estimates to construct projected unitary encodings of the relevant boundary operators ∂i k and ∂j k+1. A summary of our results are present in Table XI. Our compact mapped approach proceeds by swapping the vertex to be deleted into the final position of the register, and then settin...

    work page

  9. [9]

    • VΠIm: A projected unitary encoding of Π Im, the projector onto the image of ∂j k+1

    Projected unitary encodings of subspace projectors In this section we discuss how to implement the following projected unitary encodings: • VΠKer: A projected unitary encoding of Π Ker, the projector onto the kernel of ∂i k. • VΠIm: A projected unitary encoding of Π Im, the projector onto the image of ∂j k+1. • VΠΠ: A projected unitary encoding of Π Ker∩I...

    work page

  10. [10]

    We do this by constructing circuits that prepare a purification of the maximally mixed state over all possible k-simplices

    Preparing projected unitary encoding Vψm In this section we will discuss how to prepare the projected unitary encoding Vψm of the operator |ψm⟩⟨ ¯0| where |ψm⟩ is the purified maximally mixed state over k-simplices in the complex at scale i. We do this by constructing circuits that prepare a purification of the maximally mixed state over all possible k-simp...

    work page

  11. [11]

    We have the following costs: • Vψm : (1 , 1, ϵψ) projected unitary encoding, using √ ( N k+1) |Si k| log ( 1 ϵψ ) × [UUni + Omi k ]

    Direct mapping We focus first on the comparatively more simple case of the direct mapping. We have the following costs: • Vψm : (1 , 1, ϵψ) projected unitary encoding, using √ ( N k+1) |Si k| log ( 1 ϵψ ) × [UUni + Omi k ]. – UUni : k log(N) – Omi k : N log(N) • VΠΠ : ( 1, 5, 1 ΛΠΠ log ( ϵ−1 p )√ϵk + ϵi + ϵp ) projected unitary encoding, using 1 ΛΠΠ √ N Mi...

    work page

  12. [12]

    We have the following costs: • Vψm : ( 1, 2, ϵψ + 4 √ ( N k+1) |Si k| log ( 1 ϵψ )√√ϵs +√ϵm ) projected unitary encoding, using √ ( N k+1) |Si k| log ( 1 ϵψ ) × [UUni + Omi k ]

    Compact mapping We now focus on the compact mapping using a QROM to implement the membership oracle. We have the following costs: • Vψm : ( 1, 2, ϵψ + 4 √ ( N k+1) |Si k| log ( 1 ϵψ )√√ϵs +√ϵm ) projected unitary encoding, using √ ( N k+1) |Si k| log ( 1 ϵψ ) × [UUni + Omi k ]. – UUni : (log(N) + k log(k)) √ (k+1)k+1 (k+1)! log ( 1 ϵs ) – Omi k : √ k log ...

    work page

  13. [13]

    In this work, we compute βi,j k as βi,j k = dim ( Ker(∂i k) ) − dim ( Ker(∂i k)∩ Im(∂j k+1) )

    Performing a change of basis As discussed in the main text, there are a number of nuances associated with building operators that can encode persistent Betti numbers. In this work, we compute βi,j k as βi,j k = dim ( Ker(∂i k) ) − dim ( Ker(∂i k)∩ Im(∂j k+1) ) . (E1) Nevertheless, there are other ways this problem can be formulated. For example, the task ...

    work page

  14. [14]

    We can identify these chains by performing column reduction on the matrix Dj

    work page

  15. [15]

    Such a matrix Y can be found by doing a singular value decomposition of Dj

    We need to find a non-singular matrix Y such that Rj 2 = Dj 2Y is column-reduced. Such a matrix Y can be found by doing a singular value decomposition of Dj

    work page

  16. [16]

    As a result, Y has acted as a change of basis, from the simplicial basis, to a basis of chains that has, as a subset, a basis of C i,j 2 (Sj)

    In this example, we use the matrix Y =   α β γ δ 1 0 0 0 ABC 1 1 0 0 ACD 0 0 1 1 ABD 0 0 0 1 BCD   such that Rj 2 = ( α β γ δ 0 1 0 0 AC 0 0 1 0 BD ) 40 We can see from Rj 2 and Y that the columns indexed by α, δ are in the kernel of Dj 2, and correspond to the chains α = c1 = ABC + ACD, δ = c2 = ABD + BCD , as found earlier. As a result, Y has acte...

    work page

  17. [17]

    [14] it is suggested that it is possible to compute the persistent Betti numbers using only the original quantum algorithm presented in Ref

    Persistent Betti numbers from the quantum Zeno effect In Ref. [14] it is suggested that it is possible to compute the persistent Betti numbers using only the original quantum algorithm presented in Ref. [13] for the calculation of Betti numbers. The suggested approach is to initially perform phase estimation with the combinatorial Laplacian at scale µ1, re...

    work page

  18. [18]

    As the value of µ used to construct the combinatorial Laplacian is increased, there is no change until µj = dAX

    At scale i with µi = dAB, the hole AB + BC + CD− AD is created. As the value of µ used to construct the combinatorial Laplacian is increased, there is no change until µj = dAX. As this stage, we can see that the hole still persists. However, objects in the kernel of the combinatorial Laplacian are the harmonic representative of the homology group, and so ...

    work page

  19. [19]

    As the quantum algorithm for Betti numbers works by sampling eigenstates at random, we are only able to count the fraction of eigenstates of ∆ i 1 with zero eigenvalue

    Imagine a complex that consists of many copies of this system, separated by a large distance. As the quantum algorithm for Betti numbers works by sampling eigenstates at random, we are only able to count the fraction of eigenstates of ∆ i 1 with zero eigenvalue. If we then try to project these zero eigenstates onto the eigenstates of ∆ j 1, we would erron...

    work page