Complexity of Supersymmetric Systems and the Cohomology Problem

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.

46+11 pages

References in corpus (50)

• Fault-tolerant quantum computation by anyons
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• Quantum Chemistry in the Age of Quantum Computing
• Fermionic quantum computation
• The Bravyi-Kitaev transformation for quantum computation of electronic structure
• A Theory of Trotter Error
• Solutions of the Two Dimensional Hubbard Model: Benchmarks and Results from a Wide Range of Numerical Algorithms
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
• Emergent Space-time Supersymmetry at the Boundary of a Topological Phase
• Simulation of topological field theories by quantum computers
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• Provably efficient machine learning for quantum many-body problems
• A Short Introduction to Topological Quantum Computation
• N-representability is QMA-complete
• Strategies for solving the Fermi-Hubbard model on near-term quantum computers
• Emergent Supersymmetry from Strongly Interacting Majorana Zero Modes
• Quantum Hamiltonian Complexity
• Lattice Models with N=2 Supersymmetry
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• The Clique Density Theorem
• Lattice fermion models with supersymmetry
• On the hardness of classically simulating the one clean qubit model
• Hamiltonian simulation in the low-energy subspace
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Exact results for strongly-correlated fermions in 2+1 dimensions
• Mirror Symmetry in 2+1 and 1+1 Dimensions
• Towards quantum advantage via topological data analysis
• Extensive ground state entropy in supersymmetric lattice models
• Non-local space-time supersymmetry on the lattice
• Supersymmetric SYK models
• Isoperimetric Inequalities in Simplicial Complexes
• Computational Difficulty of Computing the Density of States
• Exact ground states of a staggered supersymmetric model for lattice fermions
• Supersymmetric lattice fermions on the triangular lattice: superfrustration and criticality
• Cooper pairs and exclusion statistics from coupled free-fermion chains
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
• What the foundations of quantum computer science teach us about chemistry
• Quantum 3-SAT is QMA1-complete
• Quantum Proofs for Classical Theorems
• Bethe ansatz solvability and supersymmetry of the $M_2$ model of single fermions and pairs
• Supersymmetric Model of Spin-1/2 Fermions on a Chain
• Electronic Structure in a Fixed Basis is QMA-complete
• Some Algorithmic Problems in Polytope Theory
• On Perfect Completeness for QMA
• Supersymmetry, lattice fermions, independence complexes and cohomology theory
• Supersymmetry and Quantum Computation

Cited by in corpus (9)

• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum algorithm for persistent Betti numbers and topological data analysis
• Clique Homology is QMA1-hard
• The topology of data hides in quantum thermal states
• Quantum topological data analysis via the estimation of the density of states
• The 7 faces of quantum NP
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Provable quantum speedups for computing persistence in topological data analysis
• Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes