YITP-26-81

1 Overview↩︎

1.1 Motivation↩︎

Topological data analysis (TDA) is a technique that uses tools from algebraic topology to study properties of data. It is a mature field in machine learning [1] with several applications [2], [3], and has gained attention as a task that may exhibit quantum advantage. TDA works by taking data and forming a ‘simplicial complex’ \(X\), a topological space consisting of higher-dimensional triangles (simplices). One can then use algebraic topology to calculate the number of \(d\)-dimensional holes in the complex, revealing information about the manifold that the data was drawn from. The number of \(d\)-dimensional holes in \(X\) is called the \(d\)’th Betti number and denoted by \(\beta_d^X\). The original quantum TDA algorithm [4] outputs the normalized Betti number \(\beta_d^X/|X_d|\), where \(|X_d|\) is the number of \(d\)-simplices in the complex. In practical TDA applications one is also interested in how many holes persist from one complex to another, when both are formed from the same dataset. This motivates the persistent Betti number \(\beta^{1,2}_d\), the number of \(d\)-dimensional holes present in a complex \(X_1\) that are also present in a larger complex \(X_2\). Indeed a quantum algorithm for the normalized persistent Betti number \(\beta^{1,2}_d/|X_{1,d}|\) was developed in [5]. Determining the computational complexity of these quantities has remained an open problem since these algorithms were proposed, with DQC\(_1\)-hardness of the normalized Betti number being a central unresolved question [6]. Recall that DQC\(_1\) is the class of problems that can be solved efficiently on a quantum computer with one clean qubit and other qubits starting in the maximally mixed state. For example, normalized trace estimation and Jones polynomial estimation are known to be DQC\(_1\)-complete [7], which can be seen as evidence of classical hardness for DQC\(_1\)-hard problems because we do not know efficient classical algorithms for them. Moreover, it is known that it is classically hard to sample from DQC\(_1\)-circuits under plausible complexity theoretic assumptions [8]. We give a more in-depth overview of the topology preliminaries in Section [sec:prelim95topo].

In this paper we consider an alternative normalized quantity: the normalized persistence \[\label{eqn:32Normalized32persistence} \frac{\beta_d^{1,2}}{\beta_d^1},\tag{1}\] the fraction of \(d\)-dimensional holes present in a complex \(X_1\) that persist into a complex \(X_2\). The difference in normalization is practically motivated, since the quantity gives an easily interpretable measure of how robust the topological features are in the initial complex. Indeed, one of the key reasons for studying persistence in TDA is that holes which persist are less likely to be the result of noise in the data and more likely to be true features of the underlying manifold. In addition, since the normalized persistence is not governed by the simplex count \(|X_d|\) it allows for reasonable comparison between the complexes on different datasets. The main goal of this paper is to study the computational complexity of normalized persistence and a family of related quantities.

A key insight of this work is that normalized persistence is naturally a low-energy subspace problem. It is known that Betti numbers are equivalent to the kernel dimensions of Hermitian operators, namely combinatorial Laplacians. Persistent Betti numbers can then be expressed through the overlap of kernels under an inclusion. This gives an immediate generalization of the problems we consider to low (or zero) energy subspace problems for local Hamiltonians, whose complexity we also study. These analogous Hamiltonian problems consist of estimating various spectral or overlap quantities in the low-energy subspace, with suitable normalization. In many physically relevant scenarios, the state of interest lies in the low-energy subspace of a local Hamiltonian, rather than the full Hilbert space. For example, low-energy states of quantum many body systems are typically described by a quantum field theory in the thermodynamic limit [9]. The utility of the low-energy subspace can also be seen in quantum algorithms. Recent work on Hamiltonian simulation shows that restricting to this subspace leads to algorithms whose simulation error depends on an effective low-energy norm, rather than the full operator norm [10], [11]. The relevance of the low-energy subspace can also be seen with practical implementations of quantum computers, since a physical qubit is typically obtained by isolating two energy levels from the rest of the spectrum. This motivates a second key goal of this paper, to establish \(\mathsf{DQC}_1\)-hardness for \(O(1)\)-local Hamiltonian problems restricted to low-energy subspaces. This is a setting directly inspired by the normalized persistence problem, and a strengthening of the previously known log-local results.

Previous work [6] has formalized the problem of approximating \(\beta_d/|X_d|\), as ‘Approximate Betti Number Estimation’. Whilst the complexity of this is still open, Gyurik et al. establish a connection with Low-Lying Spectral Density (LLSD). This problem estimates the number of eigenvalues of a Hamiltonian below a given threshold, normalized by the full Hilbert space dimension (see Problem 11), and is only known to be DQC\(_1\)-hard for log-local Hamiltonians. In [12] Cade and Crichigno established \(\mathsf{DQC}_1\)-hardness of normalized quasi-Betti number estimation. This is estimation of the dimension of the low-energy subspace of a combinatorial Laplacian divided by the dimension of the chain space. However, their result only holds for log-local co-boundary operators and does not hold for clique complexes, which are the complexes arising in TDA. When studying normalized persistence, the more relevant underlying problem replaces the \(2^n\) normalization of LLSD with the dimension of the low-energy subspace; we call this variant the low-energy spectral density (\(\textsf{LESD}\)). We prove that it is DQC\(_1\)-hard and contained in BQP. In contrast to these previous results, this DQC\(_1\)-hardness result holds for Laplacians of clique complexes. On the Hamiltonian side we are able to show that LESD is DQC\(_1\)-hard for \(O(1)\)-local Hamiltonians, strengthening the previous log-local results for LLSD. We also establish DQC\(_1\)-hardness for a variant of normalized persistence, again applying to clique complexes. These results form the first DQC\(_1\)-hardness results for the practical structures arising in TDA, and therefore serve as a step towards resolving whether ‘Approximate Betti Number Estimation’ is DQC\(_1\)-hard.

We show that all the problems considered in this paper are contained in BQP, under state preparation and overlap assumptions. For the problems that are DQC\(_1\)-hard, we are also able to show that this hardness holds with the assumptions for containment in BQP. Thus under the standard assumption that \(\textsf{DQC_1}\not\subseteq \textsf{BPP}\), this work establishes several exponential quantum advantages for problems in TDA and for local Hamiltonians in the worst-case. In order to study problems involving the exact kernel, we introduce a variant of DQC\(_1\) with perfect completeness which we call SDQC\(_1\). Similarly, if this class is classically hard to simulate, our results will imply an exponential quantum advantage for these problems also.

We next review the related literature in more detail. Readers primarily interested in our contributions can safely skip to the summary of our main results in Section 1.3.

1.2 Existing Literature↩︎

1.2.1 Complexity results for TDA↩︎

In recent years a plethora of results on the complexity of various tasks within TDA have emerged. Schmidhuber and Lloyd showed that exact computation of Betti numbers is \(\#\mathsf{P}\)-hard and approximating them to multiplicative error is NP-hard [13]. Crichigno and Kohler [14] showed that the problem of deciding whether \(\beta_d>0\) (referred to as clique homology) is \(\textsf{QMA}_1\)-hard. Note this also implies that approximating \(\beta_d\) to multiplicative error is \(\textsf{QMA}_1\)-hard, strengthening the results of Schmidhuber and Lloyd. The authors also show containment in QMA, but for a gapped version of the problem with a promised lower bound on the smallest eigenvalue of the Laplacian in NO instances. King and Kohler [15] show that this gapped version of clique homology is \(\textsf{QMA}_1\)-hard and contained in \(\textsf{QMA}\), but for weighted clique complexes. Rudolph [16] showed that gapped clique homology on weighted clique complexes is \(\textsf{QMA} _1\)-complete (with a suitable gateset), improving on the results of King and Kohler. Moreover, the author shows that standard clique homology (unweighted and without promise) is PSPACE-complete, strengthening the results of Crichigno and Kohler further. It has also been shown that estimating the minimum eigenvalue of a weighted combinatorial Laplacian is QMA-hard [17]. Finally, Hayakawa et al. show that there exist restricted versions of clique homology that are MA-complete [18].

In related works, it was shown that deciding whether a given hole persists from one complex to another is \(\textsf{BQP}_1\)-hard and contained in BQP [19]. Although this result provides evidence of exponential quantum advantage for deciding persistence of a hole, it does not tell the complexity of learning the persistence of all the holes in the initial simplicial complex.

1.2.2 Quantum algorithms for TDA↩︎

A parallel line of work has developed quantum algorithms for tasks in TDA. The first quantum algorithm was given by Lloyd, Garnerone, and Zanardi [4] and gives a way to estimate the normalized Betti number \(\beta_d/|X_d|\). Subsequent works refined this approach by improving the resource requirements of the original algorithm, for example through shorter circuit-depth constructions [20]. The framework has also been extended from Betti numbers of a single complex to persistent Betti numbers [5], [21]. There has also been work on related topological tasks, such as harmonic persistence [19], high-dimensional Dirichlet problems via quantum walks [22], and torsion detection [23].

At the same time, the regimes in which these algorithms can yield substantial quantum speedups are subtle. A detailed resource analysis was given by Berry et al. [24], and dequantized algorithms have been developed for estimating Betti numbers [21], [24], [25]. These results narrow the parameter regimes in which a quantum advantage is expected.

Moreover, although there has been substantial effort on the analysis of the quantum complexity landscape in TDA, a full understanding of the complexity of normalized Betti number estimation remains open. This motivates the study of the computational complexity of normalized quantities in TDA themselves.

1.3 Main Results↩︎

Here we outline the key results of this paper. This is not exhaustive, as we also prove hardness and containment results for various other problems that are used in our chain of reductions. A summary of our intermediate results is outlined in Section 1.5 and can also be seen in Table 1. A more detailed view of how the hardness of these problems relate to each other, as well as connections to problems from previous works, is given in Figure 1.

4pt

1.3.1 Results for TDA↩︎

Motivated by practical TDA applications and the open question as to whether estimating \(\beta_d/|X_d|\) is DQC\(_1\)-hard, we consider the normalized persistence (equation 1 ). One of the main goals of this paper is to characterize the hardness of the problem of estimating this quantity to inverse polynomial error (which we call ). As an initial step towards this goal, we consider a ‘more general’ problem, which we call Normalized Quasi-Harmonic Persistence. This is motivated by the analogous idea of ‘quasi Betti number estimation’ found in [14]. Given a graph \(G_k\), its clique complex \(\text{Cl}(G_k)\) is the simplicial complex obtained by identifying a complete subgraph of \(d+1\) vertices with a \(d\)-dimensional triangle (\(d\)-simplex). The subscript \(k\) just denotes which graph we are considering, as persistence problems require two graphs \(G_1 \subseteq G_2\). We denote the \(d\)’th combinatorial Laplacian of \(\text{Cl}(G_k)\) by \(\Delta_{k,d}\). Recall that the combinatorial Laplacian is a hermitian operator such that \(\beta_d = \dim\ker(\Delta_d)\) (for more details see Section [sec:prelim95topo]). Then an informal definition of Normalized Quasi-Harmonic Persistence is: given input dimension \(d\) and two weighted graphs \(G_1\subseteq G_2\), output an estimate \(\chi\) such that \[\frac{\dim\mathrm{Im}\,\mathcal{P}_{2,b}|_{\mathrm{Im}\,\mathcal{P}_{1,\eta}}}{\tilde{\beta}_{d,\eta}^1} - \epsilon \leq \chi \leq \frac{\dim\mathrm{Im}\,\mathcal{P}_{2,b+\xi}|_{\mathrm{Im}\,\mathcal{P}_{1,\eta}}}{\tilde{\beta}_{d,\eta}^1} + \epsilon,\] where \(\mathcal{P}_{k,b}\) denotes the orthogonal projector onto the eigenvectors of the \(d\)’th combinatorial Laplacian of \(\text{Cl}(G_k)\) with energy less than \(b\) and \(\tilde{\beta}^1_{d,\eta} = \mathrm{rank}\mathcal{P}_{1,\eta}\) is the \(d\)’th quasi-Betti number of \(\text{Cl}(G_1)\). All threshold and error parameters above are taken to be \(\Omega(\frac{1}{\mathrm{poly}(n)})\) where \(n\) is the number of nodes on \(G_1\) and \(G_2\). A formal definition of this problem is given as Problem 8. When \(b,\eta,\xi\) are sufficiently small, and we have suitable promises on the spectral gaps of \(\Delta_{1,d}\) and \(\Delta_{2,d}\) then the output \(\chi\) will be within \(\epsilon\) of the normalized persistence. In this paper we prove the following theorem.

Proofs of these results can be found in Sections 6.2 and 8 respectively. In order to study the original problem, Normalized Harmonic Persistence (Problem 9) we introduce a new complexity class. This is motivated by the fact that previous hardness results in TDA have usually required complexity classes with perfect completeness, such as \(\textsf{BQP}_1\) or \(\textsf{QMA}_1\). Thus, we introduce a variant of \(\textsf{DQC_1}\) with perfect completeness, which we call Subspace DQC\(_1\) (SDQC\(_1\)). Informally, this class can be seen as DQC\(_1\) with the additional constraint that there exists an unknown subspace of the maximally mixed register, such that any state in that subspace is accepted with probability 1. A formal definition is given in Section 3. This complexity class captures the complexity of TDA and local Hamiltonian problems that are normalized by an exact kernel. We prove SDQC\(_1\)-hardness for several such problems. For the original Normalized Harmonic Persistence problem, defined in terms of Betti numbers and persistent Betti numbers, we propose the following conjecture.

We still obtain containment in BQP under reasonable conditions (Lemma 7). Although we are not able to prove the above conjecture, we identify conditions under which it would hold.

The formal definition of this required condition is given as Conjecture 2. The main reason we are forced to leave this as a conjecture is that the Hamiltonian simulation results [28] we rely on for the other proofs preserve the spectrum up to an inverse-polynomial error, but do not in general preserve the dimension of the kernel. Establishing the required notion of kernel-preserving simulation with combinatorial Laplacians would also be a valuable tool in studying the complexity of related problems in TDA and so it is an important open question. A more detailed discussion on this can be found in Section 7.

1.3.2 Results for Local Hamiltonians↩︎

Since the TDA problems we consider can be thought of as various spectral estimations on combinatorial Laplacians, this gives a natural generalisation to related low-energy problems for Hamiltonians. In particular, we are able to show (either DQC\(_1\) or SDQC\(_1\)) hardness for various problems involving constant local Hamiltonians. We also find that all of these problems are contained in BQP, under suitable assumptions. Here we outline two key problems, and intermediate problems used in the reductions are discussed in Section 1.5. First we consider the analogue of Normalized Harmonic Persistence, which we simply call Normalized Persistence (Problem 7). Given two positive semi-definite (PSD), constant local, Hamiltonians \(H_1, H_2 = H_1 + H_{12}\), \(\textsf{Normalized Persistence}\) estimates \[\frac{\dim\mathrm{Im}\,\mathcal{P}_{\ker H_2}|_{\ker H_1}}{\dim\ker H_1},\] the fraction of \(\ker H_1\) that survives into \(\ker H_2\). Here \(\mathcal{P}_{\ker H_2}\) denotes the orthogonal projector onto the kernel of \(H_2\). We are able to prove the following:

We also consider the low-energy relaxation of this problem, which is analogous to Normalized Quasi-Harmonic Persistence. This problem replaces the kernel of \(H_2\) with its low-energy subspace. We call this problem Normalized Quasi-Persistence and it can be informally stated as follows. Given two PSD, constant local, Hamiltonians \(H_1\) and \(H_2 = H_1 + H_{12}\), output an estimate \(\chi\) such that \[\frac{\dim\mathrm{Im}\,\mathcal{P}_{2,b}|_{\ker H_1}}{\dim \ker H_1} - \epsilon \leq \chi \leq \frac{\dim\mathrm{Im}\,\mathcal{P}_{2,b+\xi}|_{\ker H_1}}{\dim \ker H_1} + \epsilon,\] where \(\mathcal{P}_{2,b}\) denotes the orthogonal projector onto the span of eigenvectors of \(H_2\) with eigenvalue less than \(b\).

This quantity can be viewed informally as a spectral-flow analogue of persistence, i.e., as tracking how a low-energy band evolves under a perturbation. Starting from the zero-energy space of \(H_1\), we add the positive semidefinite perturbation \(H_{12}\) and ask what fraction of the initial subspace remains within a prescribed low-energy band of \(H_2\). Thus Normalized Quasi-Persistence measures the survival of an initially protected subspace under a controlled deformation of the Hamiltonian. The low-energy window \(\mathcal{P}_{2,b}\) is important because exact kernels may not be stable under perturbative Hamiltonian simulations, making the low-energy relaxation the natural robust version of the problem.

In this paper we prove the following:

So far we have not discussed the actual assumptions necessary for containment in BQP. The key assumption that all problems require is efficient preparation of a state close to the uniform mixture over the normalizing subspace. The persistence problems we described above also require the initial and final subspaces to have a ‘large’ overlap. Precise definitions of these assumptions are given in Section 4.

It is important to note that, for all DQC\(_1\)-hard problems we consider, DQC\(_1\)-hardness continues to hold under the assumptions necessary for containment in BQP. This means that these problems exhibit an exponential quantum advantage, under the assumption that \(\textsf{DQC_1}\not\subseteq\mathsf{BPP}\). Analogously, the problems for which we prove SDQC\(_1\)-hardness also remain SDQC\(_1\)-hard under the assumptions for containment in BQP. Thus, unless SDQC\(_1\) is classically simulable, these problems will also demonstrate an exponential quantum advantage. Whilst it seems intuitive that SDQC\(_1\) should be classically hard to simulate, proving this is a key open question resulting from our work.

1.4 Complexity Landscape↩︎

A unifying theme of our results is that they connect a number of previously isolated problems into a single complexity landscape. This can be clearly seen in Figure 1. In this diagram solid arrows point to harder problems, so that the chain of reductions we consider can be seen clearly. We also include problems from prior works that are related to the ones we study. Formal statements of these related problems are collected in Appendix 10.

The dotted arrows in Figure 1 should be read as pure-state specializations of the subspace-normalized problems studied here:

• If we consider the pure-state version of the Normalized Quasi-Persistence problem, namely the case \(\dim\ker H_1=1\), then it recovers the Low-energy Overlap problem (Problem 14) in the unique initial-ground-state regime. In this specialization, the large overlap condition should be replaced by the corresponding YES/NO overlap promise.

• Similarly, when \(\dim\ker H_1=1\), Normalized Persistence recovers Kernel Overlap (Problem 13) in the unique-ground-state regime.

• The pure-state version of Low-energy Normalized Subtrace naturally leads to the guided local Hamiltonian problem: in the unique-low-energy-state limit, LENS becomes an energy-estimation problem for a single guided ground state.

• On the TDA side, when the initial harmonic space is replaced by a specified harmonic representative or cycle state, Normalized Harmonic Persistence specializes to Harmonic Persistence (Problem 12).

Thus, this work provides a unified framework and complexity landscape for studying energy-estimation and spectral-density-estimation problems for local Hamiltonians and TDA.

1.5 Techniques↩︎

The technical contribution of the paper has three parts. First, we isolate a family of subspace-normalized spectral and persistence problems that capture the quantities naturally arising from normalized persistence, and we introduce the complexity class SDQC\(_1\) for exact-kernel variants. These definitions are not merely auxiliary notation. Rather, they form the complexity landscape summarized in Table 1 and Figure 1. Second, we adapt circuit-to-Hamiltonian hardness arguments to this subspace-normalized setting by controlling the relevant low-energy spaces, rather than the full Hilbert space. Third, we prove containment results under state-preparation and overlap assumptions, which identify when the same quantities can be efficiently estimated in BQP.

1.5.0.1 Reduction landscape.

In order to prove DQC\(_1\)-hardness and SDQC\(_1\)-hardness of the main problems we consider, we gradually prove hardness for several intermediate problems. These results will also be of interest in their own right, as spectral density and overlap problems. In particular, they offer strengthening of some known hardness results to \(O(1)\)-local Hamiltonians. A visual summary of the overall chain of reductions can be seen in Figure 1.

A natural starting point is Brandão’s [26] proof that Normalized Subtrace is DQC\(_1\)-hard for \(O(\log(n))\)-local Hamiltonians. That problem estimates the trace below a threshold \(\eta\), normalized by the full Hilbert-space dimension: \[\frac{1}{2^N}\sum_{0\leq\lambda_i\leq\eta}\lambda_i.\] For a precise formulation see Problem 10. Brandão’s argument uses a circuit-to-Hamiltonian construction in which the average of the first \(2^{N-1}\) eigenvalues encodes the rejection probability of a DQC\(_1\) circuit. However, this argument does not directly give the constant-local hardness statements needed here. The log-local construction keeps the relevant normalization matched to the encoded circuit space, whereas a standard \(O(1)\)-local clock construction introduces a much larger Hilbert space. With the full Hilbert-space normalization, the spectral signal is then diluted and no longer determines the desired eigenvalue average to inverse-polynomial precision.

1.5.0.2 Low-energy normalization.

The starting point for our hardness proofs is a low-energy variant of the above, which we call Low-Energy Normalized Subtrace LENS (Problem 1). This is the problem of estimating the trace below a threshold \(\eta\), but instead now normalized by the dimension of the span of eigenvectors with eigenvalue at most \(\eta\). This quantity is therefore given by \[\frac{1}{\dim S_{\leq \eta}}\sum_{0\leq\lambda_i\leq\eta}\lambda_i.\] This change in normalization allows us to prove that LENS is DQC\(_1\)-hard for \(O(1)\)-local Hamiltonians (Section 5.2), a strengthening of the hardness for Normalized Subtrace with log-local Hamiltonians.

1.5.0.3 Low-energy spectral density and exact kernels.

From here, inspired by LLSD [6], we consider two spectral density problems: Low-Energy Spectral Density (LESD) and the Low-Energy Kernel Density (LEKD). Consider a PSD Hamiltonian \(H\), and let \(S_{\leq \eta }\) be the space spanned by its eigenstates with eigenvalue at most \(\eta\). Then LESD is the problem of estimating \(\dim S_{\leq b}/\dim S_{\leq \eta}\), for \(b\leq\eta\) (see Problem 3) and LEKD is the problem of estimating \(\dim \ker (H)/\dim S_{\leq \eta}\) (see Problem 5). We are able to show DQC\(_1\)-hardness of LESD for \(O(1)\)-local Hamiltonians via a polynomial time truth-table reduction from LENS. This proof (Section 5.3) uses a quadrature argument that is closely related to the analogous proof for LLSD. We also show that LEKD is SDQC\(_1\)-hard for \(O(1)\)-local Hamiltonians (Section 5.5). This proof uses the same circuit to Hamiltonian construction as the LENS proof, and we call the resulting \(N\)-qubit Hamiltonian \(H_\textsf{SDQC_1}\). However, the perfect completeness of the SDQC\(_1\) instance now implies that \[\frac{\dim\ker H_{\textsf{SDQC_1}}}{\dim S_{\leq \eta}} = \frac{\dim \mathcal{S}}{2^{N-1}}\] for a suitably chosen \(\eta\), where \(\mathcal{S}\) denotes the subspace that is accepted perfectly. By amplifying the circuit, the acceptance probability can then be made sufficiently close to the quantity above.

1.5.0.4 Subspace persistence.

From here we are able to prove DQC\(_1\)-hardness of Normalized Quasi-Persistence and SDQC\(_1\)-hardness of Normalized Persistence, both for \(O(1)\)-local Hamiltonians. These are the problems discussed in Section 1.3.2. For these proofs we divide the circuit Hamiltonian into two parts, such that one part can be treated as the initial Hamiltonian \(H_1\) and the other can be treated as a perturbation \(H_{12}\) (where \(H_2 = H_1 + H_{12}\)). Both of these proofs make use of the fact that \(\ker H_2 \subset \ker H_1\), which follows from our Hamiltonian construction. For the Normalized Quasi-Persistence proof, we perform a reduction from LESD. This follows since the kernel property implies that \[\dim \text{Im} \mathcal{P}_{2,b}|_{\ker H_1} = \sum_{0\leq\lambda_{2,i}\leq b}1\] for suitable choices \(b\leq \eta\). For this same choice of \(\eta\) we also have \(\dim S_{\leq \eta} = \dim \ker H_1\), and so we see that a suitable instance of Normalized Quasi-Persistence is sufficient to solve the instance of LESD with the DQC\(_1\) Hamiltonian. The proof of SDQC\(_1\)-hardness of Normalized Persistence proceeds similarly, with the main difference being that we instead reduce from LEKD. Now, again due to the perfect completeness of SDQC\(_1\), we can form an instance of Normalized Persistence such that \[\frac{\dim \text{Im}\mathcal{P}_{\ker H_2}|_{\ker H_1}}{\dim \ker H_1} = \frac{\dim \mathcal{S}}{2^{N-1}}.\] This is then sufficient to solve the instance of LEKD with the SDQC\(_1\) Hamiltonian, which completes the proof.

1.5.0.5 Passing to clique-complex Laplacians.

For the DQC\(_1\)-hardness of TDA problems we follow a similar chain of reductions. We begin by considering LENS for TDA (see Problem 2). This is simply the same problem as LENS, where now the input is restricted to the Laplacian of a clique complex. We prove that this is DQC\(_1\)-hard using a reduction from LENS. This proof makes use of the fact that the DQC\(_1\) Hamiltonian we consider is \(O(1)\)-local, together with existing results which show that such a Hamiltonian can be simulated by a combinatorial Laplacian. Note that by simulation here, we mean that given a Hamiltonian there exists an efficient encoding so that the spectrum of the Hamiltonian is approximated in the low-energy subspace of a combinatorial Laplacian acting on a larger space. The construction necessary for this follows from [28] and [17]. We give an overview of the latter in Appendix 9. Once this notion of simulation is established, the low energy normalized subtrace of \(H_\textsf{DQC_1}\) can be approximated by a suitable combinatorial Laplacian. From here we can prove that LESD for TDA (Problem 4) is DQC\(_1\)-hard, using the same argument as the reduction from LENS to LESD. We can then prove that Normalized Quasi-Harmonic Persistence (Problem 8) is DQC\(_1\)-hard by reducing from LESD for TDA. This is achieved simply by considering an instance of NQHP with the two graphs equal. Then for \(b\leq \eta\) we have \[\mathrm{Im}\mathcal{P}_{2,b}|_{\mathrm{Im}\mathcal{P}_{1,\eta}} = S_{\leq b}.\] This immediately allows a suitable instance of NQHP to solve the hard instance of LESD for TDA, completing the reduction. The exact-kernel version, NHP, requires a stronger simulation preserving kernel dimensions, which we formulate separately as Conjecture 2.

1.5.0.6 Containment.

Finally, the containment results identify the algorithmic assumptions under which these subspace-normalized quantities are efficiently estimable. For the low-energy spectral problems, the main assumption is efficient preparation of the uniform mixture over the relevant low-energy subspace. For the persistence problems, one also needs a large-overlap condition ensuring that the projected subspace can be sampled or amplified without losing inverse-polynomial signal. These containment statements clarify that the newly defined problems are not merely hardness gadgets, but genuine BQP estimation problems under natural state-preparation and overlap assumptions.

1.6 Discussions and open questions↩︎

Our results suggest several open directions concerning both the complexity classes introduced here and the normalized spectral quantities that motivate them. We discuss these questions from four perspectives: containment in DQC\(_1\) and SDQC\(_1\), possible refinements through intermediate classes such as \(\tfrac{1}{2}\mathsf{BQP}\), trade-offs between locality and dimension in circuit-to-Hamiltonian constructions, and the possibility of dequantization in weaker precision regimes.

1.6.0.1 Containment in \(\textsf{DQC_1}\)

None of our results consider containment in \(\textsf{DQC_1}\) for \(\textsf{DQC_1}\)-hard instances. This is due to the limitation of state preparation in Lemma 8 for \(\textsf{DQC_1}\)-hard instances. It is an interesting open problem if one can show \(\textsf{DQC_1}\)-completeness (or \(\textsf{SDQC_1}\)-completeness) for the low-energy and normalized persistence problems.

1.6.0.2 \(\tfrac{1}{2}\mathsf{BQP}\)-hardness

Recently, a complexity class called \(\tfrac{1}{2}\mathsf{BQP}\) (half-BQP), has been introduced in [29]. This complexity class is known to sit between \(\mathsf{DQC}_1\) and \(\mathsf{BQP}\). Therefore, a natural way to further refine the hardness and containment results would be to show \(\tfrac{1}{2}\mathsf{BQP}\)-hardness or containment in \(\tfrac{1}{2}\mathsf{BQP}\). Moreover, it would be interesting to introduce the notion of perfect-completeness to \(\tfrac{1}{2}\mathsf{BQP}\) (one may name it by “\(\tfrac{1}{2}\mathsf{BQP}_1\)”) and study the relations with the class.

1.6.0.3 Trade-offs between locality and dimension in circuit-to-Hamiltonian

The locality of the circuit-to-Hamiltonian construction and the normalization factor of persistence problems are closely related. We have seen that the current \(O(1)\)-local clock Hamiltonian construction leads to exponential blow-up for the dimension of the clock-register. Recently, more fine-grained analysis for the trade-offs between locality and size has been initiated [30]. It would be an interesting future direction to study a fine-grained tension between the locality and dimension in the context of normalized persistence and low-energy problems.

1.6.0.4 Dequantization

In this paper, we studied a number of low-energy problems and normalized persistence problems. Our \(\textsf{DQC_1}\) and \(\textsf{SDQC_1}\) hardness results suggest that these problems are not likely to be dequantized in the inverse-polynomial precision regime. It is an interesting open problem whether the problems introduced in this paper can be efficiently solved classically in the constant precision regime using similar approaches to those in prior works  [25], [31].

1.6.0.5 The complexity class \(\mathsf{SDQC}_1\)

We introduced \(\mathsf{SDQC}_1\) to capture the hardness of exact-kernel persistence problems. It seems that the newly introduced \(\mathsf{SDQC}_1\) and \(\textsf{DQC_1}\) are likely incomparable due to the spectral gap condition on the acceptance operator in \(\mathsf{SDQC}_1\). Establishing more detailed relationships between \(\mathsf{SDQC}_1\) and \(\textsf{DQC_1}\) is an important future direction.

1.6.0.6 Discharging the state-preparation assumption.

All of our containment results assume access to a polynomial-size circuit preparing the uniform mixture over the low-energy subspace. It is an important future direction to understand the instances of local Hamiltonians or homology that allow efficient low-energy subspace state preparation. Recently low-energy state preparation algorithms that beat native Grover search have been discovered [32], [33]. It is interesting to fit this framework for the preparation of mixtures over low-energy subspace. Moreover, the Khovanov homology algorithm of Schmidhuber et al. [34] utilizes a pre-thermalization procedure for the combinatorial Laplacian. As the low-temperature Gibbs state seems to have a good connection to the uniform mixture over the low-energy subspace, it is an interesting open direction to understand the efficiency of Gibbs state preparation for combinatorial Laplacians and its application to normalized persistence problems.

1.7 Organization↩︎

In Section 2, we recall the necessary preliminaries on topology that are used in this paper. In Section 3, we introduce the new complexity class \(\mathsf{SDQC}_1\) and discuss its basic properties. In Section 4, we formally introduce the low-energy and normalized persistence problems and state the corresponding results. Section 5 proves the hardness results for the local-Hamiltonian problems. Section 6 develops the corresponding TDA hardness results, and Section 7 discusses the conjectured exact-kernel version for normalized harmonic persistence. In Section 8, we provide proofs of containments that are postponed in Section 4.

2 Preliminaries↩︎

Here we give an overview of the general TDA pipeline as well as the necessary topology results to understand our problem statements and proofs. An abstract simplicial complex \(X\) is a collection of sets of vertices, which are closed under taking subsets [35]. A set in \(X\) consisting of \(d+1\) points is called a \(d\)-simplex. We note there are differing conventions on whether to include the empty set in \(X\). For this discussion we assume that the sets in \(X\) are non-empty. Geometrically, a \(d\)-simplex can be thought of as a \(d\)-dimensional triangle. For example, a \(0\)-simplex is a point, a \(1\)-simplex is a line segment, a \(2\)-simplex is a triangle and a \(3\)-simplex is a tetrahedron.

Next we outline how a simplicial complex can be formed from data, for the purpose of TDA. Consider some data \(x_i\in \chi\) with \((\chi, \rho)\) a metric space. In typical applications this will be Euclidean space, but any metric space will suffice. Then we fix a lengthscale \(\epsilon\) and form a graph \(G\) with nodes \(\{x_i\}\) and edges between any two points such that \(\rho(x_i,x_j)\leq \epsilon\). We then consider the clique complex of \(G\), \(X=\mathrm{Cl}(G)\). That is, the collection of complete subgraphs in \(G\), where each subgraph of \(d+1\) points is identified as a \(d\)-simplex. One can indeed check that \(\mathrm{Cl}(G)\) is a simplicial complex. A complex defined in the way above is called a Vietoris–Rips complex. This is not the only way to construct a simplicial complex from data; for example, one can instead construct a Čech complex.

A simplex \(\sigma\) is denoted by a collection of its vertices. For example, \(\sigma = [v_1,v_2,v_3]\) denotes the 2-simplex with vertices \(v_1,v_2,v_3\). If two simplices have the same vertices, we identify them as equal if they are related by an even permutation and introduce a negative sign if they are related by an odd permutation. For example, \([v_1,v_2,v_3] = [v_3,v_1,v_2] = -[v_1,v_3,v_2]\). We fix some (arbitrary) ordering of the vertices and denote the set of \(d\)-simplices, with vertices in that order, by \(X_d\). We then consider the complex vector spaces \[C_d(X) = \mathrm{Span}(X_d).\] We refer to the spaces \(C_d(X)\) as chain spaces. We can also form the whole chain space \[C(X) = \bigoplus_{d=0}^{n-1}C_d(X),\] where \(n\) is the number of vertices present in \(X\) (or number of data points in the TDA context). It is clear that \(C(X)\) is then a complex vector space spanned by all of the simplices (of all possible dimensions) present in \(X\). Taking these spaces to be over the complex numbers is natural for quantum TDA, since it gives a natural way to represent \(C(X)\) as a suitable Hilbert space. These spaces can be defined generally as free abelian groups, but this generality is unnecessary for our discussion. In this paper we take the graph \(G\), from which we form the simplicial complex, to have vertex weights \(w(v_i)>0\). In practical TDA applications, these weights can be used to encode additional scalar information about the data. This is a strict generalization, since if the weighting is not required one can take all the weights equal to one. We can extend the weighting to higher dimensional simplices by taking the weight of a simplex to be the product of its vertex weights. That is, for \(\sigma\in X\) we define \[w(\sigma) := \prod_{v\in\sigma}w(v).\] This then allows us to define the following inner product on \(C(X)\), for any \(\tau,\sigma\in X\), \[\braket{\tau|\sigma} = \begin{cases} (w(\sigma))^2 &\text{if }\sigma=\tau\\ 0 & \text{otherwise.} \end{cases}\] We note that this inner product definition matches that of [15] and [19]. Then relative to this inner product, it is clear that we can form an orthonormal basis of \(C_d(X)\) by normalizing the simplices in \(X_d\) by their weight. We define \(\mathcal{B}_d =\{\sigma' = \frac{1}{w(\sigma)}\sigma|\sigma\in X_d\}\) to be this orthonormal basis of \(C_d(X)\). From here we use \(\sigma'\) to denote the normalized basis element corresponding to \(\sigma\). Then we can define the weighted boundary maps \(\partial_d:C_d(X)\to C_{d-1}(X)\) by their action on these basis elements and extending them linearly. Consider \(\sigma = [v_0,v_1,\ldots,v_d]\in X_d\), with \(\sigma' \in \mathcal{B}_d\) as above, then we define \[\partial_d \sigma' = \sum_{i=0}^d(-1)^iw(v_i)(\sigma\setminus \{v_i\})'.\] That is, the weighted alternating sum of the simplices obtained from \(\sigma\) when each vertex is removed. Note that if all \(w(v_i) = 1\) then the usual, unweighted, boundary map definition is recovered. One can then check that for all \(d\geq 1\), \(\partial_{d-1}\circ\partial_{d} =0\). This means that \(C_d(X)\) together with the corresponding boundary maps form a chain complex: \[\cdots \xrightarrow{\partial_{d+2}} C_{d+1}(X) \xrightarrow{\partial_{d+1}} C_{d}(X) \xrightarrow{\partial_{d}} C_{d-1}(X) \xrightarrow{\partial_{d-1}} \cdots\] We will also be interested in two subspaces related to the boundary maps \(\partial_d\). These are the space of \(d\)-dimensional cycles \(Z_d(X)\) and \(d\)-dimensional boundaries \(B_d(X)\), where the following are given by: \[\begin{align} Z_d(X) &= \ker(\partial_d)\\ B_d(X) &= \text{Im}(\partial_{d+1}). \end{align}\] Note that since \(\partial_{d}\circ\partial_{d+1}=0\) we have that \(B_d(X)\) is a subspace of \(Z_d(X)\). This allows us to define the \(d\)’th homology ‘group’ as the quotient \[H_d(X) = Z_d(X)/B_d(X).\] We remark that calling \(H_d(X)\) a group is motivated by its more general definition, where \(C_d(X)\) are defined as free abelian groups. However, with our choice to work over the complex numbers, \(H_d(X)\) is just a complex vector space spanned by cosets. The main difference this definition leads to is that \(H_d(X)\) will be isomorphic to a direct product of copies of \(\mathbb{C}\), whereas in the more general case \(H_d(X)\) can have torsion groups in its decomposition. This means that the latter case captures additional topological information than our definition, such as whether the space contains a twist. It is also important to note that any choice of weights \(w(v_i)>0\) will lead to isomorphic homology groups, and hence the weights do not affect the Betti numbers.

Intuitively, cycles are the chains of simplices that form a closed loop (or higher dimensional analogue). Boundaries are then those cycles that also enclose a simplex, i.e. form its boundary. Hence the homology \(H_d(X)\) captures the cycles which are not boundaries of something, meaning they correspond to ‘holes’ in \(X\). This leads us to the definition of the \(d\)’th Betti number \[\beta_d = \dim (H_d(X)),\] which counts the number of \(d\)-dimensional holes present in \(X\). These are one of the main objects of study in TDA. The Betti numbers \(\beta_d\) can also be reformulated as the kernel dimension of (weighted) combinatorial Laplacians \(\Delta_d\). These are PSD Hermitian operators \(\Delta_d:C_d(X)\to C_d(X)\) given by \[\Delta_d = \partial_d^\dagger \partial_d + \partial_{d+1}\partial_{d+1}^\dagger\] where the adjoint \(\partial^\dagger\) is defined relative to the inner product specified above. Then we have \[\beta_d = \dim\ker(\Delta_d).\] The combinatorial Laplacians are of central importance in quantum TDA, since they allow Betti number estimation to be reframed as estimating the ground state dimension of a suitable Hamiltonian. Indeed, the combinatorial Laplacian of \(\mathrm{Cl}(G)\) is equal to the ‘fermion hardcore model’ on the complement graph \(\bar{G}\) [6]. This representation of \(\Delta_d\) is crucial in one of the constructions we use, more details can be found in Appendix 9. Since \(\beta_d = \dim\ker(\Delta_d)\) the dimension of the kernel of \(\Delta_d\) is not affected by the choice of weights \(w(v_i)\). However, altering the vertex weights does change the non-zero spectrum. This is an important detail as it is what allows a combinatorial Laplacian to simulate a \(k\)-local Hamiltonian in its low-energy subspace [17]. This is necessary for our hardness proofs and therefore the main reason why our results are stated for weighted complexes.

In TDA we are not just interested in the clique homology at one lengthscale \(\epsilon\), but rather this process is performed at multiple lengthscales. In particular, one will be interested in seeing how many of the \(d\)-dimensional holes present at lengthscale \(\epsilon_i\) are still present at \(\epsilon_j>\epsilon_i\). This notion is captured by the persistent Betti number \(\beta_d^{i,j}\). Computing this for multiple lengthscales allows us to track which topological features are robust, and therefore less likely to be a result of noise in the data. Intuitively, one can visualize that when \(\epsilon=0\), there will be no holes in the complex. Then as the lengthscale is increased, structure emerges and holes start to appear. Then as \(\epsilon\to \infty\) the graph is fully connected and all the holes have died.

Let \(X_i\) and \(X_j\) be the simplicial complexes obtained from the data at lengthscales \(\epsilon_i\) and \(\epsilon_j\) respectively. Then \(X_i \subset X_j\) and so complexes formed in this way form a filtration, a chain of subcomplexes where each is contained in the next. We can then define the inclusion map \[\iota^{i,j}_d:C_d(X_i) \xhookrightarrow{}C_d(X_j).\] This induces a homomorphism between \(H_d(X_i)\) and \(H_d(X_j)\) \[\begin{align} (\iota^{i,j}_d)_*:H_d(X_i)&\to H_d(X_j)\\ z_i+B_d(X_i) &\mapsto \iota^{i,j}(z_i)+B_d(X_j), \text{ } z_i\in Z_d(X_i) \end{align}\] The \(d\)’th persistent Betti number is then given by \[\beta_d^{i,j} = \dim \text{Im}(\iota^{i,j}_d)_*.\] The image Im\((\iota^{i,j}_d)_*\) is called the persistent homology group. It consists of the non-trivial homology elements in \(H_d(X_i)\) that are also non-trivial in \(H_d(X_j)\). The persistent Betti numbers are of key interest for this paper, as the main quantity we study is given by the normalized persistence \[\frac{\beta_{d}^{i,j}}{\beta_d^i}\] as in equation 1 . The inclusion also gives us a way to express persistent Betti numbers in terms of projectors and the combinatorial Laplacians. If we denote the \(d\)’th Laplacians of \(X_i\) and \(X_j\) by \(\Delta_{i,d}\) and \(\Delta_{j,d}\) respectively, then \[\beta_d^{i,j} = \mathrm{rank}(\mathcal{P}_{\ker \Delta_{j,d}} \circ \iota^{i,j}_d|_{\ker \Delta_{i,d}})\] where \(\mathcal{P}_{\ker \Delta_{j,d}}\) is the orthogonal projector onto \(\ker(\Delta_{j,d})\). We use this definition of the persistent Betti number throughout this paper, although we often suppress the inclusion and just write \[\mathcal{P}_{\ker \Delta_{j,d}}|_{\ker \Delta_{i,d}}.\]

There is one more way to describe the \(d\)’th homology group that we require, namely the Harmonic subspace \(\mathcal{H}_d(X_i)\). This is given by \[\mathcal{H}_d(X_i):= Z_d(X_i) \cap B_d(X_i)^\perp.\] One can then show [36] that \[\ker(\Delta_d) = \mathcal{H}_d(X_i)\] which implies we also have \(\beta_d^i = \dim(\mathcal{H}_d(X_i))\). We can also see that the \(d\)’th Harmonic subspace and \(d\)’th homology group are isomorphic via the following map \[\begin{align} \varphi_d:H_d(X_i)&\xrightarrow{\sim}\mathcal{H}_d(X_i)\\ z+B_d(X_i) &\mapsto \mathrm{Proj}_{B_d(X_i)^\perp}(z),\text{ }z\in Z_d(X_i) \end{align}\] This isomorphism gives a way to choose a representative of elements in the homology, since the actual homology elements are cosets and so two cycles can represent the same element if they differ by a boundary. Analogous to the induced map \((\iota^{i,j}_d)_*:H_d(X_i)\to H_d(X_j)\), we can also construct a linear map between the corresponding harmonic spaces. We denote this by \(\mathbf{i}^{i,j}_d\) and it is given by \[\mathbf{i}^{i,j}_d = \mathrm{Proj}_{B_d(X_j)^\perp}|_{\mathcal{H}_d(X_i)}: \mathcal{H}_d(X_i)\to\mathcal{H}_d(X_j).\] Given a harmonic \(\zeta = \varphi_d(z+B_d(X_i))\in\mathcal{H}_d(X_i)\), the map above determines whether the corresponding homology element is still present in \(H_d(X_2)\). That is, \(\mathbf{i}_d^{i,j}(\zeta)=0\) if the hole has died and otherwise it has persisted. This property was used in [19] to study the problem of whether a classical description of a hole in \(X_i\) (a harmonic representative) persists into \(X_j\), in the sense that its projection onto the harmonic space \(\mathcal{H}_d(X_j)\) is large. We include their results in Table 1 and a formal definition of the problem is given as Problem 12.

3 Subspace \(\textsf{DQC_1}\) with Perfect Completeness↩︎

In this section, we introduce a variant of \(\textsf{DQC_1}\) for studying the complexity of normalized persistence. First, we recall the definition of \(\textsf{DQC_1}\). We denote the identity on \(\mathbb{C}^{2^n}\) by \(I_n\). Then the complexity class DQC\(_1\) (Deterministic Quantum Computation with one clean qubit) is defined as follows.

As proven in previous works, complexity classes with perfect completeness, such as \(\textsf{BQP}_1\) and \(\textsf{QMA}_1\), play central roles in the identification of the complexity of problems in TDA. Motivated by these established roles of perfect completeness in TDA, we define a variant of \(\textsf{DQC_1}\) that we call \(\textsf{SDQC_1}\) (\(\textsf{Subspace } \textsf{DQC_1}\)) as follows.

As can be seen from the definition, \(\textsf{SDQC_1}\) is the set of decision problems that can be solved with \(\textsf{DQC_1}\)-type computing under the additional condition that \(U_x\) accepts any state in the non-clean qubit register perfectly if it lies in a certain (unknown) subspace \(\mathcal{S}_x\).

It should be noted that the definition of \(\textsf{SDQC_1}\) depends on the choice of universal gate set \(\mathcal{G}\) because there is no known general perfect-completeness preserving reduction among different gate sets. When we want to specify the gate set, we will explicitly write \(\mathsf{SDQC}_1^\mathcal{G}\).

3.1 Power of \(\textsf{SDQC_1}\)↩︎

To characterize the power of \(\textsf{SDQC_1}\), we show that \(\textsf{SDQC_1}\) can estimate the dimension of the subspace \(\mathcal{S}_x\) normalized by the dimension of the non-clean qubit register.

By [7], \(\textsf{DQC_1}\) computation can be performed with \(O(\log n)\) clean ancilla qubits without leaving the class. Using these clean ancillas, we apply Marriott–Watrous amplification [38] to \(U_x\) to construct \(U_x'\) such that

• \(U_x'\) outputs \(1\) with probability \(1\) for any \(\ket{\psi} \in \mathcal{S}_x\),

• \(U_x'\) outputs \(1\) with probability at most \(p(n) \leq 1/\mathrm{poly}(n)\) for any \(\ket{\psi} \in \mathcal{S}_x^\perp\).

Then we observe \[\label{eq:power95sdqc} \frac{\dim\mathcal{S}_x}{2^{q(n)-1}} \leq \mathrm{Tr}\!\left( U_x' \!\left( \ket{0}\bra{0} \otimes \frac{I_{q(n)-1}}{2^{q(n)-1}} \right)\! U_x'^\dagger \!\left( \ket{1}\bra{1} \otimes I_{q(n)-1} \right) \right) \leq \frac{\dim\mathcal{S}_x}{2^{q(n)-1}} + p(n).\tag{2}\] This shows that we can estimate \(\frac{\dim\mathcal{S}_x}{2^{q(n)-1}}\) up to arbitrary \(1/\mathrm{poly}(n)\) additive error with a polynomial number of uses of \(U_x'\).

We remark that SDQC\(_1\) and DQC\(_1\) are likely incomparable, due to the imposed spectral gap condition on the acceptance operator for SDQC\(_1\). It is therefore an interesting open question to determine further relationships between the two classes.

4 Problem Definitions and Main Results↩︎

In this section, we formally introduce problems that we study and state our main results. Throughout this section, when we say that a state can be prepared by a polynomial-size quantum circuit, we mean the state is described with \(\mathrm{poly}(n)\) bits and we can efficiently compute the \(\mathrm{poly}(n)\)-size circuit description.

4.1 Low-Energy Spectral Problems↩︎

We first introduce an energy density estimation problem of local Hamiltonians within low-energy subspaces.

We first show that this problem can be solved in quantum polynomial time under a state-preparation assumption for the low-energy subspace.

A proof of this lemma is provided in Section 8. Next, we state the hardness of LENS as follows.

A proof of this theorem is provided in Section 5.2. We also consider a variant of Low-energy Normalized Subtrace for combinatorial Laplacians.

A proof of this theorem is provided in Section 6.1.

4.2 Spectral density problems↩︎

In this section, we formally introduce and show results for the spectral density problem of local Hamiltonians restricted to low-energy subspace.

This is a natural generalization of LLSD. Clearly, taking \(\eta > \left \lVert H \right \rVert\) recovers the original LLSD problem. We first show the containment in BQP under an efficient state preparation assumption.

A proof of this lemma is provided in Section 8.

It was proven that LLSD is DQC\(_1\)-hard for log-local Hamiltonians by Gyurik et al. [6]. Using Theorem 1, we are able to prove an analogous result for LESD in the case of \(O(1)\)-local Hamiltonians.

A proof of this theorem is provided in Section 5.3. We also give an analogous problem and result for combinatorial Laplacians.

A proof of this theorem is provided in Section 6.2.

4.3 Low-Energy Kernel Density↩︎

Next, we consider a variant of Low-energy Spectral Density by focusing on the low-energy density of the kernel.

We first state the containment in \(\textsf{BQP}\) under the state-preparation assumption.

A proof of this lemma is provided in Section 8.

As this problem requires the exact kernel, we show the following hardness result with the new complexity class introduced in this paper.

A proof of this theorem is provided in Section 5.5.

4.4 Normalized Quasi-Persistence↩︎

Next, we motivate and define the normalized persistence problems. We first consider the normalized persistence of the kernel of an initial Hamiltonian into the low-energy subspace of the final Hamiltonian.

Inspired by the harmonic persistence [36] in persistent homology, we define the persistence of a subspace as follows. Let \(\mathcal{S}\) be a subspace for which we consider a persistence and let \(\mathcal{P}\) be a projector. Then, we define \(\mathrm{Im}\mathcal{P}|_{\mathcal{S}}\) to be the persistence of \(\mathcal{S}\) with respect to \(\mathcal{P}\). Then, we define the quantity that we call a normalized persistence as \[\frac{\dim \mathrm{Im}\mathcal{P}|_{\mathcal{S}}}{\dim \mathcal{S}},\] that is the portion of the dimension of the image of the projector \(\mathcal{P}\) compared to its original dimension. The normalized persistence problem is to estimate this quantity up to inverse-polynomial additive error. Note that this is a generalization of the normalized persistence quantity for Betti numbers we defined in equation 1 . This can be seen by taking \(\mathcal{S} = \ker(\Delta_{1,d})\) and \(\mathcal{P}\) the orthogonal projector onto \(\ker(\Delta_{2,d})\), for combinatorial Laplacians \(\Delta_{1,d},\Delta_{2,d}\). We define this problem as Normalized Harmonic Persistence later as Problem 9.

We first formalize a quasi version of the problem for two PSD local Hamiltonians \(H_1, H_2\) where \(H_2-H_1\) is also positive semidefinite, and we choose \(\mathcal{S}= \ker H_1\) and \(\mathcal{P}= \mathcal{P}_{\leq b} (H_2).\)

Normalized quasi-persistence may not be efficiently solved even if we have access to the uniform mixture for \(\ker H_1\). In order to prove containment for this problem we introduce the following additional condition.

We use “large” in the sense that it is lower-bounded by \(1/\mathrm{poly}(n)\). Although we focus on this \(1/\mathrm{poly}(n)\)-overlap condition, one may also consider constant-overlap or \(1/\exp(n)\)-overlap conditions for further specifications of the complexity.

This allows us to state the following containment result.

A proof of this lemma is provided in Section 8.

The containment result above shows that normalized quasi-persistence can be estimated efficiently when the relevant projected subspace has inverse-polynomial overlap and the uniform mixture over \(\ker H_1\) is efficiently preparable. We now turn to the complementary lower bound. The next theorem shows that the dimension-normalized persistence quantity is \(\textsf{DQC_1}\)-hard, and remains so in the regime where it is well approximated by the corresponding trace-overlap quantity \[\frac{\mathrm{Tr}[\mathcal{P}_{2,b}\Pi_{\ker H_1}\mathcal{P}_{2,b}]}{\dim\ker H_1}.\] Thus the hardness is not merely an artifact of small singular values in the map \(\mathcal{P}_{2,b}|_{\ker H_1}\).

A proof of this theorem is provided in Section 5.4.

4.5 Exact Normalized Persistence↩︎

The exact version of the normalized persistence problem asks how much of \(\ker H_1\) persists into \(\ker H_2\), rather than into a low-energy subspace of \(H_2\). We state this formally below.

A proof of this lemma is provided in Section 8.

A proof of this theorem is provided in Section 5.6.

4.6 Normalized Quasi-Harmonic Persistence↩︎

We now turn to the TDA setting. Consider an inclusion of clique complexes \(X_1 \hookrightarrow X_2\) induced by \(G_1 \subseteq G_2\), with \(d\)-dimensional combinatorial Laplacians \(\Delta_{1,d}\) and \(\Delta_{2,d}\). The following problem is a TDA specialization of Normalized Quasi-Persistence, where the Hamiltonian is replaced by the combinatorial Laplacian and the kernel by the harmonic subspace.

In this problem, we specify \(G_1, G_2\) to have the same vertex set. This is a common situation in TDA instances, for example with a Vietoris-Rips filtration (Section 2). Now we state the containment result.

A proof of this lemma is provided in Section 8. We also state the corresponding hardness theorem.

A proof of this theorem is provided in Section 6.2.

4.7 Normalized Harmonic Persistence in TDA↩︎

The non-quasi version estimates the normalized persistent Betti number \(\beta_d^{1,2}/\beta_d^1\), i.e., the fraction of \(d\)-dimensional holes in \(X_1\) that persist into \(X_2\).

A proof of this lemma is provided in Section 8.

Unlike the other persistence problems considered in this paper, we do not establish \(\mathsf{SDQC}_1\)-hardness of \(\textsf{Normalized Harmonic Persistence}\) directly. Instead, we record it as a conjecture.

In Section 7, we outline a condition that would imply the above conjecture.

5 Hardness for Local-Hamiltonian Subspace Problems↩︎

5.1 Preparing Uniform Mixtures of History States↩︎

For the circuit-to-Hamiltonian construction with \(\textsf{DQC_1}\)-type computation, a key subspace is the subspace spanned by the history states with all possible initial states on the mixed register. We show an efficient state preparation for that state.

5.2 \(\textsf{DQC_1}\)-hardness of LENS↩︎

To prove this result we need the following preliminary results from perturbation theory:

This allows us to state the following result of [39], [40]

5.3 \(\textsf{DQC_1}\)-hardness of LESD↩︎

Our proof of this is similar to the DQC\(_1\)-hardness result of LLSD found in [6]. They show that the normalized subtrace of a Hamiltonian can be estimated using polynomially many queries to an oracle for LLSD. The DQC\(_1\)-hardness then follows from Brandao’s proof that normalized subtrace estimation is DQC\(_1\)-hard for log-local Hamiltonians. Following the same lines, we show that any instance of LENS can be solved using polynomially many queries to an oracle for LESD.

5.4 Hardness of Normalized Quasi-Persistence↩︎

Now we prove Theorem 6.

5.5 \(\textsf{SDQC_1}\)-hardness of \(\mathsf{LEKD}\)↩︎

The proof is a direct reduction from \(\mathsf{SDQC}_1\), using the same circuit-to-Hamiltonian construction as the \(\mathsf{DQC}_1\)-hardness proof of \(\textsf{LENS}\) (Section 5.2). The key difference is that perfect completeness of the \(\mathsf{SDQC}_1\) circuit yields an exact kernel structure, whereas the LENS proof relies on the approximate spectrum. We show that a single query to \(\textsf{LEKD}\) suffices to decide the \(\mathsf{SDQC}_1\) instance.

5.6 Hardness of Exact Normalized Persistence↩︎

The proof is analogous to the \(\mathsf{DQC}_1\)-hardness proof of \(\textsf{Normalized Quasi-Persistence}\) (Section 5.4), with two replacements:

• The underlying spectral problem changes from \(\textsf{LESD}\) to \(\textsf{LEKD}\) (Section 5.5).

• The \(b=0\) case makes \(\ker H_2 \subseteq \ker H_1\) hold exactly, so the \(\textsf{Normalized Persistence}\) quantity collapses to \(\dim\ker H_2/\dim\ker H_1\) without approximation.

6 Hardness for TDA Problems↩︎

Our proof strategy for proving \(\textsf{DQC_1}\)-hardness of the analogous problems in TDA is to first show that LENS for TDA is DQC\(_1\)-hard. From there we can reduce to LESD for TDA and this then allows a reduction to Normalized Quasi-Harmonic Persistence. This allows us to conclude that all three problems are DQC\(_1\)-hard. The first of these reductions will be the most technically involved and the others will follow naturally.

6.1 DQC\(_1\)-hardness of LENS for TDA↩︎

In order to prove that LENS for TDA is DQC\(_1\)-hard we need to establish some notions related to Hamiltonian simulation. The idea here is to simulate a given Hamiltonian by encoding it in the low-energy subspace of a Hamiltonian acting on a larger space. We first state the following lemma.

The encoding \(\mathcal{F}\) will in general be a composition of encodings in the simulation style of Cubitt et al. [28] and Bravyi-Hastings [42]. This composition is sufficient to approximate the spectrum of \(H\) up to a potential identity shift. In order to prove this lemma we first define both notions of simulation.

We note that the above notion of simulation means that the eigenvalues of \(H\) will be approximated by the eigenvalues of \(H'_{\leq\Delta}\), although the corresponding eigenvalues in \(H'\) may occur with a higher multiplicity. Specifically, since \(H\) and \(\bar{H}\) have the same eigenvalues, the overall encoded Hamiltonian will have eigenvalues that occur with an increased factor of \(p+q\), where \(p=\mathrm{rank}(P)\) and \(q = \mathrm{rank}(Q)\). Of the simulations that we require, the only encoding for which this occurs is the complex to real encoding. In this case the multiplicities of all simulated eigenvalues are doubled, as the encoding uses a single copy of \(H\) and \(\bar{H}\). However as the quantities we study are normalized, doubling the multiplicities of the eigenvalues leaves them unchanged. We now consider the notion of simulation due to Bravyi and Hastings.

We remark that both of these definitions use the standard convention where \(V\) or \(\mathcal{E}\) denote the raw explicit encoding and \(\tilde{V}\),\(\tilde{\mathcal{E}}\) denote the dressed encoding that maps exactly to the required low energy subspace. It is common that the raw encoding will encode qubits in the groundspace of an unperturbed Hamiltonian. The simulator Hamiltonian will then be a perturbation of this with a low-energy subspace, which the dressed encodings map to.

These two definitions of simulation differ in the requirements of the encoding. The CMP definition allows for a more general form of encoding so that complex Hamiltonians can be simulated by real ones. However, this definition also requires \(V\) to be a product of local isometries, whereas the BH definition does not. For our purposes, the simulator Hamiltonian need only approximate the spectrum of the target Hamiltonian below some threshold and both definitions suffice for this.

It is shown by Cubitt et al. [28], using results from [43], that an arbitrary \(k\)-local Hamiltonian can be simulated by a Hamiltonian of the form \[H_{sim} = \sum_{i,j} \mu_{i,j}(\alpha X_iX_j + \beta Y_iY_j +\gamma Z_iZ_j)\] with \(\mu_{i,j}>0\) and \(\alpha+\beta, \alpha+\gamma, \beta+\gamma >0\). That is, Hamiltonians of the form above are universal. The simulation here is that of CMP in definition 5. It is clear from taking \(\alpha=\gamma=1\) and \(\beta=0\) that an XX+ZZ Hamiltonian can also simulate an arbitrary \(k\)-local Hamiltonian. Rayudu [17] showed how one can simulate (in the sense of BH) an \(XX+ZZ\) Hamiltonian using the combinatorial Laplacian of a weighted clique complex. This result, together with the above, implies that combinatorial Laplacians can approximate the spectrum of an arbitrary \(k\)-local Hamiltonian. However it is important to note that the encodings needed to achieve this will be a combination of those specified by [28] and [42]. Thus the simulation itself does not completely fall under either definition. If the target Hamiltonian is real, then the encodings necessary will fall under the BH definition and so it is reasonable to say that these Hamiltonians can be simulated by a combinatorial Laplacian in the sense of definition 6. But we do not quite get full universality for complex Hamiltonians in the sense of [28].

The proof of lemma 10 follows immediately from the simulations outlined in [28] and the construction in [17]. We give an overview of Rayudu’s construction in Appendix 9 and outline how the result can be combined with the CMP simulations below.

This result allows us to prove DQC\(_1\)-hardness of LENS for TDA. We proceed by using the above lemma to show that the output of LENS for TDA can be made sufficiently close to the output of LENS for the DQC\(_1\) Hamiltonian, such that it can decide an arbitrary DQC\(_1\) instance.

6.2 DQC\(_1\)-hardness of LESD for TDA and NQHP↩︎

The remaining two hardness proofs are much simpler. In fact, the proof of DQC\(_1\)-hardness for LESD for TDA is completely analogous to the reduction from LENS to LESD in the case of local Hamiltonians.

It remains to show that Normalized Quasi-Harmonic Persistence (NQHP) is DQC\(_1\)-hard. We do this by reducing from LESD for TDA, which is DQC\(_1\)-hard by the above.

7 Toward \(\mathsf{SDQC}_1\)-Hardness of NHP↩︎

In this section, we discuss a route toward proving Conjecture 1. First, we explain why the TDA analogue of Normalized Persistence requires a stronger ingredient than the simulation tools used in the proof of Normalized Quasi-Harmonic Persistence. The quasi-harmonic result in Section 6.2 relies on approximate low-energy simulation based on the Rayudu construction, combined with universal Hamiltonian simulation. By contrast, NHP reads the exact harmonic space. A perturbative simulation that moves zero eigenvalues by inverse-polynomial error can preserve all low-energy density estimates used for NQHP, while completely losing the Betti number and hence the persistent Betti number.

The closest existing exact-kernel primitive is the King–Kohler construction for gapped clique homology [15]. This construction performs a reduction from a \(\mathsf{QMA}_1\) verification problem, formulated through a quantum satisfiability instance, to clique homology, while preserving the zero-energy space of the local Hamiltonian and approximately preserving the promise gap for the combinatorial Laplacian. More concretely, they reduce from local Hamiltonians composed of projectors onto integer states, where integer states refer to states with integer amplitudes in the computational basis up to normalization, and construct a clique complex by (1) constructing a qubit graph with \(2^n\) holes and (2) adding gadgets for each local projector with small vertex weights. However, the King–Kohler construction does not give the ingredient needed here as a black box. Our reduction from \(\mathsf{SDQC}_1\) does not merely ask whether a kernel is nonempty. It asks for the dimension of a whole perfectly accepted subspace, normalized by the dimension of the valid history subspace. It also asks that this quotient be reproduced through a filtration. Moreover, the local-Hamiltonian proof in this work uses a hierarchy of penalty scales: the output term is treated as a smaller perturbation relative to the clock, propagation, and input terms. To transfer the proof to clique complexes, one would need a coefficient-sensitive refinement of the King–Kohler construction that represents this relative output weight while preserving the exact kernel and an inverse-polynomial gap.

It is useful to separate the missing proof into an exact-kernel analogue of the route used for NQHP. The natural intermediate problem is a TDA version of LEKD: given a weighted clique complex and a dimension \(d\), estimate the fraction of the relevant low-energy space that is exactly harmonic, with a promise gap above zero. For the \(\mathsf{SDQC}_1\) history Hamiltonian, the corresponding target construction would have two stages. A natural candidate for this step is the circuit-to-Hamiltonian construction of [44], which is better suited to the clique-complex realization. We omit the details of this construction here. First, one would realize the output-free history Hamiltonian \[H_1 := J_{in}H_{in} +J_{prop}H_{prop} +J_{clock}H_{clock}\] by a weighted combinatorial Laplacian \(\Delta_{1,d}\) in such a way that \(\ker\Delta_{1,d}\) has the same dimension as \(\ker H_1\), and the spectral gap above this kernel is preserved up to inverse-polynomial accuracy.

Second, one would add an output gadget corresponding to \[H_2(\lambda) := H_1 + \lambda H_{out},\] where \(\lambda\) is inverse-polynomial but smaller than the scale of the gadgets enforcing the output-free history space. One would assign inverse-polynomially smaller vertex weights to the output gadget than to the gadgets implementing \(H_1\). With this comparatively small output weight, the desired property of the Laplacian \(\Delta_{2,d}\) is \[\dim\ker\Delta_{2,d}=\dim\ker H_2(\lambda),\] with an inverse-polynomial gap above the harmonic space. Establishing this coefficient-sensitive construction along with the approximate preservation of the spectral gap appears to require new control beyond the present King–Kohler analysis.

Finally, NHP needs more than a kernel count for a single simplicial complex. The weighted complexes must form a filtration \(X_1\hookrightarrow X_2\), and the encodings of the kernels must be compatible with this inclusion. Ideally, the filtration should use a common encoding of the valid history space: the chain-level inclusion \(C_d(X_1)\hookrightarrow C_d(X_2)\) should send each encoded history state in \(X_1\) to the same encoded history state in \(X_2\). Under this identification, projecting onto the harmonic space of \(X_2\) should correspond exactly to projecting \(\ker H_1\) onto \(\ker H_2(\lambda)\). Then \[\beta_d(X_1)=\dim\ker H_1, \qquad \beta_d^{1,2}= \dim\mathrm{Im}\,\Pi_{\ker H_2(\lambda)}\big|_{\ker H_1},\] and an oracle for NHP would decide the underlying \(\mathsf{SDQC}_1\) instance in the same way as the local-Hamiltonian Normalized Persistence oracle.

We isolate this missing ingredient as the following conjecture and then show that this conjecture implies Conjecture 1.

This conjecture is deliberately narrower than a full universal simulation theorem. It only asks for the class of frustration-free history Hamiltonians that arise in the \(\mathsf{SDQC}_1\) reduction, and for the preservation of the exact kernel structure rather than the full spectrum. At the same time, it asks for properties that approximate Hamiltonian simulation does not provide: exact kernel multiplicity and compatibility with a filtration. A stronger and independently interesting direction would be to prove a general kernel-preserving universality theorem for weighted clique Laplacians. Such a theorem would likely imply the realization primitive above, but the present conjecture isolates the more specific structure needed for NHP. It would also be interesting to explore kernel-preserving universality for local Hamiltonians.

8 Containment of Low-Energy and Normalized Persistence Problems↩︎

In this section, we provide proofs of containments for the low-energy and normalized persistence problems.

8.1 Containment for Low-Energy Problems↩︎

8.1.0.1 Containment of LENS (Lemma 1)

8.1.0.2 Containment of LESD (Lemma 2)

8.1.0.3 Containment of LEKD (Lemma 3)

8.2 Containment for Normalized Persistence Problems↩︎

8.2.0.1 Containment of Normalized Quasi-Persistence (Lemma 4)

The remaining containment proofs are similar to the above proof.

8.2.0.2 Containment of Normalized Persistence (Lemma 5)

8.2.0.3 Containment of Normalized Quasi-Harmonic Persistence (Lemma 6)

8.2.0.4 Containment of Normalized Harmonic Persistence (Lemma 7)

Acknowledgements↩︎

DL acknowledges funding from UK EPSRC (EP/W032643/1 and EP/Z53318X/1). MSK acknowledges funding from the UK EPSRC through EP/Z53318X/1 and EP/W032643/1, the KIST through Open Innovation fund and the National Research Foundation of Korea grant funded by the Korean government (MSIT) (No. RS-2024-00413957). RH was supported by JST PRESTO Grant Number JPMJPR23F9 and JST ASPIRE Grant Number JPMJAP26A4, Japan.

Author Contributions↩︎

DL and RH conceived the idea and proved the results. RB, MSK acted as supervisors for DL and participated in discussions. All four authors participated in writing the final draft.

9 Combinatorial-Laplacian Simulation↩︎

Here we outline the construction used in [17] to show that estimating the minimum eigenvalue of a combinatorial Laplacian is QMA-hard. This construction uses the representation of the combinatorial Laplacian via the fermion hardcore model. That is, a model where no fermions are allowed to occupy adjacent sites. Precisely, consider a weighted graph \(G=(V,E)\) with weight \(u_i\) on vertex \(i\). Then the fermion hardcore model on \(G\) is given by the Hamiltonian: \[H_G = \sum_{(i,j)\in E}u_iu_j P_ia_i^\dagger a_j P_j + \sum_{i\in V}u_i^2P_i\] where \(a_i^\dagger\) and \(a_i\) are fermionic creation and annihilation operators respectively. The \(P_i\) are projectors that enforce the hardcore constraints of the graph and are given by: \[P_i = \prod_{j| (i,j)\in E}({I}-a_j^\dagger a_j).\] We see that each \(P_i\) projects onto the subspace where there are no fermions adjacent to vertex \(i\). It can be shown that \(H_G\) is a direct sum of the combinatorial Laplacians corresponding to the independence complex of \(G\). In particular the \(k\)’th combinatorial Laplacian of \(\bar{G}\) is given by the restriction of \(H_G\) to the subspace with \((k+1)\) fermions. Rayudu [17] used the fermion hardcore model to show that a combinatorial Laplacian can simulate an \(XX+ZZ\) Hamiltonian. Moreover, since these are universal in the sense of [28] it follows that weighted combinatorial Laplacians are also capable of universal simulation in some sense. First suppose that we want to simulate a Hamiltonian consisting of one term, \(\frac{3}{8}\mu_{i,j}(X_iX_j +Z_iZ_j)\), with \(\mu_{i,j}>0\). Hence we want to simulate a 2 qubit space \(\mathcal{H}_{target}= (\mathbb{C}^2)^{\otimes2}\). Then to encode each qubit we use fermionic states that obey the hardcore restrictions on a triangle, as shown in Figure 3. Note that such states must consist of at most one fermion.

Then consider the fermion hardcore model on this triangle (with coefficients 1 for now) \[H_{0,i} = P_{i_1}a_{i_1}^\dagger a_{i_2}P_{i_2} + P_{i_2}a_{i_2}^\dagger a_{i_1}P_{i_1} + P_{i_1}a_{i_1}^\dagger a_{i_3}P_{i_3} + P_{i_3}a_{i_3}^\dagger a_{i_1}P_{i_1}+ P_{i_2}a_{i_2}^\dagger a_{i_3}P_{i_3} + P_{i_3}a_{i_3}^\dagger a_{i_2}P_{i_2} + P_{i_1} + P_{i_2} + P_{i_3}\] It is clear that the subspace of the Fock space satisfying the hardcore constraints is 4 dimensional, as we cannot have more than one fermion on the graph. One can then show that \(H_{0,i}\) has two \(0\)-energy ground states, given by \[\begin{align} \ket{0}&=S_0\ket{vac}\\ \ket{1}&=S_1\ket{vac} \end{align}\] where \[\begin{align} S_0 &= \frac{1}{2\sqrt{3}}[(1-\sqrt{3})a_3^\dagger - 2a_1^\dagger + (1+\sqrt{3})a_2^\dagger]\\ S_1 &= \frac{1}{2\sqrt{3}}[(1+\sqrt{3})a_3^\dagger -2a_1^\dagger +(1-\sqrt{3})a_2^\dagger] \end{align}\] A 2 dimensional ground space might seem strange, as the complement of this graph has 3 connected components, and so we should expect \(\beta_0=3\). However, the fermion hardcore model instead captures the ‘reduced homology’ of the independence complex. In this convention we consider the empty set (or vacuum in the fermion picture) to be a \((-1)\)-simplex. This means that the \(0\)’th Betti number will now actually be equal to the number of connected components minus one. Note that this convention leaves all other Betti numbers unchanged.

We will use the ground states \(\ket{0},\ket{1}\) to encode qubit \(i\). To encode multiple qubits we use several copies of the same triangle, and the \(XX+ZZ\) interactions between them are simulated using mediator modes \(x,y,z\), see Figure 4.

Now consider the Hamiltonian \[H_0 = H_{0,i} + H_{0,j}\] Note that \(H_0\) is just the fermion hardcore model on two disjoint copies of the qubit triangle. It follows that, in the two fermion sector, \(H_0\) has four ground states \[\begin{align} \ket{00} &= S_{0,i}S_{0,j}\ket{vac}\\ \ket{01} &= S_{0,i}S_{1,j}\ket{vac}\\ \ket{10} &= S_{1,i}S_{0,j}\ket{vac}\\ \ket{11} &= S_{1,i}S_{1,j}\ket{vac} \end{align}\] where \(S_{0,i}\) and \(S_{1,i}\) are just the previous \(S_0\) and \(S_1\) operators with all creation operators acting on the \(i\)-nodes. \(S_{0,j}\) and \(S_{1,j}\) are defined analogously. We can then encode the 2 qubit space \(\mathcal{H}_{target} = (\mathbb{C}^2)^{\otimes 2}\) in these ground states. Precisely, we will take the simulator Hilbert space to be \(\mathcal{H}_{sim} = \Pi_{hc}\mathcal{F}^{(2)}\), where \(\mathcal{F}^{(2)}\) denotes the 2 fermion sector of the full fermionic Fock space on the 9 sites, and \(\Pi_{hc}\) is the projector onto states that obey the hardcore constraints corresponding to the graph in Figure 4. That is, \(\mathcal{H}_{sim}\) is the space spanned by states of 2 fermions on the graph in Figure 4 such that no two fermions are adjacent. Importantly, \(\mathcal{H}_{sim}\) does contain states with fermions on the mediators. This means, that for the 2 qubit and 1 interaction graph, \(\dim(\mathcal{H}_{sim}) = 24\). Despite this, the groundspace of \(H_0\) is still 4 dimensional which we use to encode the 2 qubit Hilbert space. The isometry \(\mathcal{E}:\mathcal{H}_{target}\to \mathcal{H}_{sim}\) is then simply the mapping from the 4 computational basis states to the 4 fermionic states above. The goal now is to simulate an \(XX+ZZ\) interaction through a perturbation to \(H_0\) that acts on the mediator modes. This is achieved with the following result of Bravyi and Hastings. Here we assume \(H_0\) has smallest eigenvalue 0 and next smallest eigenvalue greater than or equal to 1. Note that both of these conditions hold for the \(H_0\) defined above. We use \(\Pi_-\) and \(\Pi_+\) to denote the projectors onto the ground space of \(H_0\) and its orthogonal complement, respectively. We also use the standard shorthand \(O_{\pm\pm}\) to denote \(\Pi_{\pm}O\Pi_{\pm}\) for an operator \(O\). With this in mind, the result is as follows:

The perturbations considered by Rayudu are given by \(V_{main} = \sqrt{\mu_{i,j}}(V_x + V_y + V_z)\) and \(V_{extra} = \mu_{i,j}(P_x + P_y + P_z)\), where \[\begin{align} V_x &= P_xa_x^\dagger a_{i_2}P_{i_2} + P_{i_2}a_{i_2}^\dagger a_x P_x + P_xa_x^\dagger a_{j_2}P_{j_2}+ P_{j_2}a_{j_2}^\dagger a_x P_x\tag{9}\\ V_y &= P_ya_y^\dagger a_{i_3}P_{i_3} + P_{i_3}a_{i_3}^\dagger a_y P_y + P_ya_y^\dagger a_{j_3}P_{j_3}+ P_{j_3}a_{j_3}^\dagger a_y P_y\\ V_z &= P_za_z^\dagger a_{i_1}P_{i_1} + P_{i_1}a_{i_1}^\dagger a_z P_z + P_za_z^\dagger a_{j_1}P_{j_1}+ P_{j_1}a_{j_1}^\dagger a_z P_z. \tag{10} \end{align}\] Aiming to apply the theorem above, we note that \((V_{main})_{--} =0\) since all four ground states of \(H_0\) do not contain a mediator fermion. Then the effect of the perturbation \(V_{main}\) can be computed as \[-(V_{main})_{-+}H_0^{-1}(V_{main})_{+-}= -\frac{7}{12}I + \frac{5}{24}(X_iX_j + Z_iZ_j)\] and similarly the effect due to \(V_{extra}\) is given by \[(V_{extra})_{--} = \frac{4}{3}I + \frac{1}{6}(X_iX_j + Z_iZ_j).\] Note that \(V_{extra}\) is not actually block diagonal with respect to \(\Pi_{-}\) and \(\Pi_{+}\) however this condition in theorem 9 can be relaxed to \((V_{main})_{-+}H_0^{-1}(V_{extra})_{+-}=0\). This is because the block diagonal condition is just to kill three unwanted contributions in the effective Hamiltonian, but the above condition ensures two of these are zero and the third is \(O(\Delta^{-1})\) which can be absorbed into the error. One can then check that this latter condition does hold for our choice of \(V_{extra}\). It remains to upper bound \(\Lambda\), the bound on the operator norms of \(V_{main}\) and \(V_{extra}\). We note that both perturbations consist of projectors, and terms of the form \(Pa^\dagger_pa_qP + Pa_q^\dagger a_pP\), both of which have norm at most one. Hence we have: \[\begin{align} \left \lVert V_{main} \right \rVert &\leq 6\sqrt{\mu_{i,j}}\\ \left \lVert V_{extra} \right \rVert &\leq 3\mu_{i,j} \end{align}\] Hence we can take \(\Lambda = \max\{6\sqrt{\mu_{i,j}}, 3\mu_{i,j}\}\). Putting all of this together we can simulate \[\mu_{i,j}(\frac{3}{4}I + \frac{3}{8}(X_iX_j+Z_iZ_j))\] on the encoded qubits \(i\) and \(j\) with error \((\eta,\epsilon)\) using the simulator Hamiltonian \[H_{sim} = \Delta H_0 + \Delta^{1/2}V_{main}+ V_{extra}\] where we take \(\Delta \geq O(\epsilon^{-2}\Lambda^6 + \eta^{-2}\Lambda^2)\). We note that the target Hamiltonian contains an identity shift from the actual desired Hamiltonian, however since this shift is known the actual spectrum of the desired Hamiltonian can be obtained by subtracting this constant. Finally we see that \(H_{sim}\) is the fermion hardcore model on the graph in Figure 4, with vertex weighting \(u_{i_k}=u_{j_k}=\sqrt{\Delta}\) for \(k=1,2,3\) and \(u_x=u_y=u_z=\sqrt{\mu_{i,j}}\). Since \(\mathcal{H}_{sim}\) is the subspace spanned by two independent fermions, it follows that \(H_{sim}\) is equivalent to \(\Delta_1(\text{ind}(G))\), where \(\text{ind}(G)\) denotes the independence complex of the graph in Figure 4. That is, the first combinatorial Laplacian of the complement graph \(\bar{G}\).

It remains to show how this construction generalises to a full \(n\)-qubit Hamiltonian with XX+ZZ interactions. Let \([n]=\{1,2,\ldots,n\}\) denote the qubits the Hamiltonian acts on, where we have fixed some ordering from 1 to \(n\). Then we denote the set of interactions by \(\mathcal{I}\), where \[\mathcal{I} = \{(i,j)\in [n]^2: i<j \text{and} X_iX_j+Z_iZ_j \text{occurs in}H_{target}\}.\] Motivated by the identity shift in the two qubit case we then take \[H_{target}=CI + \sum_{(i,j)\in \mathcal{I}}\frac{3}{8}\mu_{i,j}(X_iX_j+Z_iZ_j)\] where \(\mu_{i,j} = \mathrm{poly}(n)>0\) and \(C\) is a constant to be determined later. Let \(k = |\mathcal{I}|\leq \frac{n(n-1)}{2}\) also. We will simulate \(H_{target}\) using the fermion hardcore model on a graph. Again we encode each qubit \(i\) using a triangle on the nodes \(i_1,i_2,i_3\) and for each interaction between qubits \(i\) and \(j\) we introduce 3 mediator nodes \(x_{i,j}\), \(y_{i,j}\), \(z_{i,j}\). We do this such that each interaction gives a subgraph identical to the graph in Figure 4. If we call the overall graph constructed in this way \(G\), then it is clear that \(G\) has \(3n+3k\) nodes. We take \(\mathcal{H}_{sim}=\Pi_{hc}\mathcal{F}^{(n)}\), the space spanned by states with \(n\) fermions on \(G\) that satisfy the hardcore constraints. Again, the dimension of \(\mathcal{H}_{sim}\) will be the number of independent sets on \(G\) of size \(n\). Then if we take \[H_0 = \sum_{i=1}^nH_{0,i}\] it is clear that \(H_0\) has a ground space of dimension \(2^n\), spanned by states of the form: \[\begin{align} \ket{00\ldots0} &=S_{1,0}S_{2,0}\cdots S_{n,0}\ket{vac}\\ \ket{10\ldots0}&=S_{1,1}S_{2,0}\cdots S_{n,0}\ket{vac}\\ \ket{01\ldots0}&=S_{1,0}S_{2,1}\cdots S_{n,0}\ket{vac}\\ \ldots \notag \end{align}\] where \(S_{i,0}\) and \(S_{i,1}\) denote the operators \(S_0\) and \(S_1\) with creation operators on the triangle corresponding to \(i\). This ground space is the encoding of the \(n\)-qubit Hilbert space that \(H_{target}\) acts on. Then the perturbations we consider are given by \[\begin{align} V_{main} &= \sum_{(i,j)\in \mathcal{I}}\sqrt{\mu_{i,j}} V_{main}^{(i,j)}\\ V_{extra} &= \sum_{(i,j)\in \mathcal{I}}\mu_{i,j}V^{(i,j)}_{extra} \end{align}\] where \(V_{main}^{(i,j)}=V_{x_{i,j}}+V_{y_{i,j}}+V_{z_{i,j}}\) with each term as in equations (9 10 ) and \(V_{extra}^{(i,j)} = P_{x_{i,j}}+P_{y_{i,j}}+P_{z_{i,j}}\). That is, a sum over all interactions of the same perturbations that we had in the two qubit case. We can then upper bound the norms of the perturbations as \[\begin{align} \left \lVert V_{main} \right \rVert &\leq 6\sum_{(i,j)\in\mathcal{I}}\sqrt{\mu_{i,j}}\\ \left \lVert V_{extra} \right \rVert&\leq 3\sum_{(i,j)\in \mathcal{I}}\mu_{i,j} \end{align}\] and so we can take \[\Lambda = \max\left\{6\sum_{(i,j)\in\mathcal{I}}\sqrt{\mu_{i,j}}, 3\sum_{(i,j)\in\mathcal{I}}\mu_{i,j}\right\}=\mathrm{poly}(n).\] Then one can show with the same computations as before that \[H_{sim} = \Delta H_0 + \Delta^{1/2}V_{main}+ V_{extra}\] is a \((\eta,\epsilon)\) simulation of \(H_{target}\) for \(\Delta \geq O(\epsilon^{-2}\Lambda^6 + \eta^{-2}\Lambda^2)\), by theorem 9. Note that after performing the same computations as the two qubit case, one can see that the identity shift is given by \[C = \frac{3}{4}\sum_{(i,j)\in \mathcal{I}}\mu_{i,j}\] As \(H_{sim}\) acts on the space of \(n\) fermions that satisfy the hardcore constraints, it follows that it is equivalent to the \(\Delta_{n-1}(\text{ind}(G))\), with suitable vertex weighting as in the 2-qubit case. We conclude that an \(n\)-qubit \(XX+ZZ\) Hamiltonian can be simulated (in the sense of Bravyi and Hastings) by the \((n-1)\)’th combinatorial Laplacian of a \(3n+3k\) node graph, up to an efficiently computable identity shift.

10 Formal Statements of Related Problems↩︎

Here we outline some of the related problems that fit into the complexity landscape we discuss. These problems, and their relevant complexities, also appear in Table 1.

First we outline the following problem:

The following complexity theoretic result was shown in [26].

A related problem was studied in [6]. For a positive semidefinite matrix \(H\in \mathbb{C}^{2^n\times 2^n}\) and \(a\leq b \in \mathbb{R}_{\geq 0}\), we define low-lying spectral density by \[D_H(a,b):=\frac{1}{2^n}\sum_{k:a\leq \lambda_k\leq b} 1,\] where \(\lambda_0 \leq \cdots \leq \lambda_{2^n-1}\) are the eigenvalues of \(H\)¹. Then, the Low-lying spectral density estimation (LLSD) problem is defined as follows:

The following result is known on this problem.

The two problems above are the inspiration for our problems LENS and LESD. Our results generalise these hardness results such that they still hold when the normalization is taken to be the dimension of a low-energy subspace.

Next, we move to the TDA literature and consider the following problem:

This problem was shown to be \(\mathsf{BQP}_1\)-hard and contained in \(\mathsf{BQP}\). The following two promise problems for local Hamiltonians are introduced in [19] as underlying quantum primitives for Harmonic Persistence. First, we introduce the Kernel Overlap problem.

Similarly to the Harmonic persistence, this problem was shown to be \(\mathsf{BQP}_1\)-hard and contained in \(\mathsf{BQP}\) in [19]. Next, we introduce a low-energy variant of this problem.

This problem is known to be \(\mathsf{BQP}\)-complete [19].

References↩︎

---

1. In [6], \(N_H(a,b)\) was used for this quantity. We instead denote this by \(D_H(a,b)\) and use \(N_H(a,b)\) for an unnormalized quantity.↩︎