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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">N</mml:mi></mml:mrow><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:math> supersymmetry and show that the problem remains <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow></mml:math>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-local Cohomology problem and showing that it is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:math>-hard and, for a large class of instances, is contained in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow></mml:math>. We then consider the complexity of estimating normalized Betti numbers and show that this problem is hard for the quantum complexity class <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">D</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">C</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:math>, and for a large class of instances is contained in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">B</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math>. 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>l</mml:mi></mml:math>-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.

Topics & Concepts