Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$

• URL: http://arxiv.org/abs/2311.17234v2
• Date: Sun, 06 Oct 2024 23:00:19 GMT
• Title: Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$
• Authors: Robbie King, Tamara Kohler,
• Abstract summary: We study the complexity of a classic problem in computational topology, the homology problem. We find that the complexity is characterized by quantum complexity classes. Our results can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
• Score: 0.0
• License:
• Abstract: We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space $X$ and an integer $k$, decide if $X$ contains a $k$-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics. We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every $k+1$-clique in the graph to be a $k$-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is $\text{QMA}_1$-hard and contained in $\text{QMA}$. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as \emph{spectral sequences}. In particular, we exploit a connection between spectral sequences and Hodge theory. Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work. Our result provides some suggestion that the quantum TDA algorithm \emph{cannot} be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.

Related papers

• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks. We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube. We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Quantum Algorithm for Estimating Betti Numbers Using a Cohomology Approach [2.2000560351723504]
  Calculating Betti numbers classically is a daunting task due to the massive volume of data. We consider the dual' approach, which is inspired by Hodge theory and de Rham cohomology. Our algorithm can calculate its $r$-th Betti number $beta_r$ up to some multiplicative error.
  arXiv  Detail & Related papers  (2023-09-19T17:44:53Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work [10.43571631715192]
  We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM) Our main technical contribution is a framework that simplifies the use of the parallel-query generalization of the compressed oracle technique for proving query complexity results. As a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks.
  arXiv  Detail & Related papers  (2020-10-22T12:44:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.