Clique Homology is QMA1-hard

• URL: http://arxiv.org/abs/2209.11793v1
• Date: Fri, 23 Sep 2022 18:14:16 GMT
• Title: Clique Homology is QMA1-hard
• Authors: Marcos Crichigno and Tamara Kohler
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch 20 years ago. We show that this decision problem is QMA1-hard. Moreover, we show that a version of the problem satisfying a suitable promise and certain constraints is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we are able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra. We discuss potential implications for the problem of quantum advantage in topological data analysis.

Related papers

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We study the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework. We focus on complexity classes p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states. We apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• Quantum computing and persistence in topological data analysis [41.16650228588075]
  Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We show that a computational problem closely related to a core task in TDA is $mathsfBQP_1$-hard and contained in $mathsfBQP$. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.
  arXiv  Detail & Related papers  (2024-10-28T17:54:43Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  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.
  arXiv  Detail & Related papers  (2023-11-28T21:15:30Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• 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)
• Quantum Parameterized Complexity [1.01129133945787]
  We introduce the quantum analogues of a range of parameterized complexity classes. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems.
  arXiv  Detail & Related papers  (2022-03-15T15:34:38Z)
• Simultaneous Stoquasticity [0.0]
  Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation.
  arXiv  Detail & Related papers  (2022-02-17T19:08:30Z)
• 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-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)
• Quantum computation of thermal averages in the presence of a sign problem [45.82374977939355]
  We illustrate the application of Quantum Computing techniques to the investigation of the thermodynamical properties of a simple system. We show how quantum algorithms completely solve the problem, and discuss how this can apply to more complex systems of physical interest.
  arXiv  Detail & Related papers  (2020-01-15T14:01:11Z)

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.