Quantifying Quantum Advantage for Topological Data Analysis
A recent paper that focuses on quantum topological data analysis (TDA) proposes a quantum algorithm that uses the combinatorial Laplacian to estimate Betti numbers, which are critical for identifying topological features like holes in various dimensions.
Quantum Topological Data Analysis
Topological Data Analysis is an approach that relies on persistent homology to study the properties of data. One way to perform TDA is to analyze the spectrum of combinatorial Laplacian. The number of zero eigenvalues (kernel) of combinatorial Laplacian corresponds to number of connected components of a graph, which is the zeroth Betti number (β₀).
Topological Data Analysis holds potential for advancing the field, but TDA is computationally challenging. The number of k-simplices in a simplicial complex grows exponentially with k and the size of the boundary matrices also grows exponentially, roughly nᵏ. Standard linear algebra operations like matrix inversion or finding null spaces (kernels) typically scale 𝒪(n³) for a matrix of size n × n. For a boundary matrix of size nᵏ × nᵏ, the computational cost becomes prohibitively large for higher dimensions k.
An important objective is to reduce the exponential computational complexity of TDA, and the question is whether quantum computers can accelerate the calculation of Betti numbers by reducing the numbers of steps needed to analyze the kernel of the combinatorial Laplacian.
In “Analyzing Prospects for Quantum Advantage in Topological Data Analysis”, published earlier this year in the prestigious journal PRX Quantum from the American Physical Society, the researchers propose a new quantum algorithm that improves upon previous methods for estimating Betti numbers using quantum computers:
- Dicke States and Kaiser Windows for efficient state preparation,
- Dirac Operator instead of Combinatorial Laplacian,
- Block Encoding of the Dirac Operator,
- Qubitization with Quantum Walks for efficient Eigenvalue extraction,
- Chebyshev polynomials to isolate zero Eigenvalues.
Dicke States with Kaiser windows
We need a quantum state ∣ψ⟩ that encodes information about the k-cliques in a graph. For TDA, we are interested in identifying topological features like connected components or holes (Betti numbers), which correspond to the kernel of the combinatorial Laplacian Δₖ.
We start by preparing a state ∣ψ⟩ that represents topological features. Dicke states are used because they allow an efficient preparation of uniform superposition over cliques in a graph, i.e. of all n-qubit basis states |x⟩ with a specific number of vertices as qubits in the state ∣1⟩ (Hamming weight), i.e. with a fixed Hamming weight wt(x) = k, and a garbage register.
Amplitude amplification is applied to enhance the likelihood that a measured quantum state corresponds to a subspace of valid k-cliques. It amplifies an efficient sampling from all possible cliques of a certain size in the graph with high precision. Kaiser windows further improve amplitude estimation by balancing the trade-off between spectral leakage and main lobe width in amplitude estimation.
Dirac Operator
In a classical regime, Betti numbers are computed through the spectrum of the combinatorial Laplacian. On a quantum computer, Betti numbers are calculated by analyzing the kernel of the Dirac operator which allows more efficient quantum simulation and qubitization. The middle block in the squared Dirac operator corresponds to the combinatorial Laplacian for k-simplices and is acting on the space of k-simplices (edges).
Block Encoding with Jordan-Wigner transform
In quantum topological data analysis we want to efficiently navigate simplicial complexes and analyze spectral properties to infer Betti numbers. Quantum Walks are key for simulating dynamics of quantum systems. Qubitization creates a quantum walk from block-encoded Dirac operator by applying controlled operations and phase shifts on ancillary qubits, which represent polynomial transformations of the eigenvalues.
The eigenvalues of Dirac operator are not used directly, but transformed by operations, represented as a polynomial function of those eigenvalues. Qubitization requires fewer gates and qubits compared to matrix exponentiation, as it avoids direct simulation of Hamiltonian evolution.
We need to encode the Dirac operator onto the qubits. There are different ways to encode data on a quantum computer:
- Encoding classical data: basis state encoding, angle encoding or amplitude encoding, etc.
- Bosonic encoding: Fock state, or continuous-variable encoding.
- Fermionic encoding (in quantum chemistry or condensed matter physics): block encoding with Jordan-Wigner transform or Bravyi-Kitaev
👉 We use block encoding with Jordan-Wigner transform to map fermionic, non-unitary Dirac operator onto a unitary, block-encoded matrix ready for qubits.
Qubitization with Quantum Walks
In the next step we need to simulate the time evolution of the Hamiltonian (Dirac operator). Simulation of quantum systems can be performed with:
- Linear combination of unitaries (LCU)
- Qubitization which uses quantum walks
- Trotterization (Trotter-Suzuki) which is approximation-based.
👉 We will use qubitization with quantum walks to simulate the time evolution of the block-encoded Dirac operator. Qubitization achieves significant quantum speedup compared to traditional Trotter-Suzuki methods, as it reduces number of quantum gates required for simulating time evolution of complex systems, allowing for better scaling with respect to system size and evolution time.
Together with a reflection operator on the ancilla system, the block encoded Dirac operator is used to construct a “qubitized” or “qubiterate” (quantum walk) operator. The eigenvalues of the Dirac operator are mapped into a phase estimation problem on a quantum computer with zero eigenvalues being ±1 eigenvalues in quantum walk operator.
The quantum walk operator acts on a quantum state and explores the structure of the simplicial complex, where spectral properties of the quantum walk operator, i.e. its eigenvalues and eigenvectors, are tied to eigenvalues of the Dirac operator, which allows to compute Betti numbers.
Chebychev Polynomials
In the last step, we want to estimate the eigenvalues of the Dirac operator from the quantum-walk-based simulation. There are different method that we can use in combination with qubitization:
- Quantum phase estimation
- Chebychev polynomials
- Variational Quantum Eigensolver
- Quantum Krylov Subspace methods
👉 We will use Chebychev polynomials to estimate the eigenvalues of the qubitized Dirac operator.
We want to efficiently isolate zero eigenvalues that correspond to Betti numbers. Instead of using quantum phase estimation, we employ Chebyshev polynomials which create sharp filters on the spectrum of the walk operator to distinguish zero eigenvalues from non-zero ones
This spectral projector isolates the kernel of Dirac operator. The filtering is done by applying the walk operator iteratively to ensure that eigenvalues corresponding to zero are amplified, while others are attenuated. The eigenvalue spectrum of the operator is sharpened which allows a precise estimation of Betti numbers.
Projection-based overlap estimation is then used to estimate probability that the initial quantum state ∣ψ⟩ lies within the zero-eigenvalue subspace. This overlap quantifies how much of the evolved state lies in the kernel (zero eigenvalue subspace) of the Dirac operator (its dimension), which is the subspace corresponding to the Betti numbers βₖ.
Disclaimer: The views and opinions expressed in this article are my own and do not necessarily reflect those of my employer.
