⚛️ quantum physics

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

This paper presents a quantum algorithm for computing persistent Betti numbers that achieves significant space and time improvements over prior methods, yet introduces a quantum-inspired classical counterpart with comparable scaling, ultimately concluding there is currently no evidence for an exponential quantum speedup on this practical task.

Original authors: Sam McArdle, András Gilyén, Mario Berta

Published 2026-04-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sam McArdle, András Gilyén, Mario Berta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy pile of data points—like a cloud of stars, a swarm of bees, or a collection of customer reviews. You want to understand the "shape" of this data. Is it a solid ball? A hollow donut? A twisted pretzel with three holes?

This is the job of Topological Data Analysis (TDA). It ignores the specific coordinates and asks: "How many holes does this shape have?" In math, these holes are called Betti numbers. If you look at the data at different levels of zoom (like looking at a map from space vs. walking on the street), you can see which holes are real and permanent, and which ones are just temporary glitches. These permanent holes are called Persistent Betti Numbers.

For a long time, scientists thought Quantum Computers could solve this problem incredibly fast—exponentially faster than any classical computer. This paper, however, is a reality check. It says, "Hold on, let's look closer."

Here is the breakdown of what the authors did, using simple analogies.

1. The Problem: The "Library" vs. The "Book"

Imagine your data is a library with $N$ books.

Classical Computers try to read every single book to find the story. If you want to know how many holes exist in a complex shape made of $N$ points, the number of possible shapes (simplices) explodes. It's like trying to read every possible combination of books in the library. The memory required is huge, and the time it takes is long.
Previous Quantum Algorithms claimed they could read the whole library in a single glance. They used $N$ quantum bits (qubits) to represent the data. They claimed this was an "exponential speedup."

The Catch: The previous quantum algorithms were like a librarian who can only tell you the percentage of books that are about "holes," not the actual number of holes. To get the real number, you have to multiply that percentage by the total number of books. If the library is huge, that multiplication step destroys the speedup. It's like knowing 1% of a billion people are doctors is easy, but calculating the exact number (10 million) takes just as much work as counting them one by one.

2. The Solution: A "Compact" Backpack

The authors built a new, streamlined quantum algorithm. Their biggest innovation is a Compact Mapping.

Old Way (The Heavy Suitcase): Previous methods tried to carry every single data point in a separate pocket. If you had 1 million points, you needed 1 million pockets (qubits). This is heavy and impractical.
New Way (The Backpack): The authors realized you don't need to carry every point. You only need to carry the coordinates of the points that make up a specific shape. Instead of 1 million pockets, you just need a backpack that can hold a few coordinates.
- The Analogy: Imagine you want to describe a triangle made of three people in a stadium.
  - Old Way: You need a ticket for every single seat in the stadium (1 million tickets) to say who is sitting where.
  - New Way: You just write down the seat numbers of the three people (e.g., "Seat 10, Seat 500, Seat 900"). You only need a tiny piece of paper.
- The Result: This saves an exponential amount of space. For practical problems, they reduced the need from a million qubits down to about 80. This is a massive win for space, even if the speed isn't as magical as hoped.

3. The "Power Method" Surprise

The authors didn't just improve the quantum algorithm; they also invented a new Classical Algorithm inspired by their quantum work.

Think of the quantum algorithm as a high-tech, expensive drone that flies over a forest to count trees.
The authors realized, "Hey, we can build a very efficient bicycle that follows the same path."
They created a "Quantum-Inspired Classical Power Method." It's not as fast as the drone, but it's much faster than the old way of walking through the forest with a clipboard.
The Result: The quantum computer is now only about quadratically faster (maybe 100 times faster) than this new bicycle, not exponentially faster (which would be a million times faster).

4. The Big Conclusion: No "Magic" Speedup (Yet)

The paper's most important message is a dose of realism.

The Claim: "Quantum computers will solve this problem instantly!"
The Reality: "Not really."
- If you want the exact number of holes (which is what real-world applications need), the quantum computer has to do a lot of extra work to convert its "percentage estimate" into a real number.
- Because of this, the "exponential speedup" vanishes. The quantum computer is faster, but only by a polynomial factor (like $N^3$ vs $N^5$ ), not an exponential one ( $2^N$ vs $N$ ).
- Furthermore, the speed depends on something called a "gap." If the data is messy and the "holes" are hard to distinguish, the computer slows down significantly.

Summary: What does this mean for you?

Space is Saved: We can now run these complex shape-analysis algorithms on quantum computers with far fewer qubits than before. This makes the hardware requirements much more realistic for the near future.
Speed is Modest: Don't expect a quantum computer to solve your data problems in a split second. It will be faster than a classical computer, but not by the "magic" factor people hoped for.
Classical is Still Strong: The authors showed that a clever new classical algorithm (the "bicycle") is so good that it closes the gap, meaning quantum computers might only have a modest advantage for now.

The Bottom Line: The authors took a "magic wand" (the previous quantum algorithm) and turned it into a "very good tool" (the new streamlined algorithm). It's a significant engineering improvement that saves space, but it's not the sci-fi instant solution we were promised. It's a step forward, but we still have a long road to travel before quantum computers dominate topological data analysis.

1. Problem Statement

Topological Data Analysis (TDA) aims to extract robust geometric and topological features from high-dimensional, noisy datasets. A central task in TDA is computing persistent Betti numbers ( $\beta_{k}^{i,j}$ ), which quantify the number of $k$ -dimensional holes (topological features) that exist at a length scale $i$ and persist until scale $j$ .

Challenges with existing approaches:

Classical Algorithms: Computing persistent Betti numbers involves linear algebra on simplicial complexes. For a dataset with $N$ points, the number of $k$ -simplices can scale as $\binom{N}{k+1}$ . Classical algorithms (e.g., matrix reduction) generally scale polynomially in the number of simplices, becoming computationally prohibitive for dense complexes or high dimensions.
Previous Quantum Algorithms: Early quantum algorithms (e.g., Lloyd et al.) claimed exponential speedups. However, they suffered from two major issues:
1. Space Complexity: They required $O(N)$ qubits to represent $N$ data points directly, which is a massive resource overhead.
2. Normalization Issue: Many quantum algorithms estimate the normalized Betti number (ratio of holes to total simplices). To recover the actual integer count $\beta_{k}^{i,j}$ , one must multiply by the total number of simplices, reintroducing a super-polynomial factor that negates the claimed exponential speedup for constant additive error.
3. Gap Dependence: The runtime depends on the spectral gap of the operators used, which was not well-understood for practical datasets.

2. Methodology

The authors propose a streamlined quantum algorithm based on Quantum Singular Value Transformation (QSVT) that addresses the space and normalization issues.

A. Core Algorithmic Framework

Instead of using the combinatorial Laplacian (as in previous works), the authors directly estimate the rank of projectors derived from the boundary operators. The persistent Betti number is defined as:
$\beta_{k}^{i,j} = \dim(\ker(\partial_k^i)) - \dim(\ker(\partial_k^i) \cap \text{Im}(\partial_{k+1}^j))$
The algorithm estimates the normalized rank of the projector $\Pi_{\beta} = \Pi_{\ker} - \Pi_{\ker \cap \text{Im}}$ using Amplitude Estimation. This involves:

Block Encoding: Constructing unitary block encodings for the boundary operators $\partial_k^i$ and $\partial_{k+1}^j$ .
QSVT: Applying polynomial transformations to these block encodings to create projectors onto the kernel ( $\Pi_{\ker}$ ) and the intersection of the kernel and image ( $\Pi_{\ker \cap \text{Im}}$ ).
Amplitude Estimation: Estimating the expectation value of these projectors to determine the rank.

B. Key Innovation: Compact Mapping

The most significant technical contribution is a new compact mapping of simplices to qubits:

Direct Mapping (Previous): Uses $N$ qubits to represent $N$ data points. A $k$ -simplex is a Hamming-weight $(k+1)$ state. Space complexity: $O(N)$ .
Compact Mapping (New): Uses $(k+1)\lceil \log_2 N \rceil$ $(k + 1) ⌈ lo g_{2} N ⌉$ qubits. Each of the $k+1$ $k + 1$ registers stores the index of a vertex in binary.
- Result: For $k = O(\text{polylog}(N))$ , the space complexity drops from $O(N)$ to $O(\log N)$ . This provides an exponential reduction in qubit count compared to previous quantum algorithms and classical storage requirements for dense complexes.

C. Subroutines

Membership Oracle: A quantum subroutine that determines if a specific set of vertices forms a valid simplex at a given length scale. The authors provide efficient implementations for both direct and compact mappings, utilizing quantum lookup tables (QROM/QRAM).
Gap Parameters: The algorithm's complexity depends on spectral gaps:
- $\Lambda_{\partial}$ : The smallest non-zero singular value of the boundary operators.
- $\Lambda_{\Pi\Pi}$ : A gap parameter related to the singular values of the product of projectors $\Pi_{\ker}\Pi_{\text{Im}}$ . This arises because the projectors do not commute when $i \neq j$ .

3. Key Contributions

Exponential Space Saving: The introduction of the compact mapping reduces the required logical qubits from $O(N)$ to $O(k \log N)$ . For practical scenarios (e.g., $N=10^6, k=3$ ), this reduces the qubit count from $10^6$ to roughly 80.
Polynomial Time Improvement: The algorithm achieves a large polynomial improvement in time complexity over previous quantum algorithms (e.g., Hayakawa [17]) and existing classical algorithms for dense complexes.
- The gate depth scales roughly as $\tilde{O}(N^{3.5})$ for dense complexes, compared to $\tilde{O}(N^{10})$ for classical worst-case scenarios.
Rigorous Complexity Analysis: The authors provide a full end-to-end complexity analysis, explicitly accounting for the normalization issue. They demonstrate that while the algorithm offers a polynomial speedup, the "exponential speedup" claimed in earlier literature for computing the actual Betti number (not just the normalized ratio) is lost due to the need to multiply by the number of simplices.
Quantum-Inspired Classical Algorithm: The authors introduce a classical power method algorithm inspired by their quantum approach.
- This classical algorithm scales only quadratically worse than the quantum algorithm in terms of the number of simplices.
- It has the same dependence on spectral gaps.
- This implies that the quantum algorithm cannot achieve better than a quadratic speedup over this specific classical heuristic for the task of estimating persistent Betti numbers to constant additive error.

4. Results and Complexity

Theorem 1 (Complexity): For a dense simplicial complex with $N$ $N$ points, the algorithm estimates $\beta_{k}^{i,j}$ $β_{k}^{i, j}$ to additive error $\Delta$ $Δ$ with success probability $1-\eta$ $1 - η$ using:
- Qubits: $O(\min\{k \log N, N\})$ (Exponential saving with compact mapping).
- Gate Depth: $\tilde{O}\left( \frac{N^{3/2} \sqrt{k \beta_{k}^{i,j} \binom{N}{k+1}}}{\Delta \Lambda_{\Pi\Pi}^{0.5} \min(\Lambda_{\partial_k^i}, \Lambda_{\partial_{k+1}^j})} \right)$ .
Comparison to Classical:
- Classical textbook algorithms scale as $O(|S|^3)$ or $O(|S|^\omega)$ where $|S| \approx \binom{N}{k+1}$ .
- The quantum algorithm offers an almost quintic speedup ( $N^{3.5}$ vs $N^{10}$ ) in the number of data points for dense complexes, subject to gap assumptions.
Comparison to Previous Quantum:
- The new algorithm is significantly more efficient in both space and time compared to Ref. [17].
- It avoids the complex basis changes required by persistent Laplacian approaches.

5. Significance and Conclusions

Re-evaluating Quantum Advantage: The paper concludes that there is no current evidence for an exponential quantum speedup for the practical task of computing persistent Betti numbers to constant additive error. The best achievable advantage is likely polynomial (and potentially limited to quadratic by the new classical heuristic).
Practical Utility: Despite the lack of exponential speedup, the exponential reduction in qubit count is a critical contribution. It makes TDA feasible on near-term and early fault-tolerant quantum devices where qubit count is the primary bottleneck.
Gap Dependence: The viability of the algorithm hinges on the scaling of spectral gaps ( $\Lambda$ ) with $N$ . If these gaps decay exponentially, the speedup vanishes. The authors note that for random geometric complexes, Betti numbers are typically small ( $O(N)$ ), which limits the potential for large polynomial speedups even in the relative error regime.
Future Directions: The work establishes a "quantum-native" framework for TDA using QSVT. Future work should focus on determining the scaling of gap parameters for real-world datasets and identifying specific application domains where high-dimensional persistent Betti numbers are large enough to justify the computational cost.

In summary, this paper provides a rigorous, resource-efficient quantum algorithm for TDA that corrects previous over-optimistic claims of exponential speedup while delivering a crucial exponential reduction in hardware requirements (qubits), making the field more accessible for practical quantum implementation.