Complexity of Supersymmetric Systems and the Cohomology Problem

• URL: http://arxiv.org/abs/2107.00011v2
• Date: Thu, 18 Apr 2024 11:28:25 GMT
• Title: Complexity of Supersymmetric Systems and the Cohomology Problem
• Authors: Chris Cade, P. Marcos Crichigno,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $\mathcal N=2 $ supersymmetry and show that the problem remains $\mathsf{QMA}$-complete. Our main motivation for studying this is the well-known fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial. This opens the door to bringing the tools of Hamiltonian complexity to study the computational complexity of a large number of algorithmic problems that arise in homological algebra, including problems in algebraic topology, algebraic geometry, and group theory. We take the first steps in this direction by introducing the $k$-local Cohomology problem and showing that it is $\mathsf{QMA}_1$-hard and, for a large class of instances, is contained in $\mathsf{QMA}$. We then consider the complexity of estimating normalized Betti numbers and show that this problem is hard for the quantum complexity class $\mathsf{DQC}1$, and for a large class of instances is contained in $\mathsf{BQP}$. In light of these results, we argue that it is natural to frame many of these homological problems in terms of finding ground states of supersymmetric fermionic systems. As an illustration of this perspective we discuss in some detail the model of Fendley, Schoutens, and de Boer consisting of hard-core fermions on a graph, whose ground state structure encodes $l$-dimensional holes in the independence complex of the graph. This offers a new perspective on existing quantum algorithms for topological data analysis and suggests new ones.

Related papers

• 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)
• Exactly solvable models for fermionic symmetry-enriched topological phases and fermionic 't Hooft anomaly [33.49184078479579]
  The interplay between symmetry and topological properties plays a very important role in modern physics. How to realize all these fermionic SET (fSET) phases in lattice models remains to be a difficult open problem.
  arXiv  Detail & Related papers  (2024-10-24T19:52:27Z)
• 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)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• 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)
• 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)
• On the complexity of quantum partition functions [2.6937287784482313]
  We study the computational complexity of approximating quantities for $n$-qubit local Hamiltonians. A classical algorithm with $mathrmpoly(n)$ approximates the free energy of a given $2$-local Hamiltonian.
  arXiv  Detail & Related papers  (2021-10-29T00:05:25Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
  arXiv  Detail & Related papers  (2021-06-27T17:25:24Z)
• Geometric and computational aspects of chiral topological quantum matter [0.0]
  We study chiral topological phases of 2+1 dimensional quantum matter. Such phases are characterized by their non-vanishing chiral central charge $c$.
  arXiv  Detail & Related papers  (2021-06-21T07:34:05Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  In particular, we study the problem of learning halfspaces under Massart noise with rate $eta$. We show any SQ algorithm requires super-polynomially many queries to achieve $mathsfOPT + epsilon$. We also study our algorithm for learning halfspaces under Massart noise empirically and find that it exhibits some appealing fairness properties.
  arXiv  Detail & Related papers  (2020-06-08T17:59: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.