Topological data analysis on noisy quantum computers
Authors: Ismail Yunus Akhalwaya
Shashanka Ubaru
Kenneth L. Clarkson
Mark S. Squillante
Vishnu Jejjala
Yang-Hui He
Kugendran Naidoo
Vasileios Kalantzis
Lior Horesh
Venue: ICLR 2024 oral (2024)
Keywords: Topological data analysis
quantum computing
unsupervised learning
feature extraction
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain computational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the original Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, require fault-tolerance qualifications that are currently unavailable. In this study, we present NISQ-TDA, a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.

Published as a conference paper at ICLR 2024
TOPOLOGICAL DATA ANALYSIS ON NOISY QUANTUM COMPUTERS
Ismail Yunus Akhalwayal
Shashanka Ubaru
Kenneth L. Clarkson
Mark S. Squillante"
Vishnu Jejjala?
Yang-Hui He
Kugendran N
Vasileios Kalantzist
Lior Horesh
ABSTRACT
Topological data analysis (TDA) is powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbi- tant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain com- putational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the orig- inal Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, re- quire currently unavailable fault-tolerance. In this study, we present NISQ-TIe a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to nigh-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm nei- ther suffers from the data-loading problem nor does need to store the input data the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.
INTRODUCTION
With the advent of modern technology, the collection of information-rich, high-dimensional data has become prevalent. These high-dimensional datasets are typically characterized by multidimen- sional correlation structures that are difficult to uncover. Extracting and analyzing such structural information crucial machine learning as well as in accelerating scientific discovery. Topolog- ical data analysis (TDA) is powerful unsupervised machine learning technique for the extraction of valuable shape-related features of large datasets (Zomorodian & Carlsson, 2005; Ghrist, 2008; Wasserman, 2018). It represents dimensional datasets and reduce them to a small set of local and global signature values that are interpretable and laden with predictive and analytical value. TDA has been shown to be useful in various scientific applications, including machine learning and artificial intelligence (Al) for the analysis of deep neural network architectures (e.g., estimate the capacity (Guss & Salakhutdinov, 2018) and topological complexity (Naitzat et al., 2020) of neural networks); neuroscience (Giusti al., 2015), where topology is used to reveal intrinsic geometric structures in neural correlations; cosmology (Cole & Shiu, 10)8,,, where TDA is used for detecting non- non-Gaun Gaussiantstt of the cosmic microwave background (CMB); and genetics (Rabadán et al., 2020; Mandal et al., 2020b), for pre- dicting phenotypes from gene co-expression or raw genomics data. Despite such progress in some applications, the true potential of TDA has been severely limited because classical algorithms for
of the few data analysis algorithms that process high-
'These authors contributed equally to this work. Corresponding authors 'BMM Research, USA and South Africa I University of the Witwatersrand, South Africa 6 Royal Institution, UK

---

Published as a conference paper at ICLR 2024
TDA have proven to be computationally prohibitive, only mitigated to some extent by sampling or by limiting calculations to low -ww-dimensional properties.
Quantum computers represent one potential approach to address these prohibitive computational re- quirements of TDA. The power of quantum computers lies in their ability to perform computations in large computational (Hilbert) spaces, accessed via relatively small physical systems (Deutsch, 1985; Lloyd, 1996). With the recognition of this novel computational power in the 1980s (Feyn- man, 1982), there has been an arduous search for algorithms that achieve significant computational speedups over classical algorithms (Shor, 1994; Grover, 1996; Nielsen & Chuang, 2010). Such quantum algorithms offer the potential solve problems that can not be solved using conventional computers. Quantum computers outperforming current classical supercomputers has been termed quantum advantage in the literature (Bravyi et al., 2018; Arute et al., 2019; Deshpande et al., 2022; Rinott et al., 2022). However, this has not yet been achieved for any problem of practical value.
In seminal paper, Lloyd et al. (2016) proposed Quantum TDA (QTDA), an algorithm that achieves an expected exponential speedup in solving approximation of TDA. Recent works (Gyurik et al., 2020; Cade & Crichigno, 2021; Crichigno & Kohler, 2022; Schmidhuber & Lloyd, 2022) have studied the hardness of the approximation problem solved by QTDA, and discussed the conditions under which the algorithm provably enjoys speedup over classical algorithms. Furthermore, this speedup is not overshadowed by the data-loading cost (Aaronson, 2015), which plagues several other quantum algorithms (Harrow et al., 2009; Gilyén et al., 2019), especially those related to machine learning (Biamonte al., 2017; Schuld et al., 2015). However, the QTDA algorithm still requires long-lasting quantum coherence and low computational error to store and process the loaded data. Indeed, it requires fault-tolerant quantum computing (Shor, 1996; Aaronson, 2015; Preskill, 2018), an error-corrected quantum computer needing a very large overhead in resources (number of low-noise qubits and operations) (Arute et al., 2019; Zhao et al., 2020). Many components of the Lloyd et al. (2016) algorithm require fault-tolerance: Grover's 's search (Grover, 1996), Quantum Phase Estimation (Nielsen Chuang. 2010), and repeated access to the input data. However, fault- tolerance has not yet been achieved on currently available quantum devices, and is likely several years away from full realization (goo, 2023). Intriguingly, the qubit numbers and noise levels that are currently realized in hardware are not classically simulatable, which raises the question of whether some algorithm could make use of these non-fault-tolerant noisy devices (Noisy Intermediate-See Quantum (NISQ) (Preskill, 2018)) for quantum advantage?
In this paper we present a quantum algorithm for solving the same problem as QTDA with an im- proved runtime, shorter circuit depth, and without fault tolerance requirements. Our NISQ-TDA al- gorithm solves the principal problem of TDA, estimating the Betti numbers of the given data (Ghrist,, 2008). The algorithm only requires pairwise distances of the n data-points input and outputs an estimate for the (normalized) Betti numbers of the data, which are signature values that describe the shape of the data. However, the calculation of these Betti numbers by current methods requires operating on large exponential-sizer matrices (details of TDA and Betti numbers are provided in the next section). The approximation problem solved by our algorithm is believed to be intractable classically (likely belonging to class of problems called -hard (Morimae et al., 2014)) under certain settings (Gyurik et al., 2020; Cade & Crichigno, 2021; Crichigno & Kohler, 2022), and in this sense potentially enjoys super-polynomial to exponential speedup over classical algorithms for certain classes of problems (Schmidhuber & Lloyd, 2022). We present a theoretical error analysis for the proposed algorithm, establishing error guarantees for the estimated Betti numbers, and show that the algorithm requires only P(n/V6))-ephl circuit complexity. We then present preliminary empirical results from implementations on real hardware and quantum simulations that illustrate the noise resiliency of our algorithm. Our presented theoretical and numerical results demonstrate that NISQ-TDA has the potential to be the first generically useful NISQ algorithm.
2 PRELIMINARIES
We begin by introducing the key concepts of quantum computing, TDA and quantum TDA (QTDA).
Quantum computing: Quantum computing is characterized by operations on the quantum state of quantum bits qubits, representing vector in 2" dimensional complex vector (Hilbert) space. The quantum operations or measurements correspond to multiplying the quantum state vector by certain 2n x 2n matrices. Quantum circuits represent these operations in terms of set of quantum
2

---

Published as a conference paper at ICLR 2024
gates operating on the qubits. The number of these gates and the depth of the circuit define the circuit complexity of a given quantum algorithm. Quantum computers are difficult to build (preparing and maintaining the quantum states is extremely hard) and are very noisy. Therefore, the principles of quantum error correction were proposed to protect the quantum system from information loss and other damages (Gottesman, 2010). A (large-scale) quantum computer with many qubits is said to be fault-tolerant if the device is capable of such quantum error correction. However, realization of such fault-tolerant quantum systems is likely several years away. Currently available quantum computers are termed "Noisy Intermediate- Scalle Quantum" (NISQ) (Preskill, 2018), and these devices are prone to considerable error rates and are limited in size by the number of logical qubits available in the system. In order to obtain results with reasonable accuracies on NISQ device, the quantum circuit implementing a given algorithm needs to of short depth.
Topological data analysis: TDA represents one of the few data analysis methodologies that can process high-dimensional datasets and reduce them to a small set local and global signature values that are interpretable and laden with predictive and analytical value. Given a set of n data-points {z,); )--! in some space together with a distance metric D, a Vietoris-Rips (Ghrist, 2008) simplicial complex is constructed by selecting resolution/grouping scale that defines the "closeness" of the points with respect to the distance metric D, and then connecting the points that are a distance of e from each other (i.e., connecting points x; and Ty whenever Dira xry) S E, forming a so-called 1-skeleton). A k-simplex is then added for every subset of k + 1 data-points that are pair-wise connected (i.e., for every k-clique, the associated k-simplex is added).
Let Sy denote the set of k-simplices in the Vietoris-Rips complex 1' = {Sx with St E Sk written as fjk } where jı is the ith vertex of 8k. Let H/ denote an n (4 -dimensioonal Hilbert space, with basis vectors corresponding to each of the possible h-simplices (all subsets of size k + 1). Further let Ry denote the subspace of 7s spanned by the basis vectors corresponding to the simplices in Sk, and let (sx) denote the basis state corresponding to 8k E Sk. Then, the n-qubit Hilbert space C is given by C2" ~ Oi=o Ha- The boundary map (operator) on k-dimensional simplices Ōn : Hr - Hx-1 is a linear operator defined by its action on the basis states as follows:
k-1
On (kn) = -- (-1)(1s-_10)))
1=0
where (sk) is the lower simplex obtained by leaving out vertex (i.e., Sk-1 has the same vertex set as 8& except without ji), and 8k-1 is k - 1-dimensional, dimension less than &g- The factor (-1)² produces the oriented (Ghrist, 2008) sum of boundary simplices, which keeps track of neighbouring simplices so that 1g-10u (s2) 0, given that the boundary of the boundary is empty.
The boundary map Ūj. Hle + Ha-1 restricted to a given Vietoris- complex I is given by ã. = Og Pk. where P: the projector onto the space S& of simplices in Т. The full boundary operator on the fully connected complex (the set of all subsets of points) is the direct sum of the k- dimensional boundary operators, namely ő D₁ Dg. The k-homology group is the quotient space
HIg == ker (ōx) ) /img((++1), )) representing all k-holes which are not "filled-in" by le simplices and counted once when connected by simplices (e.g., the two holes at the ends of tunnel count once). Such global structures moulded by local relationships is what is meant by the "shape" of data. The kth Betti Number 3% is the dimension of this k- k-homology group, namely 8g == dim H4.
These Betti numbers therefore count the number of holes at scale as described above. By comput- ing the Betti numbers at different scales E, we can obtain the persistence barcodes/diagrams (Ghrist, 2008), i.e., a set of powerful interpretable topological features that account for different scales while being robust to small perturbations and invariant to various data manipulations. These stable per- sistence diagrams not only provide information at multiple resolutions. but they also help identify, in an unsupervised fashion, the resolutions at which interesting structures exist. The Combinatorial Laplacian, or Hodge Laplacian, of a given complex is defined as A == 0. 0, + 1 From the Hodge theorem (Friedman, 1998; Lim, 2019), we can compute the kth Betti number as
Bx = dim ker(Ax).
(2)
Therefore, computing Betti numbers for TDA can be viewed as rank estimation problem (i.e.. Be = dim Hd rank (A)). Additional TDA details can be found in Appendix A.2. The problem
3

---

Published as a conference paper at ICLR 2024
of normalized Betti number estimation (BNE) is defined as (Gyurik et al., 2020): Given set of points, its corresponding Victoris-Ripp complex I, an integer S k I n 1, and the parameters (E, (0, find the value Xx E [0, that satisfies with probability 1 17 the condition
3k
Xk
E,
[
where |Sx| is the the number of k-simplices Sk E I or dim Hy. the dimension of the Hilbert space spanned by the set of k-simplices in the complex.
Quantum TDA: Lloyd et al. (2016) proposed Quantum TDA (QTDA), an algorithm for solving an approximation of TDA in polynomial time for class of simplicial complexes. Recent works have shown, e.g.- (Gyurik et al., 2020; Schmidhuber & Lloyd, 2022), that the problem QTDA solves approximately is intractable classically for certain classes of complexes. The TDA problem of computing Betti numbers exactly has been shown to be intractable for even quantum computers as decision clique homology has been proven to be QMAI- (Crichigno & Kohler, 2022) for clique complexes; and promise weighted clique homology has been shown to be 1MAl-hard and contained in QMA (King& Kohler, 2023). The approximative version that QTDA actually solves involves a different computational class: DQC1-hard. This normalized Betti number estimation problem has been shown to be DQCl-hard for general chain complexes (Cade & Crichigno, 2021) and is conjectured to hold for clique complexes (Cade & Crichigno, 2021; King & Kohler, 2023).
QTDA involves two main steps, namely: (a) repeatedly constructing the simplices in the given simplicial complex mixed quantum state using Grover's search algorithm (Boyer et al., 1998); and (b) projecting this onto the eigenspace of Ag in order to calculate the Betti numbers of the complex, using quantum phase estimation (QPE) (Nielsen & Chuang, 2010) (details are provided in the Appendix A). The computational complexity is Onn (fxx)/K))) where n is the number of data points, 0g denotes the smallest nonzero eigenvalue of Ax, and Ç& is the fraction of all simplices of order & in the given complex, resulting in significant speedup over known classical algorithms. However, QTDA requires long-lasting quantum coherence to store the loaded data for the length of the long-depth circuits thus requiring fault-tolerant quantum computing. In particular, Grovers and QPE require precise phase information where any errors would accumulate multiplicatively.
NISQ-TDA
We now present our proposed quantum algorithm, NISQ-TDA, for estimating the (normalized) Betti numbers of datasets (simplicial complexes) defined through vertices and edges. The algorithm in- volves three key components, namely: (a) an efficient representation of the full boundary operator as a sum of Pauli operators; (b) a quantum rejection sampling technique to project onto the data-defined simplicial complex; and (c) stochastic rank estimation method to estimate the output signature Berri numbers. In order to calculate the Betti numbers, the first of two major tasks is to construct quan- tum circuit that applies the data-defined Laplacian to any input set of simplices. In our algorithm, this involves three main sub-components.
The first is a quantum representation of the complete (not data-defined) boundary map operator (say B), called the Fermionic boundary operator (Cade & Crichigno, 2021; Akhalwaya et al., 2022). It acts on all possible simplices with n points and returns their corresponding boundary simplices. The representation involves only unitary operators written as a sum of Pauli (fermionic) operators. The Hermitian boundary operator B is written as B === := - a; + Jordan-Wigner (Jordan & Wigner, 1928) Pauli embeddings corresponding to the n-spin fermionic annihilation operators. The implementation of this fermionie boundary operator B on quantum computer requires only n qubits, Onn?) gates, and an ((n)) --depth circuit, see Appendix B for details.
where the o, are the
The second sub-component which we call Projection onto simplices, consists of projecting onto the simplicial complex (I') corresponding to the given data by implementing the projector (Pp) using multi-qubit gates and auxiliary flag-registers. A series of multi-control-NOO in the complement of the g-close graph (precomputed classically), checks if the edges of the input simplices (in superposition) are not present in the data. The result is stored in a flag register which can either be measured (causing a collapse) or used reversibly allowing for uncomputation. Since there are (*) ~ On²) potential edges, this seems to require O(n?) depth. However the checks can be run in parallel and in batches using a round-robin procedure for depth of O(z).
gates, one for each edge
4

---

Published as a conference paper at ICLR 2024
The result of the checks on maximum of n/2 pairs of vertices time, needs n/2 flag qubits in n - 1 rounds, thereby covering all possible (2) pairs of vertices not e-close. The n/22 pairs are chosen such that the C-C-NOT (Toffoli) gates, controlling on pairs of vertex qubits, targeting the flag register, are executed in parallel.
If the flag registers are measured, then just n// flag qubits suffice in total and can be reused using the power of mid-circuit measure and reset. In each round, we measure the flag register and proceed only if we receive all zeros. This collapses the simplex superposition into those simplices that only have pairs which are not missing from the adjacency graph.
If the flag registers are not measured due to the need for reversibility (which is our case when performing qubitization), then the auxiliary qubits cannot be measured and reused and (nn)) inde- pendent auxiliary qubits are needed.
The 'all-orders' data-defined Laplacian can now be expressed as A = BPB.
Although this simple lincar-depth circuit implementation of Pr suggests a requirement of quantum computers with all-to-all connectivity (as used in our experiments), can indeed implement it on quantum computers with only linear qubit connectivity using a sorting network approach in ((n) depth (Beals et al., 2013; O'Gorman et al., 2019). The network uses nearest-neighhor SWAP gates and with n layers of such 'qubit swaps", all (2) pair of qubits become nearest-neighbors at some layer; see O' Gorman al. (2019) for details.
Most importantly, the ability to write the Laplacian in terms of a circuit that does not require ac- cessing stored quantum data is one of the key enabling innovations of NISQ-TDA. The input edge data is not stored on the quantum computer but enters through the presence or absence of the multi- qubit control gates of the projector. Every time the complex projection is called, the data freshly and accurately injected into the quantum computer. This suggests that NISQ-TDA is partially self- correcting, and under noise presence, the last application Pr mitigates the noise. When noise- levels only allow for one coherent application of Pr, this application meaningfully represents the data and can be used for alternate machine learning tasks.
The third sub-component, which we call Projection to simplicial order, is the construction of the projector (Px) onto the k-simplex subspace. The circuit is a sequence of control- 'add one' sub- circuits that conditions each vertex qubit of the simplex register and increments log(n)-sizee count register. The operation is equivalent to implementing efficiently implemented using diagonalization (Shende al., 2006) in the Fourier basis. Similarly to Pr. the projection can be executed by measurement collapse (by measuring the count register) or reversibly, enabling uncomputation uncomputation. The cost in depth is (n)), since each vertex qubit must take
and can be
turn to control onto count register qubit. The data-defined Laplacian corresponding to simplicial order i can thus be written as A PRAPE-
The second major part of the NISQ-TDA algorithm, which we call the Stochastic Chebyshev method, consists of using the above quantum circuit in a larger classically controlled framework, making NISQ-TDA a hybrid guantum-classical algorithm. The classical framework is a stochas- tic rank estimation using the Chebyshev polynomials (Ubaru & Saad, 2016; Ubaru et al., 2017). Once we obtain the rank of the Laplacian, we have the Betti numbers Ba dim(ker(AA) |Sx| - rankk ras) where Se C I the set of k-simplices the given complex T. Stochastic rank estimation recasts the degomddccomooiition problem into the estimation of the matrix function trace.
Assuming the smallest nonzero eigenvalue of Å Au/n is greater than or equal to 6, we have
trace(h(As)), where h(x) = 0 otherwise rank(Ax) del
1
if x > 6
Supposing A = E, A /u44)) (ugl is the eigen-decooposiitonn we have h(āa)) = E, (us) where the step function h(-) takes value of 1 above the threshold 8 > 0 and the eigenvalues of As are in the interval (0) 1]. Next, h(Ax) is approximated using a truncated Chebyshev polynomial series (Trefethen, 2019) h(AA) En (Âc, where T.(+) is the jth-degree Chebyshev polynomial of the first kind and cj are the coefficients with closed-form expressions. The trace is approximated using the stochastic trace estimation method (Hutchinson, 1990) given by trace(A) w By Eie 11 (or) Alw;), where |ot), / 1, .,..., Dl. are random vectors with zero mean and uncorrelated coordinates. It can be shown that set of random columns of the Hadamard matrices works well as
5

---

Published as a conference paper at ICLR 2024
choice for lut), both in theory and practice (see the supplementary material). Sampling a random Hadamard state vector in a quantum computer can be conducted with a short-depth circuit. Given an initial state 10), we randomly flip the qubits (by applying NOT gate determined by a random n-bit binary number generated classically). Thereafter, we apply the n-qubit Hadamard gate to produce state corresponding to random column of the 2" 2n Hadamard matrix. Therefore, the
rank of A can be approximately estimated as rank(A&) J. E Σ Cj (A (A)))
where the Cj are Chebyshev coefficients for approximating the step function. Given a circuit that block-encodes Åg. we can block-encode a j-degree Chebyshev polynomial Týj (Ax) using the idea of qubitization (Low & Chuang, 2019; Gilyén al., 2019). Details are given in Appendix B.
NISQ-TDA Algorithm: We now have all the ingredients to present our NISQ-TDA algorithm:
Algorithm NISQ-TDA Algorithm
Input: Pairwise distances of n data points and encoding of the s-close pairs; parameters c, Ó, and By ()=²)); and n, n-bit random binary numbers.
Output: Betti number estimates XR. k = O..... n2
for / = I...., Bly = (²))) do
for 0, ...., = (log(1/E)) do
1. Prepare a random Hadamard state vector (oa) from (0) using the I-th random number.
2. Use the circuits for Pk. Pr, and = B/ / to compute
(db)) = 109) Á (1)) + [ where q = #auxiliary qubits needed for projections.
3. Use qubitization to form: 15
|0++1 Ty(āx) (ur) + [1) from lot).
4. Compute the Chebyshev moments of (vzl Tj (s)) (er) from (5) (
end for For j = 0, estimate |St| using the average norm of the Pr Iuz)- end for
1 Ei= En= s Repeat for k- = 0, ....., 1.
Estimate X
Our NISQ-TDA algorithm returns the estimates Xx for the normalized Betti numbers S for each order k = 0, O...., n2 1, where J.S₁] is the number of k-simplices in the given I'. We discuss potential scientific machine learning and Al applications
Analyses:
NISQ-TDD in the Appendix. The remainder of this section focuses on theoretical analyses of our NISQ-TDA algorithm, with the formal details and proofs provided in Appendix C. begin with the following main result.
Theorem 1. Assume we are given the pairwise distances of any data points and the encoding of the corresponding s-close pairs, together with an integer 0 S k S n - 1 and the parameters (e, v) E (0, 1). Further assume the eigenvalues of the sculed Laplacian Âg are in the interval {0} U [ö, 1], and choose ny and m such that
n. ny= 0 (1og(1/m)) é
(
log(1/e) m
and
V8
Then, the Betli number estimation E [0, 10 by NISQ-TDA, with probability at least 1 - 1), satisfies
3%
X*
S
Our analysis accounts for errors due to (a) polynomial approximation of the step function; (b) stochastic trace estimator; and (c) also shot noise, i.e., errors in Chebyshev moments estimation and their propagation in classical computation; for details, see Appendix C.
We next discuss the circuit and computational complexities of our proposed algorithm and show that is NISQ implementable under certain conditions, such the requirement for simplices-dense com- plexes, which commonly occur for large resolution scale. The main quantum component of the algo-
rithm comprises the computation of 0.5) (uxl (Ā)))) (ux), for j 0,..., , m (llog(1/e)///

---

Published as a conference paper at ICLR 2024
with n, 3) random Hadamard vectors. The random Hadamard state preparation requires single-qubit Hadamard gates in parallel and O(1) time. For given lt, constructing Åg involves implementing the boundary operator B and the projectors Pr and Pa. The operator B, involving the sum of n Pauli operators, can be implemented using circuit with O(n) gates. Ps. requires O(n n) gates, while Pr requires O(n²) gates, but with both fitting within (nz) depth due to parallelization. Our implementation of Pr requires n2/2 auxiliary qubits for measured projection but O(n²) auxiliary qubits when uncomputation is needed.
The total time complexity of our algorithm
( max o
n (og(1/)) v0 'c mm))
mm
Supposing 5F is the spectral gap of A& and Á As, then 8 4. The best-known classical algorithm for Betti number estimation of order k has time complexity of O(poly(n*)) (Gyurik et al., 2020) or O(n 1/61/8800 (/1))((/))) (Apers et al., 2022). Thus, the QTDA algorithms can achieve super- polynomial to exponential speedups over the best-known classical algorithms whenever we have:
Simplices/liqque dense complexes - the given complex P is simplices/clique dense, i.e.. S is large |S&| ~ (p)o)(nn)):
O poll((n) spectral gap the spectral gap between zero and nonzero eigenvalues of AІ is not exponentially small, i.e., 8 of À is ((1/poly(n)) (Apers et al., 2022); and
Large Betti number the Betti number 3e (and the ratio Be/|Sk) needs to be large so that large e suffices to estimate a reasonable precision.
A few examples for simplicial complexes that satisfy these conditions are discussed in the Appendix. Further examples and discussions on the potential speedups for quantum TDA algorithms are pre- sented in (Schmidhuber & Lloyd, 2022).
We wish to remark that known examples of simplicial complexes with exponentially many holes (Betti number) are limited. An example family of graphs with exponentially many high- -igh-dimensional holes are presented in (Fendley & Schoutens, 2005). More importantly, our algorithm still likely achieves exponential advantage over known classical approaches in efficiently answering the ques- tion: does the given simplicial complex have exponentially many holes or not? In that regard, our algorithm is indeed applicable to honcraaddr high-dimensional classical data.
From different point of view, the Chebyshev moments capture the spectral information of A and have even more information than the Betti numbers. This therefore opens the door for these (Pr-corrected) noisy moments to be used directly as input features in downstream contexts such as machine learning classification, further relieving the depth and noise requirements of NISQ-TDA.
4 EXPERIMENTAL RESULTS
With the theory promising short depths, it remains to demonstrate that NISQ-TDA is sufficiently noise-robust for quantum advantage to be achieved for the actual depths in realizable hardware and under realistic noise levels. Currently optimized classical TDA algorithms cannot compute all Betti numbers for 64 generic vertices (we have empirically verified with a popular public package called GUDHI (Maria et al., 2014)). Hence, quantum advantage could possibly be achieved when running NISQ-TDA on 64 vertices. Such large NISQ-TDA circuits are also beyond what is simulatable classically (Pednault et al., 2017; 2019).
We first present the actual depths needed in the form of depth versus number of vertices plot, which also empirically confirms that circuit depth grows linearly with the number of vertices. Figure shows depths for both actual quantum hardware circuits and generic all-to-all quantum simulator circuits. For the quantum hardware, employed the public-cloud accessible 'H1' 12-qubit trapped- ion quantum computer from Quantinuum (powered by Honeywell) (Honeywell, 2022). We selected the most conservative number of edges cover the worst-case depth scenario. The magenta solid points of sub-figur A correspond to Laplacian circuit depths obtained from Quantinuum's 's own native compiler, and the blue circled points correspond to those obtained from quantum simulator.
7

---

Published as a conference paper at ICLR 2024
A. Depth vy Vertices flog scale)
Dogree
Degise
2040
4390
2043
Daysh
122
GASH allto-all
250
lon-trap
6+
verlees
C.
D).
Edge (2 vertices)
Square (4 vertices)
Cube vertices)
Results from real hardware Laplacian applications (using measure and reset projec- tions): A. Circuit depth versus the number of vertices for degree
Figure 1:
1 and 3; (B., C. and D.) Histograms of the probability measurements as obtained from the hardware (right, magenta bars) and from simulator (left, blue bars) for three different datasets namely, edge (2 vertices), square (4 vertices), and a cube (8 vertices). & defines the null state, and "X" denotes the probability mass with incorrect flag readings.
We observe that the circuit depth for the Laplacian scales linearly with respect to the number of data points. As discussed earlier, our algorithm can be implemented on quantum computers with linear qubit connectivity well, using the sorting network approach (Beals et al., 2013).
The remaining three sub-figures ments for different numbers of vertices (2, 4, 8) for both hardware runs (right, magenta bars) and simulation runs (left, blue bars). These measurements are the raw outputs of the quantum circuit before being converted into expectations (where flag values play role). The respective complexes chosen correspond to easily understandable shapes (edge, square, cube) represented by the (green) edges. The input simplex set corresponds to a uniform superposition over all simplices (including not shown triangles, tetrahedrons, and all higher-order polytopes). Due to projection onto the spec- ified complexes and interference (correctly eliminating boundaries. sending mass to the null state ②), not all simplices will appear/remain after the application of the Laplacian, demonstrating that the hardware truly performing a coherent quantum calculation. These sub-figures clearly show that there is agreement between hardware and noise-free simulations on which simplices receive the top probability measurements. Three types of errors are, however, visible by the hardware: reduced probability mass for correct simplices, some small probability mass on incorrect simplices (also not shown the non-top measurements), and correct simplex mass but incorrect flag readings (marked with red 'X' in sub-figures B and D). Even with these errors. Figure I unequivocally demonstrates that real-world noise-levels there sufficient coherence to reproduce the correct interference at the depths of these circuits.
C, D) present the histograms of the top probability measure-
The next task would be demonstrate that these errors, which inevitably enter, do not dramatically disturb the downstream Betti number calculation. For this we chose complexes with large eigenvalue gaps, and sufficiently many random vectors and shots. The Chebyshev parameters we selected are such that, in the noise-free scenario, the algorithm would calculate the Betti number almost perfectly (i.e., with a mean error close to zero). Thus, any Betti-number emrors involving the noisy simulations approximations. In this setup. the error that can naturally be considered tolerable 0.5, since any emror less than 0.5 rounds exactly the correct Betti number. In Figure 2, we present results from
due mainly to the quantum noise and only minimally downstream classical
8

---

Published as a conference paper at ICLR 2024
Mamu exer suriace
vu varisnes
3
2
1.95
Moxn 4tH
1,0
Morn RNT.
1.85
0.5
(8474307)
[16,1778]
(0.0005.0000)
(0.001.0.1))
(0.0002,0000)
depti)
(2.60)
Noise Intel (1Q:2))
0.000
20
Numtoer of vectums
40
80
801
100
Figure 2: Results from noisy simulations: in (I-qubit, 2-qubits) gates and (number of vertices n, circuit depth). B. Mean and the variance of the Betti number estimated as a function of the number of random vectors ny with n = 8 vertices, degree m and the noise-level: (0.001, 0.01).
A. Mean error surface as a function of the noise levels
extensive noisy quantum simulations of the non-qubitized version of the algorithm. The right plot shows the mean and the variance (as error bars) of the Betti number estimated number of random vectors Ny. We note that the mean converges to ~ 1.84 (the true Betti number is 30 = 2) and, most importantly, the variance reduces as we increase n,,- This variance-reduction mitigates errors due to shot noise and randomness in the trace estimation, illustrating the precision- tesuu-number-offee
function of the
benefit of NISQ In the left figure, present the mean error surface plot for Betti number estimation, as function of noise levels (chosen triples of measurement, one and two-qubit gate errors) and number of vertices (with concomitant circuit depth). The first number of the listed noise-level pair corresponds to the one-qubit error probability. The measurement and the two-qubit error probabilities are both set the second value. the surface plot, the solid region (for
2 to = 8) corresponds to actual noisy simulations and the translucent region (from 16 to 64 vertices) corresponds to extrapolation of the surface for larger n, which we cannot simulate classically (even n = 16 was not simulatable using large classical machine with 2 GPUs). The surface plot extrapolations provide the minimum noise-level requirements for NISQ-TDA to successfully run on future larger NISQ devices. See Appendix D) for additional results, including preliminary results on cosmic microwave background (CMB) data.
5 CONCLUSIONS
The true potential of TDA for machine learning has been severely limited because of the compu- tationally prohibitive requirements classical algorithms. To address this critical issue and revive the potential of TDA viable machine learning approach, we presented rithm for Betti number estimation with comprehensive error and complexity analyses. This is one of the first quantum machine learning algorithms with short depth and potential significant speedup under certain assumptions. Our algorithm neither suffers from the data-loading problem nor does likely require fault-tolerant coherence for even mid-size datasets. The algorithm fits the hybrid quantum-classical scheme but within a recently developed randomized-appron approxxmmaion framework. The implementation and successful execution of the entire algorithm on real quantum hardware and noisy simulations was demonstrated, illustrating noise-resiliency at realistic noise-levels. These ad- vantages imply that this algorithm may be one the few noise-robust quantum algorithms capable of performing an important and useful AI task on near-term (non-fault tolerant) quantum devices, beyond the reach classical computation. Possible future research directions include: improve- ments to the algorithm in order to efficiently deploy it sparsely connected quantum devices; achieving substantial asymptotic speedups under more general settings; and identifying interesting domain problems for which NISQ-TDA can be employed for practical purposes.
quantum algo-

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research was supported in part by the Air Force Research Laboratory (AFRL) grant number FA8750-C-18-0098 and in part by IBM Research, South Africa under the Equity Equivalent In- vestment Programme (EEIP) of the government of South Africa. VJ is supported South African Research Chairs Initiative of the National Research Foundation, grant number 78554. Firstly, we wish to thank Brian Neyenhuis, Jennifer Strabley, Chad Edwards, and Tony Uttley from the Quantinuum quantum team for generously providing us credits to access their quantum comput- ers and assisting with the experimentation. Secondly, we would like to thank Adam Connolly and Julien Sorci for pointing out flaw in the algorithm of carlier version of the paper. Next, would like to acknowledge Tal Kachman for the suggestion to use the simplices with the count register. The authors would also like to thank Scott Aaronson, Paul Alsing, Ryan Babbush, Sergey Bravyi, Chris Cade, Marcos Crichigno, Aram Harrow, Gil Kalai, and Seth Lloyd for valuable discussions.
part by the
-inermeeednneemmett to entangle
REFERENCES
Suppressing quantum emrors by scaling surface code logical qubit. Nature, 614(7949):666-681, 2023.
Scott Aaronson. Read the fine print. Nature Physics, 11(4):291-293, 2015.
Kartick Adhikari, Robert Adler, Omer Bobrowski, and Ron Rosenthal. On the spectrum of dense random geometric graphs arXiv preprint arXiv:2004.04995 2020.
Robert Adler, Omer Bobrowski, and Shmuel Weinberger. Crackle: The homology of noise. Dis- crete & Computational Geometry, 52(4):680-704, 2014.
N. Aghanim al. Planck 2018 results. VI. Cosmological parameters. Astron. Astrophys., 641:A6, 2020. doi: 10.1051/0004--336/2200 833910. [Erratum: Astron.Astrophys. 652, C4 (2021)).
Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru. Representation of the fermionic boundary operator. Physical Review A, 106(2):022407, 2022.
Andris Ambainis and Joseph Emerson. Quantum t-designs: t-wise independence in the quantum world. In Secony Annual IEEE Conference on Computational Complexity (CCC'07), pp- 129-140. IEEE, 2007.
Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating betti numbers. arXiv preprint arXiv:2211.0960 2022.
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using programmable superconducting processor. Nature. 574(7779):505-510 2019.
Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit sym- metric positive semi-definite matrix. Journal of the ACM (JACM), 58(2):1-34, 2011.
Frank Bauer, Jürgen Jost, and Shiping Liu. Ollivier-Ricci curvature and the spectrum of the normal- ized graph Laplace operator. arXiv preprint arXiv: 105.3803, 2011.
Robert Beals, Stephen Brierley, Oliver Gray, Aram W Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. Efficient distributed quantum computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2153):20 20686, 2013.
Orr Beit-Aharon and Roy Meshulam. Spectral expansion of random sum complexes. Journal of Topology and Analysis, 12(04):989-1002. 2020.
Matteo Biagetti, Alex Cole, and Gary Shiu. The Persistence of Large Scale Structures I: Primordial non-Gaussianity. JCAP, 04:061, 2021. doi: 10. 14.0008//477-7331102200/4/611
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, ): 2017.
10

---

Published as a conference paper at ICLR 2024
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493-55) 1998.
Zvika Brakerski and Omri Shmucli. (pseudo) random quantum states with binary phase. In Theory of Cryptography Conference, pp. 229-250. Springer, 2019.
Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 36) -110, 2018.
Chris Cade and Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. arXiv preprint arXiv:2107.00011, 2021.
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fu- jii, Jarrod McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, al. Variational quantum algorithms. Nature Reviews Physics, ((9):6256444 2021.
Nadiía Chepurko, Kenneth L Clarkson, Lior Horesh, and David P Woodruff. Quantum-inspired algorithms from randomized numerical linear algebra. arXiv preprint arXiv:2011.04122 2020.
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang- Sampling- -aased sublinear low-rank matrix arithmetic framework for dequantizing quantum ma- chine learning. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Com- puting, pp. 387-400, 2020.
Alex Cole and Gary Shiu. Persistent Homology and Non-Gaussianity. JCAP, 03:025, 2018a. doi: 10.1088/1473 77518/44477775111100000000
Alex Cole and Gary Shiu. Persistent homology and non-Gaussianity. Journal of Cosmology and Astroparticle Physics, 2018(03):025, 2018b.
Marcos Crichigno and Tamara Kohler.
Clique homology is qmal-hard. arXiv preprint
arXIv:22299.11993 2022.
Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi. Jens Eisert, et al. Quantum computational ad- vantage via sigh-dimensional gaussian boson sampling. Science advances, 8( 8())cabb77994 2022.
David Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818) 97-117, 1985.
David DiVincenzo. The physical implementation of quantum computation. Fortschritte der Physik: Progress of Physics, 48(9-11):711-78,, 2000.
Job Feldbrugge, Matti van Engelen, Rien van de Weygaert, Pratyush Pranav, and Gert Vegter. Stochastic Homology of Gaussian vs. non-Gaussian Random Fields: Graphs towards Betti Num- bers and Persistence Diagrams. JCAP, 09:052, 2019a. doi: 10. 47.1888//455-7711/20199999
Job Feldbrugge. Matti Van Engelen, Rien de Weygaert, Pratyush Pranav, and Gert Vegter. Stochastic homology of Gaussian vs. non Gaussinn random fields: graphs towards betti num- bers and persistence diagrams. Journal of Cosmology and Astroparticle Physics, 2019(09):052, 2019b.
Paul Fendley and Kareljan Schoutens. Exact results for strongly correlated fermions in 2+ dimen- sions. Physical review letters, 95(4):046403, 2005.
Richard P Feynman. Simulating physics with computers. International Journal of Theoretical
Physics, 21(6/7), 1982.
Paraskevi Fika and Christos Koukouvinos. Stochastic estimates for the trace functions matrices via Hadamard matrices. Communications in 2017.
and Computation, 46(5):3491-
Joel Friedman. Computing Betti numbers via combinatorial Laplacians. Algorithmica, 21(4):331- 346, 1998.
11

---

Published as a conference paper at ICLR 2024
Robert Ghrist. Barcodes: the persistent topology of data. Bulletin of the American Mathematical Society, 45(1):61-7,, 2008.
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transforma- tion and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193-204, 2019.
Chad Giusti, Eva Pastalkova, Carina Curto, and Vladimir Itskov. Clique topology reveals intrinsic geometric structure neural correlations. Proceedings of the National Academy of Sciences, 112 (44):13455-134G) 2015.
Timothy E Goldberg. Combinatorial Laplacians of simplicial complexes. Senior Thesis, Bard Col- lege, 2002.
Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum com- putation. In Quantum information science and its contributions to mathematics, Proceedings of Symposia in Applied Mathematics, volume 68, pp. 13-58, 2010.
Lov К Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.
Anna Gundert and Uli Wagner. On eigenvalues of random complexes. Israel Journal of Mathemat- ics, 216(():545-58) 2016.
Sam Gunn and Niels Komerup. Review of quantum algorithm for Betti numbers. arXiv preprint arXiv: 07673, 2019.
William H Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebraic topology. arXiv preprint arXiv:1802.04444 04400, 2018.
Aldo Guzman-Sane -aenn,, Nina Haiminen, Basum Saugata, and Laxmi Parida. Signal enrichment with strain-level resolution in metagenomes using topological data analysis. BMC Genomics, 20:25- 34, 2019.
Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage for topological data analysis. arXiv preprint arXiv:2005.02607, 2020.
Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009.
Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with guantum-enhancee feature spaces. Nature, 567(7747):209-211 2019.
Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by quantum communication channel. Problemy Peredachi Informatsii, 9(3)33111, 1973.
Honeywell. Quantinuum HI series trapped-ion quantum processor powered by honeywell. 2022.
URL https:://// / wwww.wwww quant innum. com/ http//roductssh//l
Danijela Horak and Jürgen Jost. Spectra of combinatorial Laplace operators on simplicial com-
plexes. Advances in Mathematics, 244:303-336, 2013.
Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hart- mut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. Quantum advantage in learning from experiments. Science, 376(6598): 182-1186, 2022.
MF Hutchinson. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications Statisiies-Smmuaaiion and Computation, 19(2):333-450, 1990.
JJordan and Wigner. Über das paulische äquivalenzverbot. Zeitschrift Physik, 47(9)6331-66 651, 1928.
Matthew Kahle. Random simplicial complexes. arXiv preprint arXiv: 107. 2016.
12

---

Published as a conference paper at ICLR 2024
Robbie King and Tamara Kohler. Promise clique homology weighted graphs is QMAI-har and contained in QMA. arXiv preprint arXiv:2311.17234 2023.
Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81725):6672, 1998.
Antti Knowles and Ron Rosenthal. Eigenvalue confinement and spectral gap for random simplicial complexes. Random Structures & Algorithms, 5163):00-537,, 2017.
Alan Lew. Spectral gaps, missing faces and minimal degrees. Journal of Combinatorial Theory, Series A, 169: 105127, 2020a.
Alan Lew. The spectral gaps of generalized flag complexes and a geometric Hall-type theorem. International Mathematics Research Notices,
2020b.
Lek-Heng Lim. Hodge Laplacians on graphs. arXiv: 1507.05379 [cs, math), August 2019. URL
http:/ http//axxvvv.o http//aawi.....gaaa//o/o hwtprg//bb/1550/ wwwaa////1...5111111 05379.. arXiv: 1507.05379.
Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv preprint arXiv:2201.08309, 2022.
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed- up in supervised machine learning. Nature Physics, 170) 2021.
Seth Lloyd. Universal quantum simulators. Science, pp. 1073-1078, 1996.
Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geo- metric analysis of data. Nature communications, 7:10138, 2016.
Guang Hao Low and Isaac L Chuang. Optimal Hamiltonian simulation by quantum signal process- ing. Physical review letters, 118(1)011001,, 2017.
Guang Hao Low and Isaac Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019.
Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al. Quantum computational advantage with programmable photonic processor. Nature, 606(7912): 75 15,-812001 2022.
Sayan Mandal, Aldo Guzman-Saena Niin Haiminen, Saugata Basu, and Laxmi Parida. A Topolog- ical Data Analysis Approach on Predicting Phenotypes from Gene Expression Data. In Algorithms for Computational Biology, pp. 178-187. Springer, 2020a.
Sayan Mandal, Aldo Guzmán-Sáan Sáenz, Niina Haiminen, Saugata Basu, and Laxmi Parida. topolog- ical data analysis approach on predicting phenotypes from gene expression data. Algorithms for Computational Biology, 22099:18. 2020b.
Clément Maria, Jean- Boissonnat, Marc Glisse, and Mariette Yvinec. The gudhi library: Sim- plicial complexes and persistent homology. In International congress mathematical software, pp. 167-174. Springer, 2014.
Vasileios Maroulas, Farzana Nasrin, and Christopher Oballe. A bayesian framework for persistent homology. SIAM Journal on Mathematics of Data Science, 2(1):48 74, 2020.
Tomoyuki Morimae, Keisuke Fujii, and Joseph Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical review letters, 112113)330000, 2014.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems, 28, 2015.
Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. J. Mach. Learn. Res., 21(184):1-44 2020.
13

---

Published as a conference paper at ICLR 2024
Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cam- bridge University Press, 2010.
Bryan O' O'Gorman, William Huggins, Eleanor G Rieffel, and K Birgitta Whaley. Generalized swap networks for near-term quantum computing. arXiv preprint arXiv:1905.055 1905.090900111 18, 2019.
Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland, and Robert Wisnieff. Pareto-efficient quantum circuit simulation using tensor contraction deferral. arXiv preprint arXiv:1710.0586.. 2017.
Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. Leveraging secondary storage to simulate deep 54-qubit sycamore circuits. arXiv preprint arXiv:1910.09534 2019.
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy L O'brien. A variational eigenvalue solver on photonic quan- tum processor. Nature communications, 5(1):1-7, 2014.
John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018.
Raál Rabadán, Yamina Mohamedi, Udi Rubin, Tim Chu, Adam N Alghalith, Oliver Elliott, Luis
Arnés, Santiago Cal, Álvaro Obaya, Arnold J Levine, et al. Identification relevant genetic alterations in cancer using topological data analysis. Nature communications, 11(1):1-10, 2020.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113(13):130503, 2014.
Christian Reiher. The clique density theorem. Annals of Mathematics, pp. 683-707, 2016.
Yosef Rinott, Tomer Shoham, and Gil Kalai. Statistical aspects of the quantum supremacy demon- stration. Statistical Science, 37(3):322-377, 2022.
Alexander Schmidhuber and Seth Lloyd. Complexity-theorete limitations on quantum algorithms for topological data analysis. arXiv preprint arXiv:2209.14288, 2022.
Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Physical review letters, 122(4):040504, 2019.
Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172-185, 2015.
Vivek V Shende, Stephen S Bullock, and Igor L Markov. Synthesis quantum-logie circuits. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, (000)-1000-11100 2006.
Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceed- ings 35th annual symposium on foundations of computer science, pp. 124-134. leee, 1994.
Peter W Shor. Fault-tolerant quantum computation. In Proceedings of 37th Conference on Founda- tions of Computer Science, pp. 56-65. IEEE, 1996.
Ewin Tang. Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Physical Review Letters, 127(6)000000,, 2021.
Lloyd N Trefethen. Approximation Theory and Approximation Practice, Extended Edition. SIAM, 2019.
Shashanka Ubaru and Yousef Saad. Fast methods for estimating the numerical rank of large matrices. In Proceedings of The 33rd International Conference Machine Learning, pp. 468 4477, 2016.
Shashanka Ubaru, Yousef Saad, and Abd-Krim Seghouane. Fast estimation of approximate matrix ranks using spectral densities. Neural computation, 29(5):111711351, 2017.
14

---

Published as a conference paper at ICLR 2024
Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson, and Lior Horesh. Quantum topologiaal data analysis with linear depth and exponential speedup. arXiv preprint 11X1:22008.0281,,, 2021.
Larry Wasserman. Topological data analysis. Annual Review of Statistics and Its Application. 5: 501-532, 2018.
John Watrous. Quantum computational complexity. In Computational Complexity: Theory, Tech- niques, and Applications, pp. 2361-2387. Springer New York, 2012.
Taiki Yamada. Spectrum of the Laplacian on simplicial complexes by the Ricci curvature. arXiv preprint 1r0iv: 07404, 2019.
Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter J. Love. Measurement reduction in variational quantum algorithms. Phys. Rev. A, 101:062322, Jun 2020. doi: hww.:/PhyyReAA.11.066333333 URL https://link. aps. orgg/oi/10.. 1103/PhysRevA, 1et...11...222......... 062322.
Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Hu, et Quantum computational advantage using photons. Science,
37066523):4400114 2020.
Leo Zhou, Sheng-Tao Wang. Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2):21067, 2020.
Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249-274 2005.
15

---

Published as a conference paper at ICLR 2024
Topological data analysis on noisy quantum computers Supplemental material
Here in the appendix, we present numerous details related to NISQ-TDA, including background information, fleshed out details related the novel ideas in the proposed algorithm, theoretical analyses and proofs, and additional numerical simulation results.
A DETAILS ON QUANTUM ALGORITHMS, TDA, AND QTDA
We begin with list of desiderata of quantum algorithm, and technical background details related to TDA and QTDA, including several applications and use cases.
A.1 DESIDERATA OF A QUANTUM ALGORITHM
An end-to-end algorithm that successfully achieves such quantum advantage on near-term (or even currently available) devices and has practical, real-world and commercial value must arguably sat- isfy a set of desiderata. Similar to the famous seven DiVincenzo criteria (DiVincenzo, 2000) for quantum hardware, we propose a seven-criteria counterpart for quantum software that such quan- tum algorithm needs to satisfy, as depicted in Figure 3. Although quantum computers can operate on large (exponential) computational spaces, well-known quantum information bottleneck is the so-called data-loading problem (Aaronson, 2015). in that if the process of loading the data requires exponential time, then the subsequent quantum computational benefits are over-shadowed by this loading time, and do not convey any asymptotic advantage. Indeed, information theory precludes the possibility of lossless exponential compression for generic unstructured data. Therefore, the data size must be small compared to the computational space, and hence, the first criterion is that the algo- rithm should be effective on small arbitrary classical inpul data. Many quantum machine learning (QML) algorithms (Biamonte al., 2017; Schuld et al., 2015; Schuld & Killoran, 2019) suffer from this inherent data-loading issue. The term "arbitrary" conveys the desirable property of the general applicability of the algorithm to handcrafdd classical input data and excludes the data access through an oracle assumptions. A few recent works (Havlížek et al., 2019; Liu et al., 2021; Huang al., 2022) have demonstrated quantum speedups for different machine learning tasks, but they restricted to specially tailored classical data, or data from well-defined quantum experiments.
The second requirement of the algorithm is that it should achieve significant asymptotic (ideally exponential) speedup (Knill & Laflamme, 1998; Watrous, 2012) on a provably' hard problem. Re- cently, many hybrid classical-quantum algorithms have been proposed, including variational quan- tum eogen-solvers (VQE) (Peruzzo et al., 2014) and the quantum approximate optimization algo- rithm (QAOA) (Zhou et al., 2020), that heuristically exploit the exponential computation space. However, these algorithms do not achieve provable speedup (Cerezo et al., 2021). Moreover, recent developments of "dequantized" algorithms (Chia et al., 2020; Chepurko et al., 2020; Tang, 2021) have reduced the potential speedups of many of the linear-algebraic QML proposals (Reben- trost et al., 2014; Biamonte et al., 2017; Schuld et al., 2015; Schuld & Killoran, 2019) to be between nil and most modest polynomial.
There are, of course, many quantum algorithms that provably achieve polynomial- catoommmlllt--xxoeeettaa speedups over the best-known classical methods (Shor, 1994; Grover, 1996; Nielsen & Chuang, 2010; Gilyén et al., 2019). However, the majority of these algorithms require fault-tolerant quan- tum computers (Shor, 1996; Aaronson, 2015; Preskill, 2018), which are error-corrected quantum systems needing a considerably large overhead in resources (number of low-noise qubits and oper- ations) (Arute al., 2019; Zhao et al., 2020). Fault tolerance has not yet been achieved at scale on currently available quantum devices, and it is likely several years away from full realization. Intrigu- ingly, the qubit numbers, coherence times and noise levels that are currently realized in hardware are not classically simulatable (Pednault et al., 2017: 2019), which raises the question of whether some algorithm could make use of these non-fault-tolerant noisy devices (Noisy Intermediate- Quantum (NISQ) (Preskill, 2018) 8)) for quantum advantage. Hence, the third and fourth requirements of the ideal algorithm are: it should compile to a short-depth circuit, allowing execution within
By "provably" we mean the problem is provably hard as computational class that is widely accepted be classically hard (Watrous, 2012).
16

---

Published as a conference paper at ICLR 2024
Desiderata of quantum algorithm
Arbitrary classical input
Quantum computation
2. Provable speed-up
Information theory
3. Shallow depth circuit
OSIN
n-ai date 100
m-bi auguo 11001
4. Noise resilient
Par bakkig
Small-size output
6. Correctness guarantees
7. Usefulness
Figure 3: The armed quantum computing advantage race: a set of seven criteria that an aspired quantum algorithm should satisfy (left), and the end-to-end quantum computational model (right), where the funnels symbolize the narrow input and output bottlenecks and the boxes represent the other desired properties.
the achievable coherence times, and it should be noise resilient, thereby tolerating the inevitably introduced noise with each operation.
The fifth requirement demands that the output should be small in size. This represents another infor- mation theory bottleneck of quantum computing, where Holevo's theorem (Holevo, 1973) suggests we can only read up to n classical bits from an n-qubit device, even though the output quantum state is exponential in size. Many QML and other algorithms suffer also from this issue (Aaronson, 2015). Another desirable property of the output forms our sixth desideratum, namely that the output of the algorithm should have correctness guarantees. This could be achieved by algorithms with a certain probability of success followed by a procedure to classically verify the correctness of the output, or by algorithms that converge the correct solution with statistical error guarantees.
The final requirement of the algorithm is that it should solve a useful problem of real-world appli- cations. The algorithm should be end-to-end and solve problem with practical use-cases. Recent quantum advantage results (Arute et al., 2019; Zhong et al., 2020; Madsen et al., 2022) fall short with respect to this crucial requirement.
Next, we discuss how our algorithm fares against the set of seven criteria introduced in this paper that should be satisfied by an aspired quantum algorithm.
Criterion is satisfied with respect to arbitrary small classical input in that the inputs to our al- gorithm and the quantum computer are just edges between the data-points, with up to n/2 edges considered in parallel, and the input can be any dataset complex defined by its vertices and edges. Moreover, the data not stored on the quantum computer explicitly, and is input each time the pro- jector Pr is applied.
Criterion 2, that of NISQ-TDA achieving provable asymptotic speedups is likely satisfied for certain instances and classes of complexes (for which the problem is DQC1-hard) previously discussed; also refer to the discussions in (Crichigno & Kohler, 2022: Schmidhuber & Lloyd, 2022).² 2 Since the NISQ-TDA algorithm only requires the complex be defined by its vertices and edges, one may
We note that recent results (Crichigno & Kohler, 2022; Schmidhuber & Lloyd, 2022) have shown the problem of estimating exact Betti numbers of clique complexes to be hard (QMA-1 and NP hard) even for unlikely to achieve quantum advantage for estimation of exact
quantum computers, and thus NISQ-TDA is
Betti numbers of clique complexes.
17

---

Published as a conference paper at ICLR 2024
A.
O-stmplee
Seingles
(slac)
B.
Hg
Connecting points with destane
Simplicid complecstt
Homologg
C3
C2
Ca
Network
Arbitrary complex
Boundary maps k-chains boundaries
Figure 4: A: k-simplices or k-chains (fully connected sets of k+1 data points) shown for k 0, 0, 3. B: Point cloud of raw data (left); Points be connected using any arbitrary distance metric e (middle), i.e., edges are inserted between points that are within & of each other (alternatively, the data could already come with edge information): higher-order k-simplices k-clique (right). C. Input data represented as a graph or network, or is given as (D) an arbitrary complex. E: Persistent homology, where the top region shows the edge connections and simplices different scales, and the bars represent the formation and cessation of connected components (Hn) and 2D holes (H1); The number of bars given scale ε equals the Betti numbers So and $1, respectively. F. Chain complex and homology: Sequence of chain groups connected by boundary operators that map k-chains to their boundaries.
created for every
consider estimation of Betti numbers other classes complexes (Schmidhuber Lloyd, 2022), such abstract simplicial complexes, Erdos-Reny: Renyi complexes and other possible chain complexes. For example, the cube (n = 8 instance) considered in our experiments is not a Vietoris-Rips com- plex (in that case, the cube would have been filled in), but offers one with example of complex with a 3D hole with just 8 vertices. Our algorithm should achieve superpolynomial to exponential speedups for complexes with very large number of simplices ([Sal ~ (p)oy(nn)) very large Betti number (3g [S&)) and large spectral gap (1 (1/V8- O(vr)).
Criterion 3 is satisfied since the algorithm compiles to a short depth quantum circuit that is im- plementable on present-day and near-term quantum devices, where the circuit depth will be data dependent (depending the number of edges, and also the spectral gap for the polynomial degree). Preliminary experiments show linear scaling of the circuit depths for a fixed polynomial degree.
Criterion 4 seems to be satisfied as suggested by the preliminary simulation and hardware imple- mentation results, which show that NISQ-TDA is noise-resilient. The noise-resiliency stems from two factors: (a) repeated data loading through the projectors Pr; and (b) the stochastic trace estima- Each application of Pr inputs the clean data information afresh, correcting the errors introduced due to noise to the previous step. The stochastic trace estimator estimates the trace by averaging over many random samples, hence averaging out the noise effects.
Criterion 5 of small output is naturally satisfied in that the algorithm output is an estimate of the normalized Betti number, and the outputs measured from the quantum computer are the moments. Criterion 6 is satisfied, as presented error guarantees for NISQ-TDA and discussed the condi- tions under which the algorithm will likely achieve speed up over classical algorithms.
Criterion 7 is likely satisfied in that it can certainly solve interesting useful problems, such esti- mating whether or not a given complex has exponentially many holes and extracting spectral infor- mation of high-order Laplacians, with substantial speedups known classical approaches, even if
18

---

Published as a conference paper at ICLR 2024
is unclear whether NISQ-TDA will achieve substantial speedups arbitrary data for Betti number estimation; some specific useful applications are discussed below.
A.2 TOPOLOGICAL DATA ANALYSIS
Figure illustrates the key concepts of TDA. A k-simplex or a k-clique or k-chain is a collection of k + 1 fully connected points (see Figure 4(A)), and simplicial complex (clique chain complex) is collection of such (nested) simplices (Figure 4(B)). Formally, an abstract simplicial complex T (Figure 4(D)) is set of simplices satisfying: (a) if simplex is in 7, then all its faces are in r, and (b) intersection of two simplices in I' is through a face of each of them. A clique complex is typically defined for a graph, and is a simplicial complex with the k-simplices given by the k-cliques of the graph. A simplicial complex also deñnes collection of abelian groups. A chain complex is a sequence of modules (groups) connected by boundary operators (defined later); see Figure 4(F).
Homology provides us with a linear-algebraic tool to extract, from simplicial complexes derived from data, values that describe the shape of the data, such as the number of connected compo- nents (clusters), tunnels (e.g.. doughnut shape), holes (as in Swiss cheese cavities), or higher- dimensional voids, together known as the Betti numbers (Ghrist, 2008) (see Figure 4(C)). As the e-distance (Figure 4(B)) is varied the simplicial complex changes, altering the Betti numbers (Fig- ure 4(C).. The pattern of changing Betti numbers (persistent homology (Ghrist, 2008)) provides a topological characterization of the data distribution that is ieaee-indeenndnnt, invariant under rota- tion and translation, and robust under variations due to data representation, data sampling, and data noise. These Betti numbers are defined in terms of Laplacian matrix (A&), which takes set of simplices and returns an oriented sum of all simplices connected via the boundary simplices of the input. The signed orientations allow simplices to cancel out if they encompass hole, where the hole-surrounding boundaries form the kernel set of the Laplacian. The Betti numbers are precisely the size of these kernels of various simplicial orders. The Laplacian can very large for high-order k, and classical algorithms for Betti number calculation become intractable even for k 2 3. In this paper, we present new quantum representation of the Laplacian separating the boundary action from simplicial complex construction enabling implementation on near-term devices.
A.3 QTDA ALGORITIMM
The seminal approach of Lloyd et al. (2016) to estimate the Betti numbers using quantum computers, which was further analyzed by (Gunn Kornerup, 2019) and (Gyurik et al., 2020), comprises two main steps. The first step of the algorithm is to create mixed state Pk over the states (sx) of k- simplices (over Ha) that in the complex r. The second step is to Hamiltonian simulation (of the boundary operator or the Laplacian As) and quantum phase estimation (QPE) with Ps in the input register (repeatedly projecting simplices from the complex onto the kernel) to estimate the kernel dimension of the Laplacian.
In order to prepare the maximally mixed state Pk as part of the first step, the QTDA algorithm first uses Grover's 's search algorithm (Boyer et al., 1998) to construct the k-simplex state
186)
VISA
#
for the set Sy with |S&l = dim Hd. Then, the mixed state
Σ
(sk) (sk)
Pk =
1kl
ELES
can be prepared from lxx) by applying the CNOT gate each qubit and tracing out into the auxiliary zero qubits. The time complexity of this step is O 12 ) where Ç |S is the fraction of k-simplices that are in the complex I. The number of gates required for this step is (Gunn & Kornerup, 2019). We believe this step is unnecessary, because a random simplex of order can be drawn from the complex efficiently. Nevertheless, the same Grover's search is needed restrict the boundary operator to the complex in the next step.
O 0(ko [nn2 + nkk
v5)
19

---

Published as a conference paper at ICLR 2024
The second step uses QPE estimate the kernel dimension of the Laplacian 4s. For this, the following Dirac operator (the square root of the generalized Laplacian)
0
02
8
B
(4)
Ön-1
0 n-1
is first simulated such that B Blockdiag (A....., An] is block diagonal matrix); since 0c0x+1 O. Given that B has the same nullity (kernel) B², the idea is use Hamiltonian simulation of B (i.e., implement U e! and use QPE with Ps: (computed in the first step) as the input state to estimate its cigenvalues. Since B an n-sparse Hermitian with entries {0, =1), is claimed that this can be simulated using Onn) qubits and O(n²) gates (Low & Chuang, 2017)."
QPE yields an approximate estimate of the eigenvalues of Ax. We need to scale As such that its spectrum is in the interval [0, 1], in order to avoid multiples of 2T: Section C for details scaling. Supposing the smallest nonzero eigenvalue of (the scaled) 4g is greater than 5 >> 0, we then estimated need to estimate the cigenvalues with a precision of least 3 in order to distinguish
zero eigenvalue from others. Therefore, the time complexity of this step is O n² and requires as many gates for its implementation.
This use of QPE provides us with an approximate estimate of some random eigenvalue of AІ. For BNE with additive error c, we need to repeat the two steps ((c-2) times. Hence, the total time complexity of QTDA (original Lloyd al. (2016) version") for BNE with X dim He given by
8x
is
nd 25
Remark (Time Complexity Discrepancy). We note that there is a discrepancy in the total time complexity of the QTDA algorithm reported in (Lloyd et al., 2016) and in the subsequent articles by (Gunn Kornerup. 2019) and (Gyurik al., 2020), primarily due to differences in the underlying assumptions. This relates to simulation of the matrix or Ag. where Lloyd et al. (2016) suggest the requirement of constructing and applying the projector P& at each round (possibly using Grover's search algoritium, although some implementation details are missing). Hence, the total time com- plexity in (Lloyd et al., 2016) product of the time complexity of the two steps. In contrast, the follow-up sludies by (Gunn & Kornerup, 2019) and (Gyurik et al., 2020) assume that we have access to B or De an n-sparse matrix, in order to simulate it in the second step, and therefore the time complexities of the two main steps are added (Gunn & Kornerup, 2019; Gyurik et al., 2020) to obtain the total computational time complexity.
The subsequent articles by (Gunn Kornerup, 2019) and (Gyurik et al., 2020) do not address the issue of efficient quantum construction of B or A from the pairwise distances the n points, and assume that oracle access is given to the nonzero entries of B and their locations.
A.4 POTENTIAL USE-CASES
The proposed NISQ-TDA method advantageous for computing the Betti numbers of simplices- dense complexes, especially higher order Betti numbers (the regime where classical methods fail). Here, we briefly discuss some of the potential applications where NISQ-TDA can be extremely useful and even revolutionary.
3 'The block diagonal form is obtained in the Hamming weight sorted representation of the simplices.
*The serious issue is that the restricted Dirac operator not on hand, and requires Px to known; see Remark 1.
'Exeept that adjust the cost of QPE under spectral interval assumption.
20

---

Published as a conference paper at ICLR 2024
Neural networks. The training and application of artificial Neural Networks (NN) is key methodology of artificial intelligence, and understanding the processing and capabilities of neu- ral networks is critical to that methodology. TDA has been proposed for the analysis of neural networks; in one such proposal (Naitzat et al., 2020), the dataset points are considered to comprise sample of surface and the topological complexity To. considered here to be the sum the Betti numbers, is estimated for the dataset surface. Each layer é, computes a transformation of its input, and so yields a sample of surface, whose topological complexity T. can also be estimated. In the analysis of (Naitzat et al., 2020), the resulting S with h layers, is found decrease rapidly, so that network processing can be understood as a se- quence of topological simplifications. By considering the nature and rapidity of this simplification, insights into network architecture and processing are obtained. Another application of TDA (Guss & Salakhutdinov, 201 8) considers the question of the appropriate width and height of networks, via the estimation of the capacity of network as a function of the network height and maximum width. Here the network is used for classification, dividing the input space into positive and negative instances, and with the decision boundary between these two sets. The capacity of the network is considered be the maximum topological complexity of the decision boundary determined by the network. TDA can be applied to the analysis of decision boundaries. Most importantly, we note that where both (Naitzat et al., 2020) and (Guss & Salakhutdinov, 2018) consider only small Betti numbers, and mainly low-dimensional datasets, further insights could be obtained via estimation of higher Betti numbers of nigheer-dimessional data, reachable via NISQ-TDA.
sequence To, Ti..... Th. for a trained network
Cosmic microwave background. Next, we consider the CMB application, potential use-case of NISQ-TDA, for further discussion due to three favourable reasons. The first is due to the im- mense scientific and cosmic value that is to be gained from meticulous study of the available and prospective high-quality CMB data, including the testing of theories of fundamental physics, the constraining of the fundamental constants of the universe, and even the probing of the existence of parallel and past universes. Secondly, the CMB use-case has been extensively studied from a clas- sical TDA perspective. Indeed, promising results have already been empirically demonstrated for low-order Betti numbers (Cole & Shiu, 201 Sa; Biagetti et al., 2021). A few papers have even pro- duced convincing theoretical results demonstrating the power of Betti numbers to shed light on the CMB use-case, in particular (Feldbrugge et al., 2019b) have derived analytic expressions for low- order Betti numbers proving their usefulness. Thirdly, (Adler et al., 2014) have proven that low and, more importantly, high-order Betti numbers associated with random sample of points generated from different probability distributions contain valuable characterizing properties.
We make the novel connection between the results in (Adler et al., 2014) and its application to the study of the CMB. As a proof of principle, we have implemented the insights from their paper and empirically demonstrated distinguishability of the studied distributions, experimenting with a small number of points to match the regime of interest for NISQ-TDA; see section D.2 for these results. The preliminary results suggest the Betti numbers of small sample set can be used for the detection of non-Gause Gan--aasii in the CMB data, and NISQ-TDA can he used for the estimation of these Betti numbers of all order.
Neuroscience. Topology-base based methods have been used to detect interpretable structures from neural activity and connection data Neuroscience (Giusti al., 2015). Such structural features can yield key insights into neurological processes. In (Giusti et al., 2015), clique topology was used to extract invariant features from neural data that reveal geometric structures of neural correlations in the rat hippocampus. In particular, Betti curves, the distribution of the Betti numbers 8y function
of the edge density p. and integrated Betti values Be, defined as B& So (p)dp. were considered as clique topology features and were computed from neural connectivity data. The article showed that the geometric signatures observed using these topological features in the neural correlations revealed many interesting insights. Neural connections have many unknown non- lineairrrsssss, and clique topology can extract such nonlinear features present in the connectivity data, presenting novel insights in brain activity and connectivity. Indeed, the clique topology features such as Betti curves and integrated Betti values considered in this application require us to compute the Betti numbers of many clique-dense complexes. Thus far, only small order Betti numbers have been considered due to computational impediments. Higher order clique topology features might reveal many new insights in neural connectivity.
21

---

Published as a conference paper at ICLR 2024
Genetics. TDA is also playing an important role in various aspects of genetics. As repre- sentative example, TDA has been exploited to address an important problem in the sequencing of sample of collection of genomes are present (Guzman-Saenz et al., 2019). This problem arises in the investigation of the community of constituent microorganisms in micro-enviionment where differentiating between similar organ- isms leads to many false positive identifications because of the numerous possible assignments of short sequencing reads reference genomes. TDA used to address this problem by extracting information from the geometric structure of data, where said structure is defined by relationships reference database, resulting in separation of true
masse when distinct organisms with very similar genomes
between sequencing reads and organisms positives from false positives and capturing the non-obvious structure defined by the reads indis- criminately mapping to multiple organisms (Guzman-Saan -Sanaz et al., 2019). another representative example, TDA has been exploited to address an important problem in phenotype prediction to whether RNA sequencing- -based gene expression contains enough information to separate healthy and afflicted individuals (Mandal et al., 2020a). This problem is particularly difficult given the poor phenotype predictions from standard machine learning methods. By taking into account the topo- logical information and features relevant to classification from gene expression data, TDA is used gene expression data and to obtain topological
to understand the shape of the very high-dimensione summaries of the gene expressions of subjects contained within this data, rendering significant im- provement in phenotype prediction of disease and confirming that gene expression can be a useful indicator of the presence or absence of a health condition (Mandal al., 2020a). In both of these ex- amples, only small Betti numbers are considered, whereas significant insights should be obtainable using the higher Betti numbers within reach via NISQ-TDA.
B NISQ-TDA DETAILS
Here, present additional details related to different aspects of the proposed algorithm. The first key innovation of NISQ-TDA is the fermionic representation of the full boundary operator B.
B.1 FERMIONIC BOUNDARY OPERATOR
Fermionic fields obey Fermi-Dirac statistics, which means that they admit mode expansion in terms of creation and annihilation oscillators that anticommute. Exploiting this fact, it convenient to map Pauli spin operators to fermionic creation and annihilation operators. The Jordan-Wignet transformation (Jordan & Wigner, 1928) is one such mapping. In this section, we will make use of it to express the boundary matrix.
The Lloyd et al. (2016) restricted boundary operator given in (1) is not in a form that can be easily exccuted quantum computer, nor does it act on all orders, k at the same time. In particular, a high-level description of the action of the boundary operator on a single generic k-dimensional simplex with the location of the ones assumed to be known. Furthermore, this representation is in tensor product form composed of quantum computing primitives that directly map to quantum gates in the quantum circuit model. To begin, define the operator:
0 1
-+ = (0= + 10,)
=
0 0
(5)
This allows writing the full boundary operator in terms of the above operator:
g(m) = o. 8 N....a.
- + 1..8...000
01
+ + 8 Q 8 1 .
Q+ 0 18 180.... 8...
(6)
1=0
22

---

Published as a conference paper at ICLR 2024
4mo
4m:
9mz
4m;
9a.
10)
0)
0)
qa
10)
0
c0
7
Figure 5: Projection onto the simplicial complex Pr: Example circuit diagram with n vertices (and six edges)
90
((#)
(+)
T
P
P (
iqf
qn
(()
P()
P(7))
(())
92
(-
9:
((
Figure 6: Projection onto the simplicial order Ps: Example circuit diagram with 4 vertices
where the a; the Wingnrr (Jordan & Wigner, 1928) Pauli embeddings corresponding to the n-spin fermionic annihilation operators. This fermionic boundary map representation was presented in (Cade & Crichigno, 2021) and (Akhalwaya et al., 2022). For details its correctness and (n))-depth unitary circuit to construct it on a quantum computer, see Akhalwaya et al. (2022).
B.2 PROJECTION OPERATORS
In the main paper, discussed the two projection operators, namely, projection onto the simplicial complex Pt and projection onto the order PR, which are key components of the proposed NISQ- TDA algorithm. Here, we present example circuit diagrams for these two operations. Figure presents an example circuit for Pr with n = 4 vertices, assuming all possible six edges are present. We have n main qubits, and n/2 auxiliary qubits needed, along with operations.
measure and reset
As discussed the main text, we can alternatively use (c) auxiliary qubits, one for each possible edge. Then, we can implement the projector Pr reversibly. With this approach, we can obtain a block-encoding of the Laplacian ÅS using O(n²) auxiliary qubits. The key advantage of this approach is that block-encoding the Chebyshev polynomial (Ā))) is now possible. See details in the next section.
Figure 6 presents sample circuit for Pt. again with 4 vertices. We use Fourier transform (QFT/QFF circuits) as a change basis, followed by the permutation circuit (phase rotations) to implement the count increment.
23

---

In the quantum setting, however, particularly with NISQ computations, generating random states (u)) of exponential size with i..dd entries is not viable. Alternatively, it has been shown that random columns drawn from the Hadamard matrix work very well in practice for stochastic trace estima- tion (Fika & Koukouvinos, 2017). Sampling random Hadamard state vector in quantum com- puter is extremely simple and can be conducted with short-depth circuit. Given an initial state (0), randomly flip the qubits (possibly by applying a NOT gate as determined by random n-bit binary number E [0, 2n 1] generated classically). Thereafter, we simply apply Hadamard gates to all qubits. This produces a state corresponding to a random column of the 2n 2" Hadamard matrix. The columns of Hadamard matrix have pairwise independent entries. Hence, we consider the random state vector (mn) = }ho(n)> i.e., some random Hadamard column with c(l) defining the random index, and then we estimate the moments Aeen)A))ee()) and average over the ny samples Published as a conference paper at ICLR 2024
B.3 STOCHASTIC RANK ESTIMATION
Another key ingredient of our proposed NISQ-QTDA algorithm is a stochastic rank estimation pro- cedure that estimates the Betti number 3g by estimating the rank of As. which replaces the QPE component of the Lloyd et al. (2016) algorithm. The standard approach to estimate the rank of a square matrix is to compute all of its eigenvalues and count the number of nonzero eigenvalues. for which prior work (Lloyd et al., 2016) has employed QPE. In this paper, we propose rank estima- tion procedure that does not require any decomposition of the corresponding matrix. In particular, our rank estimation approach is based on the classical stochastic Chebyshev method (Ubaru & Saad, 2016; Ubaru et al., 2017). Namely, the proposed approach recasts the rank estimation problem to one of estimating the trace of certain (step) function of the matrix. The trace is then approximated by a stochastic trace estimator, where the step function is approximated by a Chebyshev polynomial approximation.
Stochastic trace estimator: Given a Hermitian matrix E RNXN, the stochastic trace estima- tion method (Hutchinson, 1990; Avron & Toledo, 2011) uses only the moments of the matrix to approximate the trace. In the classical setting, trace(A) is estimated by first generating random vector states (17) with random independent and identically distributed (i.i.d) entries, 1,.,, Bl. and then computing the average over the moments (my|A|pr)) namely,
trace( (A)
(vr (mllA)m))
Tly
Any random vectors (e1) with zero mean and uncorrelated coordinates can be used (Avron & Toledo, 2011).
to approximate the trace. The етrоr analysis for this approach is presented in the next section.
Alternatively, quantum t-design circuits are popular way to generate pseudo-random states (Am- bainis & Emerson, 2007; Brakerski & Shmueli, 2019). A t-design circuit outputs a state that is indistinguishable from states drawn from a random Haar measure. These t-designs in quantum computer are equivalent to t-wise independent vectors in the classical world (Ambainis & Emerson, 2007). Short-depth circuits exist (though not as short as above) that are approximate t-designs (Brak- erski & Shmueli, 2019). Such (-design circuits can be used to generate the random states (uz) for trace estimation. Indeed, random vectors with just 4-wise independent entries suffice for trace es- timation (we omit the details here because this approach is less competitive than the above super- short-depth Hadamard construction).
Chebyshev approximation: Assuming the smallest nonzero eigenvalue of A is greater than or equal to 6, then the rank of A can be written as
if x > otherwise
rank(A) trace(h(A)), where h(x) =
(8)
Given the eigen-decomposition
= Σ, A (u) we have the matrix function ((A)
Σ, h(A:)lu:) (u.l where the step function hi(:) takes value of 1 above the threshold 8 > 0. The parameter 8 is assumed to be known (or, in the classical setting, can be estimated using the spectral density method (Ubaru & Saad, 2016)). In the case of TDA, for many simplicial-comple types, lower bound for the smallest nonzero eigenvalue of A can be estimated; refer to Section C.3 for a few examples.
24

---

Published as a conference paper at ICLR 2024
Next, the approach of Ubaru al. (Ubaru & Saad, 2016; Ubaru al., 2017) consists of approx- imating the matrix function h(A) by employing Chebyshev polynomials (Trefethen, 2019), and estimating the trace using the stochastic estimator (7). More specifically, h(A) is approximately expanded in the following manner
M(A) Σ (TT(A), ==0
where (2) is the jth-degree Chebyshev polynomial of the first kind, formally defined as (z(x) = cos(j cos (z)). We therefore have To(z) = 1, (z) = x and Tz+1(z) = 2xT;(x) (z).
The expansion coefficients ej for the polynomial to approximate step function h(t), taking value 1 in (a, b] and elsewhere, are known to be given by
(cos (onss((()) (a) cos (b))
j =
Cg
sin(j cos cos (a)) sim(j cos c0))
1>0
Therefore, the rank given matrix A, with the smallest nonzero eigenvalue greater than or equal ò, can be approximately estimated using the stochastic Chebyshev method as:
1 Dl
rank(A)
Σ (((m
(9)
The method estimates the rank using only the Chebyshev moments of the matrix (m) (A)) Classically, these moments are typically built using the three-term recurrence (Ubaru Saad, 2016). Therefore, we need to compute the Chebyshev moments (uilT, (An]))(Ax)lu) for = 0...., m on the quantum computer using qubitization".
Suppose are given a (1, -llock encoding UA of a Hermitian matrix (Lin, 2022). Then we can use the qubitization idea (Low & Chuang, 2019; Gilyén et al., 2019) obtain block encoding of T2 (AA)
Qubitization Block encoding Chebyshev polynomial of Hermitian matrix:
Given the cigen-decompositionn A = E, A tu:) we have for any eigenstate (u.) that
UA 109) (u.) = 109) A ju.) + (..) A (09)
/us) + [i))).
where [i) is an unnormalized state that is orthogonal to all states of the form (0t") (e). From above, have [..) /1 1 X [+)) for normalized state [1, If U is Hermitian, show that Hi = (ppam(109) lus). [I:)) is an invariant subspace of U.- Next, we consider projection operator the basis B; = span((09) (u,) .|+)) such that:
7 8.
0 -1
That is, Zn is reflection operator restricted each subspace Hi. Next, if define rotation matrix
O = UAZn.
then H4 is invariant to this matrix and its powers. We can show that
(4)
0
Namely, 0 = ZT) is (1, bblocck encoding of (A).
"A previous version of this paper proposed an algorithm that did not make use of qubitization but instead used the relationship between the Chebyshev polynomials and the moments of the Laplacian. However this approach incurs additional complexity factor (see Table C.3) as pointed out to by Adam Connolly and Julien Sorci, necessitating the of qubitization to remove this overhead.
25

---

Published as a conference paper at ICLR 2024
For q 1, Zn is just Pauli Z gate (defined on the subspace of the projection). For q > 1, Zn can be implemented using one additional qubit, two control gates, and a Pauli Z gate. For details, Chapter 7 in (Lin, 2022). Therefore, given Hermitian block encoding of A, we can compute (1, + 1)-block encoding of (A) using qubitization.
(2) auxiliary approach for Pr, then using the circuits for Pk. Pr and compute (1, () Hermiitaan block encoding of Åk, with q = O and form In our case, we use an
B B/ Vn,
(oi = (09) A (0)) + {
Then, using the above approach, we can obtain a (1, q + bbockk encoding T2 (Ax), and form (()) 0o++1 T (Ax) (1)) + I1)
from (61). We can next compute the Chebyshev moments 0(0 = (vrl (Ax) (1i) from ( for
j O..... m and = l...., If we use the measure-and and-reset approach for Pr (n/2 auxiliary and measure and resets), then implementing Zn will be more involved.
The next section presents our analysis of the error and the computational complexities of the above NISQ-TDA algorithm.
C THEORETICAL ANALYSES
We turn the theoretical analysis of our proposed NISQ-QTDA algorithm, first discussing the error analysis that provides bounds on the number of random vectors n, and the polynomial degree m
S c, and subsequently presenting the gate and time com- needed achieve BNE with X* - S
plexities of the algorithm. We then discuss different scenarios under which the QTDA algorithms can achieve significant speedups over classical algorithms, including when our proposed algorithm can be NISQ implementable.
C.I ERROR ANALYSIS
Algorithm returns a Betti number estimate Xk for each order h: = 0,... in Theorem shows that, for the appropriate choice of m and n,, this estimate is BNE with an additive error E (0, 1). Here we present the detailed proof of this theorem.
.....,, n - 1. Our main result
Proof: The proof of the theorem comprises of two parts. The first is related to the error due the stochastic trace estimator. The random state vector in our algorithm (1y) = [hc(t) is some random Hadamard column with c(I) defining the random index, then the estimate (ha()) A ha()) can be viewed as a uniform random sample of the transformed matrix M HAH" with the Hadamard matrix H, i.e., (he(n) A hat)) (Ee(t) JM (ee()) where lex) are basis vectors. Hence, we can use the analysis of unit vector estimators in (Avron & Toledo, 2011 1) to obtain enror bounds. In particular, we apply Theorem 16 of (Avron & Toledo, 2011).
Lemma 1. (Avron & Toledo, 2011, Theorem 16) Assume
given Hermitian matrix A RNXN error tolerance e E (0, 1) and probability parameter 1 E (0, 1). Then, for random state vectors (o)) = (he(t) as random Hadamard columns, 1,..., Uly and for ny 2 (2g(A) log(2/m) where TH (A) max; Ast, we have
IP
(mllAlp)) trace(A) Se.N 21-1
(10)
nly
The proof follows from the arguments establishing Theorem 16 in (Avron & Toledo, 2011), where we set f. c- N in the Hoeffding's inequality, the samples take values in the interval [0, max; M,],, and we know M, N Ai since H has orthogonal columns with || = N.
The second part is due to the error the Chebyshev polynomial approximation of the step func- tion. For our analysis, since the step function is discontinuous function, consider surrogate
26

---

Published as a conference paper at ICLR 2024
function to approximate using the Chebyshev polynomials. In particular, consider the following polynomial, which was considered (Musco Musco, 2015) for the analysis of Krylov subspace methods.
Lemma (Chebyshev Minimizing Polynomial (Musco & Musco, 2015)). Let a > be specified parameter, and the gap Y E (0, 11, and let 2 1. Then, there exists degree polynomial p(x) such that:
p((1 + +)aa) = r)a,
p(x) 2 for all x 2 (1 7)0,
|p(x)] 2- for all x E [0,
Furthermore, when q is odd, the polynomial only contains odd powered monomials and the polyno- mial is given by
p(x) (1 7)) Tm(x/a)
Tm +7)
Here (2) is the m-degree Chebyshev polynomial of the first kind. Utilizing this polynomial, have the following result.
Proposition 1. The Betti number estimate ggvenn by
ttrac(p((A)) (Ax))
(11)
|S
where f(x) = p(1 x) and p(.) is the polynomial in Lemma 2, for parameters a = (1 - 8), and 8 and a degree 2 log(1/e) satisfies T-8
V8
3k Skl
S.
Proof. Suppose the eigenvalues of Å are in the interval {0} U6, 1], then the cigenvalues of I A = 8
will be in the interval [0, 5] U {1}. and by Lemma with = (1 8) and
I-8 we have
Bx S 2 & trace(ā(A (x)) S 3r S 2m
a
since (1 + = and the function is |p(x)) S शमt for all x E [8, 1]. For selecting an appropriate degree m, we want 2m S for which m V values conclude that
log(a/t) suffices. By substituting the
log(1/e)
2 V8
suffices.
We are now ready to complete the proof of the main theorem. The stochastic Chebyshev method approximates the trace as (p = m. E, (o)(())))))) for random vector states luz)- trace,,
(Fa.e.. (7(A))
The Betti number estimate X then be written as X bound
We therefore need to
[8
3x S
tracc,, (i(A)) 8x
X
[S
By triangle inequality, we have
trace,, (p(Ax)) 3x < trace (p(Á.) trace + (racce(((Aw) - [ka]
From Lemma since the maximum diagonal entry of Â is 1, the size is |S and 1p(x:) for x E [0, 1), and we obtain for n, = O (log(2/m))
tracen. (ø( (a)))) trace (()))((() 6
Moreover, from Proposition have
(race(ū((x)) - 3a 5 ee Su
27

---

Published as a conference paper at ICLR 2024
Additional errors: In addition to these errors, during the actual hardware implementation, will encounter additional errors due to noise. Two sources of noise exist, namely (a) shot noise due to measurement and (b) hardware noise. The shot noise is typically modelled using a Gaussian assumption, and hence is assumed reduce O(1/ /T) for T repeated measurements/shots. This implies that the Chebyshev moments we compute will have errors. Suppose the additive error/noise in the moment computations is ET after T' shots and the noise is independent. That is, each moment we compute 0 = (vil ( (Ax))) (oz) + er for j = O,...,m. m. Then, the error due to shot noise in the normalized Betti number estimation X = 1 Ei= -= under the independent
noise assumption, will be
eha
cjeT.
j=0
If use the step function expansion, then we have |cyl S (2/j) and the shot noise error will be ChT I 4er. If we consider the polynomial in the analysis above, then we only have the muth degree polynomial, and |cml 1/ + + I 1. The shot noise error will be even lower. For the expansion of any analytic function (e.g.. we can consider a scaled tanh function for rank estimation (Ubaru et al., 2021)), the Chebyshev coefficients decay exponentially (Trefethen, 2019).
The hardware noise is much more difficult to characterize, since it is hardware and technology dependent. Therefore, in order to account for errors due these two sources of noise, we will need to repeat the whole experiment several times and draw statistics to compute the Betti numbers.
Combining the results yields the desired bound in the theorem.
C.2 COMPLEXITY ANALYSIS
We now discuss the circuit and computational complexities of our proposed algorithm and show that it NISQ implementable under certain conditions, such as clique-dense complexes which com- monly occur for large resolution scale and high order
k. The main quantum component of the algo- rithm comprises the computation of 0.5) = {val (Ax) lur), for = O...., with n, ((e-²) random Hadamard vectors. The random Hadamard state preparation requires n single-qubit Hadamard gates in parallel and O(1) time.
.,, m ~ ((lo((//e)
For given k constructing À involves implementing the boundary operator B and the projectors Pr and Pr. The operator B, involving the sum of n Pauli operators, can be implemented using a circuit with (n) gates. Constructing Pa requires On n) gates, and this succeeds for a random order k. Then for Pr. we need to find all the simplices that are in the complex r. This can be achieved in two ways. The first is the measure-and-rest in parallel and n 1 rounds, and thus the time complexity is O(n). The number of gates required will be On?²). The second approach is to use (*) auxiliary qubits, one per edge, and uncompute when done. Here, since we can consider n edges at a time, the time and depth of this approach
approach which uses n/2 auxiliary qubits
will also be (n) (once an initial projection from uniform is successful, which takes O n time).
Since we need to construct Ty (Ax))) up to the power 0(log(1/c//V))) the circuit has a total gate complexity of On / //)) with depth of Onn log(11c)// The first projection Pa yields a random order k. and the subsequent projections onto a simplicial order needed for higher moments will also have be onto the same order k. Due to the application of the boundary operator B. the subsequent simplicial order projections will result in projection onto one of the simplicial orders 1 or k ++1 1 (after one application) and 2 k or l +-22 (after two applications). Hence, we need to repeatedly apply the order projection (a constant number of times) in order to ensure that we are operating on the right order (in addition to the complex projection). The procedure of computing the m Chebyshev moments is repeated n, = O(c-²) 2)) times with different random Hadamard column vectors, and thus the total time complexity of our algorithm to compute the BNE X is given by
o
1 2
n (1g()/)) n 1)
max
28

---

Published as a conference paper at ICLR 2024
That is, we need O (2) time for the initial projection Pr to succeed, and then ((nloo(1/ee\/V) for Chebyshev moments estimation using qubitization. Suppose oz is the spectral gap of A and Å Ae then 0 dx
C.3 QUANTUM ADVANTAGE
Table 1 summarizes the circuit and computational complexities of our algorithm and compares them to that for the QTDA algorithm of Lloyd et al. (2016). As remarked earlier, the gate and time complexities for this QTDA algorithm reported in Gyurik et al. (2020) and Gunn & Kornerup (2019) are different from those reported in Lloyd et al. (2016), since Gyurik et al. (2020) and Gunn & Kornerup (2019) both assume the operator is given and thus they add the complexities of the two steps (Grover's algorithm and QPE); refer Remark above.
Table I: Comparisons of the eircuit and computational complexities for QTDA compute BNE with an error, a Ç fraction of order-k simplices in the complex, and ō smallest nonzero eigenvalue of Á
Methods
# Qubits
Gates (
Depth Ki
Time 2572 n (lg((1/))
Loyyd et (2016)
2n + log
Ours (NISQ-QTDA-I)
3n/2
O( log( (1))/v/)
Oin log(1 (11))
o max
[ell3
Vo log(1/e)
Ours (TSQ-Q
O (oglog(1/))//
Oin Olxlog(1/e)/
max
vo
In NISQ-TDA-I, auxiliary qubits Pr are heavily reused due the power of measurement and reset. Unfortunately, this qubit-saving strength comes large sampling cost factor which can only be ignored for constant and ||e]|2, which is the 2-norm the coefficients of the Chebyshev approximation to the step function. NISQ-TDA-2 uses reversible computation and qubitization, completely avoiding the large sampling overhead, but instead requiring (?) auxiliary qubits.
Simplices/llique dense complexes: We first discuss examples of complexes that are sim- plices/clique dense. Gyurik et al. (2020) presented few examples of a family of graphs that are clique-dense. Using the clique-density theorem (Reiher, 2016), we can consider a class of graphs/complexes that are clique-dense. Let > k-2 be constant. Then, for graph with
2(K-T]
nodes and ?m²² edges and for given order & 2 3, we have [Sp] = [(n*+1) by the clique- density theorem (Reiher, 2016). If 2 8-1, K., then the graph will be even denser. Such clique-dense complexes occur in TDA when the resolution scale is large (close maximum distance between points), and therefore QTDA algorithms can achieve a significant speedup for BNE over classical algorithms, particularly when we are interested in larger (and many) orders of k. We also refer to the discussions in Lloyd et al. (2016); Gyurik et al. (2020) when quantum TDA algorithms are advantageous.
Laplacian spectral gap: We next discuss different settings, namely when the Laplacian of a given simplicial complex has a sufficiently large spectral gap such that small degree m will suffice for BNE. Not much is known for general simplicial complexes in terms of lower bounds for d, the smallest nonzero eigenvalue of the combinatorial Laplacians (Gyurik et al., 2020). However, we can identify many specific examples of simplicial complexes for which 5 can be large. Indeed, several articles (Goldberg, 2002; Horak & Jost, 2013; Yamada, 2019; Lew, 2020a;b) have studied the spectra of the Laplacian of different simplicial complexes, including random simplicial complexes (Gundert & Wagner, 2016; 6; Kahle, 2016; Knowles & Rosenthal, 2017; Adhikari et al., 2020; Beit-Aharon & Meshulam, 2020).
Some specific complexes: First, let consider few specific types of simplicial complexes. The articles by Horak & Jost (2013) and Yamada (2019) consider the Laplacian spectra of k-regular
Details of this corrected runtime (see acknowledgements and the section Qubitization), an alternate approach and improvements to the qubitization approach is in preparation, Akhalwaya al.
29

---

Published as a conference paper at ICLR 2024
complexes and orientable complexes. A simplicial complex I' is k-regular if and only if all of its k- faces have the same degree dg. whereas a -+-l--mmmoionnal simplicial complex orientable if and only if all k- f-faces of I have orientation such that any two simplices which intersect face induce different orientation on that face. For k-regular simplicial complexes with degree dj = 1, the Laplacian A has all nonzero eigenvalues equal to k + Horak & Jost (2013) show similar results for higher degree and for orientable k-dimensional simplicial complexes. Yamada (2019) presents lower bounds on the nonzero eigenvalues of the Laplacian for these two types of complexes in terms of the Ricci curvature (Bauer et al., 2011) 1) of the complex. For an orientable k-dimensional simplicial complex I' with maximum degree dę for the (k 1)-faces, the smallest nonzero eigenvalues of An. denoted by dg, satisfies
(A: 1)-
2
0g 2 (I+ ()( 1)
dx
where Ke is the Ricci curvature on r. If the complex is orientable k-regular, then the minimal eigen- values of Åş satisfies 8% 2 (k+ 1)kc. We refer Yamada (2019) for bounds on the Ricci curvature Re for k-regular complexes. Such complexes therefore can have large spectral gap between zero and nonzero eigenvalues (i.e., large for the scaled Laplacian) when is sufficiently large.
Next, the article by Goldberg (2002) considers the Laplacian spectra of few specific complexes, For a finite simplicial complex I that contains distinct flapoid clusters of size des the nonzero eigenvalues of the Laplacian are all equal to de o(n.. The article by Lew (2020b) presents a lower bound for the spectral gap of the k-Laplacian Aạ for complexes without missing faces. In particular, for an n- vertex simplicial complex I' without missing faces of dimension larger than E, the smallest nonzero eigenvalue (spectral gap) of Ak. for ls S L, satisfies
òy 2 (e ()dc + k + ln,
where du is the minimal degree of a k-simplex in P. These complexes therefore can also have large spectral gap, under appropriate conditions.
Random complexes: Let now consider random simplicial complexes. For a random complex r with n vertices and constants C1, C2 and p 2 (k + C1) log(n)/n, /n, Gundert & Wagner (2016) show that, if the expected degree of k - faces is d, := p(n k),, then the normalized Laplacian Å
has all its nonzero eigenvalues in the interval
C2 1+ VTx
C₂ VTp
1+
with high probability. It was recently shown by Adhikari et al. (2020) that, for random dense graphs/complexes, the limiting spectral gap (between zero and nonzero eigenvalues) of the nor- malized Laplacian approaches 1/2. Another interesting and relevant result related to the spectra of random complexes was obtained by Beit-Aharon & Meshulam (2020), who consider random subset complexes. Suppose I' is full complex (also called a homological sphere) with all possible sim- plices of order up to n - 1, i.e., an n-simplex. Let Ō be random subset of T, G C Г, of size ñ and let & be the minimal (smallest nonzero) eigenvalue of the k-Laplacian AS of & for k Then, for k 2 and & <>( 0, if the size 4k3 we have (Beit-Aharon & Meshulam, 2020)
g²
P (1- E) S O
These results therefore suggest that random dense complexes will likely have large spectral gap between zero and nonzero eigenvalues. Indeed, this is exactly the regime (large () where the quan- tum algorithms are advantageous. As discussed by Lloyd (1996), such dense complexes occur in TDA when the resolution scale E is large. For such complexes, our proposed QTDA algorithm has great prospects to be NISQ implementable.
Approximate BNE: When the spectral gap of the Laplacian Å is not larger than the chosen threshold 6, our NISQ-QTDA algorithm estimates an approximate Betti number by counting the
1he normalized I Laplacian is defined as Å == D3 Ar. where D3 is the diagonal matrix with the degrees of the faces its diagonal entries.
30

---

Published as a conference paper at ICLR 2024
Betti number estimation
B.
Betti number estimation
Po
Po
10
15
20
2,00 St990
P1
6,59, cade
B
241 dtade
Circuit Fidelity
Degnoe +
Degree
SMRC bine 3010 600)
Hellagger
0:31
100
Depth
Figure 7: Results from classical and noisy simulations: Betti number estimation as a function of Chebyshev degree for (A.) simplicial complexes with stable connections/shape, i.c., large spectral-gap and (B.) complexes with weak connections/shape. C. Fidelity of NISQ-QTDA circuit (measured using Hellinger distance) function of circuit depth for different noise-levels.
(larger) eigenvalues above the threshold 8. This defined in Gyurik et al. (2020) the problem of approximate Betti number estimation (ABNE). Such ABNE will be useful in certain situations, since our method provides larger (dominant) eigenvalues for estimating the Betti number. These small nonzero eigenvalues occur when there are thinly (loosely) connected components the complex. Such connections likely occur when the resolution scale is small, and they might not persist when E increases. Our approach therefore provides way filter out noise and estimate the features that persist at larger resolution scale. Moreover, we note that computing the moments of the Laplacians A₂ (exponential in size) for different & is non-trivial and these moments can used as features for certain downstream learning tasks, for example.
approach filter out small (noisy) eigenvalues and only consider
D ADDITIONAL EXPERIMENT RESULTS
In this section, we present a few additional experimental results that provide further insights into TDA and our NISQ-QTDA.
D. CLASSICAL TDA RESULTS
We first illustrate the performance of the classical version of the proposed stochastic Chebyshev method for Betti number estimation. Figure and B) plot the Betti number estimated function of the Chebyshev polynomial degree for two classes of simplicial complexes, respectively. The first class in Figure 7(A) correspond to complexes that have stable shape (well connected), as in if we remove few edges, the shape (and hence the Betti numbers) do not change. The Laplacian corresponding to such complexes have large spectral gap. We note that the Betti number estimated by our method for such complexes are fairly accurate and small degree polynomial approximation suffices to get a good estimate of the Betti numbers. The black dash lines are the true Betti numbers and the star-solid lines correspond the Betti numbers estimated for four different complexes all with 8 vertices, respectively (2 squares, squares, 6 squares/cube and squares with diagonals included).
31

---

Published as a conference paper at ICLR 2024
The second class in Figure 7(B) correspond to complexes that have weak connections, such that removing a few edges changes the shapes (and Betti numbers) significantly. Such complexes have relatively Laplacian small spectral gap. We note that, we require higher degree approximation for accurate Betti number estimation. We considered four different complexes (1 square and 4 dangling points, 2 squares with two edges connecting them, 3 squares, and 5 squares). Interestingly, we observe that the Betti vs. degree curves for the similar complexes have a similar shape and we can be distinguish between them, even though the Betti numbers estimated are not correct. This shows our method is provides a way to distinguish complexes/shape even with a low degree approximation.
Figure 7(C) plots the Hellinger distance (a measure of fidelity) of our AISQ-TDAA circuit as a function of the circuit depth, i.c., number of vertices/qubits for different noise levels in simulations. The square Hellinger distance between two probability measures P and Q is defined as
1 H² HP(P))) -2 2
/ (VaP-vade
f
In the figure, we consider the Hellinger distance between the measured probabilities using noiseless simulations and noisy simulations, Four different noise levels were considered. The noise-level pairs show the I-qubit and 2-qubit gate eгror rates. The measurement error rate was set be same as the 2-qubit gate error rate. We plot the Hellinger distance restricted to the top 10% of the noise-free free outcomes, thereby focusing only those outcomes with sufficient probability mass at the given shot count. As expected, the Fidelity/noise-eron increases as the circuit depth (and number of qubits) increase.
D.2
CMB RESULTS
The cosmic microwave background (CMB) is the remnant after-glow of the Big Bang, forming an opaque background curtain in the sky. The curtain dates back to when the Universe was about 380, 000 years old (redshift = 1100) when the universe first became transparent to radiation. CMB photons produce a nearly perfect black-body spectrum with a present day temperature of around 2.725 K (Aghanim et al., 2020). This temperature fluctuates by around one part in 10* depending upon the angle in the sky one looks. The uniformity corroborates an epoch of cosmological inflation and provides a window into physics in the early Universe. Recalling that a function é Gaussian when the vector ō = (6(z1),..., ((x,)) is drawn from an n-ddiennsonal Gaussian distribution for all n and for all z,, of particular interest are deviations from Gaussianity in the CMB. These are typically assessed by looking at three-point and four-point correlation functions, the spatial bispec- trum and trispectrum. An application of TDA compares simulations of the CMB with a Gaussian probability distribution to those with particular local injections of non Non--aassianity, e.g., by consid- cring (xx) = d(x) + (olz)()) - (o))² with o(x) a Gaussian field and fNL a parameter capturing the amount of non-Gaussianity. Preliminary investigations in this direction using classical TDA in- clude (Cole & Shiu, 2018a; Feldbrugge et al., 2019a; Biagetti et al., 2021), and the present state of the art deteets fNL O(10). Benchmarking against different values of fNL, NISQ-TDA could compute higher-order Betti numbers associated with the actual sky and test for non-Gaussianity in the CMB potentially greater degree of sensitivity.
Here, we present preliminary results to illustrate how we might apply the insights of Adler et al. (2014) (for example drawing high-dimensional points and excluding the 'core') for the detection of non-Gaussianity in the CMB data. We consider random sets of n = 64 sample points in three dimensions from Gaussian and exponential distributions. The visualization of the data distributions in 3D and the norm distributions are presented in Figure 8 (first two rows). Our goal is to illustrate that by only using homological information (Betti numbers in the form of 'persistent diagrams') ') of very small sample sets (forced to have zero-mean and unit-variance, making the task much more difficult,, we can still distinguish the two distributions. Furthermore, we wish to show that each extra Betti number considered boosts the accuracy. Such an illustration would suggest that we can detect non- -on-Gaussianity in CMB data using NISQ-QTDA to greater degree than low-order classical TDA since QTDA furnishes all high probability Betti numbers of any order.
In order to run our experiment, we use the GUDHI (Maria et al., 2014) package for Betti number estimation of the data at different resolutions to create the persistence diagrams (representing oc- currence/birth and disappearance/death of holes at resolution scale =). See the last row of Figure for example output of the GUDHI pipeline. Directly visualizing the points and the norm dis-
32

---

Published as a conference paper at ICLR 2024
distribut igoussiant
Lengths stribution texponentia)
100
700
600
600
300
200
200
100
0.
PD: 48 gaussian
PDs 49 exponemtial
1000
2.000
Death
Desth
1,300
23000
#0
2300
0.300
0.3
2.0
2.0
8.0
0.5
1.5
13
2.0
25
Birth
Birth
Figure 8: Results for CMB data: Random n = 64 sample points per sample set in three dimensions from the Gaussian distribution (in left column) and the exponential distribution (right column). The first row is the visualization of all 50 sample sets (30 train and 20 test). The second row is the histogram of norms of all the points, and the last row are example persistence diagrams for two sample sets, one from each distribution.
tributions illustrates that the distinguishability task is non-trivial (especially when the form of the distribution is unknown). Secondly, it only when viewing the persistence diagrams (PDs) does the differing behavior become easier to detect. However, a single sample set's associated PD is unlikely be rigorously helpful in telling apart another single sample set. Fortunately, in the simulation use-case as well as for the real CMB data (considering it's presumed rotational invariance) we may repeatedly draw sample sets, creating a of PDs to train and test on. Therefore, we next employ Bayesian (learning) package called BayesTDA (Maroulas et al., 2020) with train (30) and test (20) sample sets, to calculate two Poisson point-process posteriors from the training data, allowing for the calculation of the Bayesian likelihoods of the test data given the two competing posteriors, and culminating in a single Bayes factor for each test data set. The Bayes factors can then be used for threshold. To obviate the choice of threshold we simply calcu- late the Area Under the Curve (AUC) measure of classification accuracy (0.5 as bad as random guessing and is perfect classification).
classification by comparing
33

---

Published as a conference paper at ICLR 2024
Boyes fottor (Beth 1MMC: 0:4500000000000
Boyes Factor (Bett) 2JAUC: 0.931249999999999
1.
3-
(Combired)AUC:: 0. 0.9925
Figure 9: Results for simulated 'CMB' data (Gaussian vs exponential (Adler et al., 2014). but with an enforced mean of zero and variance of unity (element-wise)) Bayes factors and AUC obtain for the data distributions when 31 (top left), 3g (top right) and both 31 and 33 combined (bottom) were used in the learning model
In Figure 9, we present the Bayes factors and AUC obtained for the data distributions when 31 (top left), 82 (top right) and both 31 and 32 combined (bottom) were used in the learning model. We observe that can clearly distinguish the two distributions using the Bayes factors. Moreover, we note that the different Betti numbers contain independent valuable information. Therefore, by potentially computing all relevant Betti numbers of the CMB data using NISQ-QTDA, and using the above approach, we expect to detect non-Gausyianity in the CMB data to higher sensitivity levels than is possible classically (since even for moderate numbers of data points, we cannot compute higher order Betti numbers classically).
34


Reviews:
[{"review_id": "eCsyecX9Tc", "reviewer": "Reviewer_G9wH", "summary": "Finding any application of NISQ (noisy intermediate-scale quantum) technology has been challenging, let alone in machine learning problems. Furthermore, most NISQ algorithms are heuristics in nature and do not come with rigorous guarantees. The authors propose a new NISQ algorithm for topological data analysis (TDA) with a rigorous performance guarantee for solving TDA efficiently (no classical algorithms can solve TDA efficiently due to complexity-theoretic hardness), does not suffer from data loading problems (many previous quantum algorithms only obtain advantage when one neglects the cost in data loading), and is robust to noise.", "questions": "Could the authors analyze the amount of local depolarizing noise on each gate that NISQ-TDA can tolerate? I suspect that the algorithm cannot tolerate a constant amount of noise per qubit (which is how people typically think of NISQ). However, understanding the noise level can still be very useful (e.g., noisy random quantum circuit sampling requires 1/n noise to have exponential quantum advantage).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Understanding potential applications of NISQ is a very important question in the entire field of quantum computing. The work provides a significant step toward obtaining an end-to-end application of NISQ by proposing a NISQ algorithm for topological data analysis.\n\nTopological data analysis is only efficient classically for low-order Betti numbers. Calculating high-order Betti numbers is known to be hard on a classical computer assuming widely believed complexity-theoretic conjectures. Hence, there are quantum advantages in calculating high-order Betti numbers.\n\nWhile quantum algorithms for TDA have been known and have been subject to extensive studies in the past few years, existing quantum algorithms require deep quantum circuits, making them challenging to run on NISQ computers. The work proposes an algorithm NISQ-TDA that uses significantly shallower quantum circuits, making the algorithm suitable for the current quantum technology.\n\nThe authors experimentally tested the proposed NISQ-TDA algorithm on a 12-qubit trapped-ion quantum computer and showed promising results that the proposed NISQ algorithm is robust to realistic device noise.", "weaknesses": "A minor weakness of this work is that the proposed algorithm is not strictly applicable to NISQ devices. NISQ devices can only implement an O(log n)-depth quantum circuit before the measurement outcomes become random noise. While the work provided a significant improvement in the circuit depth, the circuit depth is still O(n).\n\nA theorem analyzing the amount of local depolarizing noise on each gate that can be tolerated by the proposed NISQ-TDA algorithm is missing in the current writeup (the physical experiments do show that the proposed algorithm is promising).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dMjo4t1JXp", "reviewer": "Reviewer_MnCf", "summary": "This paper presents NISQ-TDA, a new quantum algorithm for topological data analysis (TDA) that is readily implemented on near-term noisy quantum devices. This work avoids an unrealistic data input model by constructing an explicit (and shallow) quantum circuit for data-loading. The two major steps in the circuit construction are (1) representing the full boundary operator as a Fermionic boundary operator that allows efficient Pauli decompositions, and (2) projection onto problem-specific simplices using a quantum rejection sampling technique. Notably, the explicit circuit construction of the combinatorial Laplacian operator does not require accessing stored quantum data. \n\nTo estimate the Betti number (defined as the rank of the kernel space of the boundary operator), the authors adopt a stochastic rank estimation method. First, the rank estimation problem is recast into a trace estimation problem through a spectral mapping function $h(\\cdot)$, which can be constructed using a truncated Chebyshev series. Then, by employing a stochastic trace estimation method due to Hutchinson, the Betti number is estimated by summing over finitely many the Chebyshev moments. \n\nNISQ-TDA has been tested on both noisy numerical simulators and trapped-ion quantum devices (Quantiuum). Numerical results suggest good robustness against machine noise.", "questions": "1. Theorem 1 gives a rigorous sample complexity of NISQ-TDA and the total time complexity is $O(\\frac{n\\log(1/\\epsilon)}{\\sqrt{\\delta} \\epsilon^2 \\zeta_k^{2\\log(1/\\epsilon)/\\sqrt{\\delta}}})$. This time complexity looks exponentially better than the best-known classical result. However, this result is not directly comparable with the complexity of Quantum TDA ($O(n^5/(\\delta_k \\sqrt{\\zeta_k}))$) (of course, the QTDA requires stronger quantum computers). Is it possible that NISQ-TDA can outperform the fault-tolerant QTDA in a certain parameter regime?\n\n2. The circuit depth of NISQ-TDA heavily depends on the Chebyshev truncation number. What is the exact dependence of the Chebyshev truncation number in terms of the input data set (or the projection operator)? Does the resource analysis (Fig 1A) treat the Chebyshev truncation number as a parameter depending on the number of vertices, or it is fixed as a constant?\n\n3. In Fig 1B-D, how many shots were used on the hardware to estimate the probability? \n\n4. In Fig 2A, the error seems huge for intermediate-size problems even with moderate machine noise (e.g., (0.001, 0.01) for 1- and 2-qubit gate error). To solve practical problems in the application domains, is there any way to further suppress/mitigate the machine noise for NISQ-TDA?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The Quantum TDA problem was first studied by Lloyd et al. (2016), in which an efficient quantum algorithm was proposed. The algorithm in Lloyd et al. requires a fault-tolerant quantum computer to run Grover's algorithm and digital Hamiltonian simulation (for QPE). This paper appears to propose a new quantum algorithm that does not rely on a fault-tolerant quantum computer with potential superpolynomial speedups compared to classical. \n\nEmpirically, this paper presents both resource analysis (Fig 1A) and real-machine results (Fig 1B-D). Also, a noisy simulation suggests this algorithm is robust to machine noise. The numerical evidence strongly implies that this algorithm could be useful for NISQ devices, justifying the claim by the authors. Potential applications to ML, AI, neuroscience, and cosmology are discussed.\n\nOverall, this paper is well-written and the plots are easy to follow.", "weaknesses": "I feel the technical discussion in Section 3 (especially the projection to a simplicial order) is a bit hard to follow. Is it possible to give some concrete examples (e.g., in terms of explicit circuit & Pauli operators)? Also, it would be better to discuss more on the actual resources (gate counts, # of measurements, etc.) spent on the Quantinuum hardware. See the following \"Questions\" section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AYRZjbBU3A", "reviewer": "Reviewer_tAjA", "summary": "This paper proposes a hybrid classical-quantum algorithm for solving the problem of topological data analysis. More specifically, they consider the problem of estimating the Betti numbers for a simplicial complex. They propose an algorithm that is NISQ-friendly yet still yields speedup over the best-known classical algorithms. Moreover, the algorithm is fully implemented on an existing ion trap device, showing good agreement with simulated results as well as robustness to noise.", "questions": "- I am a bit confused by Figure 1B, C, and D. What exactly are the bars representing? I assume it shows the probabilities of obtaining results corresponding to vertices, edges, triangles, etc., but is it the case that several are omitted for the cube and square?\n- I wonder if there is any intuitive, high-level reasoning for what kind of problem structure is being leveraged here that enables quantum speedup.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This is a very interesting work that proposes to solve a problem that is hard for classical computers, accessible to quantum speedup, and is practically useful. \n- The end-to-end implementation on NISQ devices is quite amazing and the close match with noiseless simulation is also surprising.\n- One particularly interesting aspect of this work is how they avoid the data-loading issue which is typical for many proposed quantum algorithms for machine learning. The projections by mid-circuit measurements appears to be an important step and I wonder if other quantum algorithms can benefit from this.", "weaknesses": "For real quantum advantage, the input data must satisfy several conditions listed at the end of Section 3. The advantage for solving the problem of deciding whether a simplicial complex has exponentially many holes seems less clear and perhaps less practical. It would be great to know if the algorithm still provides speedup for real-world instances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3KxkUgQUhS", "reviewer": "Reviewer_FCsJ", "summary": "The paper proposes a quantum algorithm for topological data analysis (TDA), which is a technique for extracting shape-related features of high-dimensional data. The proposed algorithm NISQ-TDA uses a quantum rejection sampling technique to project onto the data-defined simplicial complex, and a stochastic rank estimation method to estimate the Betti numbers, which are signature values that describe the shape of the data. The paper provides theoretical and empirical analyses of the algorithm, showing that it has error guarantees, short circuit depth, noise resiliency, and potential speedup over classical algorithms for certain classes of problems.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The writing of the paper is clear and well-structured. The paper proposes a quantum algorithm for TDA called NISQ-TDA, which is a technique for extracting shape-related features of high-dimensional data. NISQ-TDA, is designed to work on noisy intermediate-scale quantum devices, which are the current and near-term quantum computers that have limited resources and error rates.\n\n2. The paper presents one of the first quantum machine learning algorithms with short depth and potential significant speedup under certain assumptions. The proposed algorithm neither suffers from the data-loading problem nor does it likely require fault-tolerant coherence for even mid-size datasets.\n\n3. The paper presents results from implementing the entire algorithm on real quantum hardware and noisy simulations, illustrating noise-resiliency at realistic noise-levels. The paper also discusses possible applications of NISQ-TDA for scientific machine learning and AI tasks.", "weaknesses": "1. The reviewer has a basic understanding of quantum computing, but not familiar with TDA. The paper does not provide sufficient background and related work on quantum computing, TDA and QTDA. It assumes that the reader is familiar with these topics and does not cite relevant literature or explain the key concepts and notations.\n\n2. The paper does not provide any empirical evidence of the quantum advantage or noise-resiliency of the NISQ-TDA algorithm. It only shows some preliminary results on small datasets and noisy simulations, without any statistical analysis or comparison with baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)