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
- Promise 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 result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
arXiv Detail & Related papers (2023-11-28T21:15:30Z) - On the quantum time complexity of divide and conquer [42.7410400783548]
We study the time complexity of quantum divide and conquer algorithms for classical problems.
We apply these theorems to an array of problems involving strings, integers, and geometric objects.
arXiv Detail & Related papers (2023-11-28T01:06:03Z) - Taming Quantum Time Complexity [50.10645865330582]
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) - New Approaches to Complexity via Quantum Graphs [0.0]
We introduce and study the clique problem for quantum graphs.
inputs for our problems are presented as quantum channels induced by circuits.
We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $textsfNP$, $textsfMA$, $textsfQMA$, and $textsfQMA(2)$.
arXiv Detail & Related papers (2023-09-22T14:20:14Z) - Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.
We use this framework to study the complexity of transforming one entangled state into another via local operations.
Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
arXiv Detail & Related papers (2023-06-22T17:46:39Z) - 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) - 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.