Fermionic Independent Set and Laplacian of an independence complex are QMA-hard Chaithanya Rayudu Abstract The Independent Set is a well known NP-hard optimization problem. In this work, we define a fermionic generalization of the Independent Set problem and prove that the optimization problem is QMA-hard in a k k -particle subspace using perturbative gadgets. We discuss how the Fermionic Independent Set is related to the problem of computing the minimum eigenvalue of the k th k^{\text{th}} -Laplacian of an independence complex of a vertex weighted graph. Consequently, we use the same perturbative gadget to prove QMA-hardness of the later problem resolving an open conjecture from [ 1 ] and give the first example of a natural topological data analysis problem that is QMA-hard. 1 Introduction Quantum Merlin Arthur (QMA) is the complexity class of decision problems for which a ‘yes’ solution can be efficiently verified using a quantum computer. The k -Local Hamiltonian problem [ 2 , 3 , 4 ] was the first non-trivial problem shown to be QMA-complete. Since then numerous other problems have been proven QMA-complete, mostly arising in quantum computing and information science [ 5 ] . While the k -Local Hamiltonian problem serves as a fundamental QMA-complete problem, analogous to k -SAT’s role in NP-completeness, the majority of NP-complete problems are constrained combinatorial optimization problems such as Minimum Vertex Cover, Maximum Independent Set, and Longest Path [ 6 ] . Such constrained optimization problems had a great impact on the development of classical algorithms, and hardness results. By studying quantum generalizations of such constrained optimization problems, we can explore new quantum algorithms and hardness results for quantum problems that are currently lacking. This kind of motivation inspired a previous work [ 7 ] which studies quantum generalizations of classical constrained problems with Vertex Cover as a driving example. Following this motivation, we define a fermionic generalization of the Independent Set and study its computational complexity. We prove that the Fermionic Independent Set is QMA-hard when restricted to a k -particle subspace. When problems without an obvious quantum connection are shown to be related QMA, it can offer new insights into the structure of QMA and as well as the problem at hand. One such problem in Homology is to determine the existence of a k -dimensional hole in a topological space. When the space is represented by the clique complex of a graph, this problem is of practical interest in Topological Data Analysis (TDA) which uses topological features such as holes to characterize and study data. TDA has found a broad range of applications from computational neuroscience [ 8 ] to cosmology [ 9 ] . Recently, there has been a significant progress towards understanding the computational complexity of determining the existence of a hole by relating it to quantum complexity classes. This connection was possible because of a correspondence between the combinatorial Laplacian of a clique complex whose null space captures the holes and a supersymmetric Hamiltonian [ 10 ] . The question of whether the clique complex has a k -dimensional hole or not is equivalent to whether the supersymmetric Hamiltonian has a zero energy ground state or not in the k -particle subspace. In this work, we prove that computing the minimum eigenvalue of the k^{\text{th}} -Laplacian of a clique complex is QMA-hard resolving an open conjecture from [ 1 ] in the affirmative. Our result is proved for the Laplacian operator of the independence complex and holds true for the clique complex as well since the clique complex of a graph is same as the independence complex of the complement graph. A novelty of our work lies in the simplicity of our proof techniques based on perturbative gadgets compared to highly specialized homological proof techniques of previous works [ 11 , 1 ] . Although the Fermionic Independent Set and the minimum eigenvalue problem of the Laplacian of an independence complex might seem unrelated at first, when expressed as constrained optimization problems they differ only slightly in their objective functions. The similarity between the problems is also reflected in the fact that we use the same perturbative gadget to prove QMA-hardness of both the problems. We consequently establish the first QMA-hardness result of a natural TDA problem. 1.1 Related Work Crichigno and Kohler [ 11 ] proved that the problem of deciding whether the minimum eigenvalue of the k^{\text{th}} -Lapalacian is equal to 0 or >0 is QMA 1 -hard where QMA 1 is the complexity class QMA with perfect completeness. But the corresponding QMA 1 -hard supersymmetric Hamiltonians that they construct can have exponentially small gap above the zero energy ground space. This was later improved by King and Kohler [ 1 ] where they constructed QMA 1 -hard supersymmetric Hamiltonians corresponding to clique complexes of vertex weighted graphs with inverse polynomial gap above the zero energy ground space, thereby placing them in QMA. The authors conjectured in [ 1 ] that there are supersymmetric Hamiltonians corresponding to clique complexes which are QMA-hard, meaning estimating the minimum eigenvalue of the Laplacian operator even when it is nonzero is QMA-hard, rather than just QMA 1 -hard. 1.2 Notation and organization The notation [n] denotes the set of integers \{1,2,...,n\} . A graph is denoted by G , G([n],E) where vertices are labeled by elements from [n] and set E denotes the edges between the vertices. An edge between vertices i and j is represent by ij . Hamiltonians are denoted by H and V with various subscripts, and projectors are denoted by P and \Pi with various subscripts. Hilbert spaces are denoted by \mathcal{H} with various subscripts. The notation \rho denotes a density operator and the notation \mathrm{Tr}[A] denotes the matrix trace of an operator A . Positive semi-definiteness of an operator A is denoted by A\succeq 0 . Fermionic creation and annihilation operators are denoted by a^{\dagger} , a . Pauli matrices X , Y , and Z are defined as follows \displaystyle X=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},\,\,\,\,\,\,Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},\,\text{and}\,\,\,\,\,\,Z=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix}. In section 2 , we define the Fermionic Independent Set problem and the minimum eigenvalue problem of the Laplacian of an independence complex of a vertex weighted graph. We briefly the similarities and the differences between the two problems. In appendix A , we recall some theorems behind perturbative gadgets necessary for our work. In section 3 , we give a proof of QMA-hardness of Fermionic Independent Set problem when restricted to a k -particle subspace. In section 4 , we extend the QMA-hardness proof to minimum eigenvalue problem of the k^{\text{th}} -Laplacian of an independence complex. 2 Definitions 2.1 Independent Set Independent Set is a combinatorial graph optimization problem. Given a graph G([n],E) with vertex weights \{c_{i}\}_{i\in[n]} , a subset of vertices S\subseteq[n] is called an independent set of graph G if no two vertices from the subset S are adjacent to each other in graph G . In other words, S is an independent set of G if for all distinct i,j\in S , ij\notin E . Weight of an independent set S is sum of weights of all the vertices in the independent set S . The weighted Independent Set problem is to find an independent set with the maximum weight. Let x_{i}\in\{0,1\} be a binary variable for each i\in[n] such that if i\in S then x_{i}=1 and x_{i}=0 otherwise. Formally, we can define the optimization problem as \displaystyle\max\,\,\sum_{i\in V}c_{i}x_{i} (1) \displaystyle s.t.\,\,\,\,\,\,\,\,\,\,\, \displaystyle x_{i}x_{j}=0\quad\forall\,ij\in E, (2) \displaystyle x_{i}\in\{0,1\}\quad\forall\,i\in[n]. (3) The constraint x_{i}x_{j}=0 implies at most only one of x_{i} or x_{j} can be equal 1 which implies at most only one of i or j can be in set S . Independent Set and Vertex Cover are complement to each other. For every independent set S\subseteq[n] , the complement subset [n]\backslash S is a vertex cover. Therefore, Maximum Independent Set and Minimum Vertex Cover problems are equivalent to each other. By identifying the vertices of the graph with fermionic modes such that creation and annihilation operators of the mode labeled by the i^{\text{th}} vertex are a_{i}^{\dagger} and a_{i} , we can represent an independent set S with fock states \Pi_{i\in S}\,a^{\dagger}_{i}\ket{\text{vac}} that are equivalent up to a phase. With the fermionic representation, we can rewrite the Independent Set optimization problem as \displaystyle\max_{\rho}\,\, \displaystyle\mathrm{Tr}\left[\left(\sum_{i}c_{i}a^{\dagger}_{i}a_{i}\right)\rho\right] (4) \displaystyle s.t.\quad \displaystyle\mathrm{Tr}\left[a^{\dagger}_{i}a_{i}a^{\dagger}_{j}a_{j}\rho\right]=0\quad\forall\,ij\in E, (5) \displaystyle\mathrm{Tr}[\rho]=1,\,\,\rho\succeq 0. (6) The constraint operators a^{\dagger}_{i}a_{i}a^{\dagger}_{j}a_{j} in eq. 5 are projectors onto the fock state a_{i}^{\dagger}a_{j}^{\dagger}\ket{vac} of the i , j modes restricting \rho to be in the subspace orthogonal to a_{i}^{\dagger}a_{j}^{\dagger}\ket{vac} . These constraints require \rho to have a maximum of one spinless fermion among the modes i and j for every edge ij in graph G . 2.2 Fermionic Independent Set We propose a fermionic generalization of the Independent Set called Fermionic Independent Set defined as follows. Definition 1 (Fermionic Independent Set) . Let G([n],E) be a graph with n vertices and an edge set E where the vertices label fermionic modes that can be occupied by spinless fermions. Given a hopping Hamiltonian H=\sum_{ij\in E}w_{ij}(a^{\dagger}_{i}a_{j}+a^{\dagger}_{j}a_{i}) , the Fermionic Independent Set optimization problem is defined as \displaystyle\min_{\rho}\,\, \displaystyle\mathrm{Tr}[\left(\sum_{ij\in E}w_{ij}(a^{\dagger}_{i}a_{j}+a^{\dagger}_{j}a_{i})\right)\rho] (7) \displaystyle s.t.\quad \displaystyle\mathrm{Tr}[a^{\dagger}_{i}a_{i}a^{\dagger}_{j}a_{j}\rho]=0\quad\forall\,ij\in E, (8) \displaystyle\mathrm{Tr}[\rho]=1,\,\,\rho\succeq 0. (9) One of the key features we aimed for in defining a fermionic generalization of the classical Independent Set is that the objective Hamiltonian should be easy to optimize if we ignore the constraints. With that in mind, our choice of Hamiltonian H to be a hopping Hamiltonian is not the only choice. One could consider a more general quadratic Hamiltonian that includes diagonal terms a^{\dagger}_{i}a_{i} which can be exactly diagonalized in a polynomial time on a classical computer. Without the quadratic diagonal terms, our definition of a Fermionic Independent Set is not a strict generalization of the classical Independent Set problem. But for the purpose of understanding the computational complexity of the problem, it is sufficient to restrict to single particle hopping Hamiltonians. Instead of fermionic generalization of the Independent Set, we could consider generalizing the Vertex Cover with fermions where we have vertex cover constraints instead of independent set constraints. Physically, independent set constraints can be intuitively interpreted as fermionic modes with strong repulsion giving rise to an effective low energy subspace. One way to obtain the fermionic generalization of Vertex Cover from definition 1 is by applying a transformation \mathcal{T} that transforms the creation and annihilation operators as \mathcal{T}a_{i}\mathcal{T}^{-1}=a_{i}^{\dagger} , \mathcal{T}a_{i}^{\dagger}\mathcal{T}^{-1}=a_{i} and the vacuum state as \mathcal{T}\ket{vac}=\Pi_{i=1}^{|V|}a_{i}^{\dagger}\ket{vac} . This transformation changes eq. 8 into a vertex cover constraint \mathrm{Tr}[(I-a^{\dagger}_{i}a_{i})(I-a^{\dagger}_{j}a_{j})\rho]=0 and the hopping Hamiltonian from H to -H . Therefore, both the problems are equivalent to each other. In section 3 , we prove that the Fermionic Independent Set is QMA-hard when restricted to a k -particle subspace. Theorem 2 . The Fermionic Independent Set problem as defined in definition 1 is QMA-hard when restricted to a k -particle subspace. Furthermore, we prove QMA-hardness of the problem with additional structure thereby implying that the general problem is also QMA-hard. The additional structure is that the hopping weights w_{ij}=u_{i}u_{j} \forall\,ij\in E with vertex weights u_{i}\geq 0\,\,\forall\,i\in[n] . 2.3 Laplacian of an independence complex In topological data analysis, data is studied using topological features such as holes. When the data is given as a graph which in turn can be triangulation of an underlying topological manifold, homology of the clique complex of the graph provides information about the holes in the underlying topological manifold. Clique complex of a graph is equivalent to independence complex of the complement graph. The independence complex of a graph G([n],V) is a simplical chain complex where the simplices are the independent sets of the graph G . Let S=\{v_{1},v_{2},...,v_{k}\}\subseteq[n] be an independent set of size k of the graph G , and the corresponding k -simplex is an ordered set of vertices \ket{v_{1},v_{2},...,v_{k}} . The simplices that differ only in the ordering of vertices are equivalent to each other up to a phase such that \displaystyle|...,v_{i},v_{j},...\rangle=-|...,v_{j},v_{i},...\rangle (10) where swapping of two neighboring vertices in the ordering induces a negative sign. Let C_{k} be the free abelian group with k -simplices as the basis. The boundary operator \partial_{k}:C_{k}\rightarrow C_{k-1} is defined by its action on a k -simplex as \displaystyle\partial_{k}\ket{v_{1},...,v_{k}}=\sum_{i=1}^{k}(-1)^{i}\ket{v_{1},...v_{i-1},v_{i+1},...,v_{k}}, (11) and the boundary operators satisfy \partial_{k}\partial_{k-1}=0\,\forall\,k . Formally, independence complex is a chain complex defined as \displaystyle...\xrightarrow{\partial_{k+2}}C_{k+1}\xrightarrow{\partial_{k+1}}C_{k}\xrightarrow{\partial_{k}}C_{k-1}\xrightarrow{\partial_{k-1}}... The k^{\text{th}} -homology \mathcal{H}_{k} of the chain complex is the following quotient group: \displaystyle\mathcal{H}_{k}=\text{Kernel}(\partial_{k})/\text{Image}(\partial_{k+1}). (12) We can capture the k^{\text{th}} -Homology group using representatives from each equivalence class in the quotient group that are orthogonal to Image (\partial_{k+1}) . To have a notion of orthogonality, let us introduce an inner product \langle a,b\rangle between any two simplices a,b as follows \displaystyle\langle a,b\rangle=\begin{cases}w(a)w(b)&\text{ if }a=b\\ -w(a)w(b)&\text{ else if }a=-b\\ 0&\text{ otherwise}\end{cases} (13) where weight of a simplex w(v_{1},v_{2},...,v_{k})=w(v_{1})w(v_{2})...w(v_{k}) is the product of weights of its vertices. With this inner-product, we now have a Hilbert space. The span of the representatives from each of the equivalence classes is the kernel of the k^{\text{th}} -Laplacian operator \Delta_{k}:C_{k}\rightarrow C_{k} defined as \displaystyle\Delta_{k}=\partial_{k}^{\dagger}\partial_{k}+\partial_{k+1}\partial_{k+1}^{\dagger}. (14) Note that the Laplacian operator is positive semi-definite. The question of whether there are any k -dimensional holes is equivalent to asking if the minimum eigenvalue of the k^{\text{th}} -Laplacian \Delta_{k} is =0 or >0 . We can rewrite the question about minimum eigenvalue of the Laplacian using fermions. Let the vertices of the graph G([n],E) label fermionic modes that can be occupied by spinless fermions, and consider a staggered (weighted) supersymmetric Hamiltonian H_{\text{Lap}}=Q^{\dagger}Q+QQ^{\dagger} , where \displaystyle Q=\sum_{i\in[n]}u_{i}P_{i}a_{i}\quad\text{ and }\quad Q^{\dagger}=\sum_{i\in[n]}u_{i}P_{i}a_{i}^{\dagger}\quad\text{ where }\quad P_{i}=\prod_{j\mid ij\in E}\left(I-a^{\dagger}_{j}a_{j}\right)\quad\text{ and }\quad u_{i}\geq 0 (15) After simplification, we can rewrite the Hamiltonian H_{\text{Lap}} as \displaystyle H_{\text{Lap}}=\sum_{ij\in E}u_{i}u_{j}P_{i}a_{i}^{\dagger}a_{j}P_{j}+\sum_{i\in[n]}u_{i}^{2}P_{i}. (16) It is easy to verify that the Hamiltonian H_{\text{Lap}} preserves the subspace of hard-core fermions defined as the fock subspace where no two fermions are adjacent to each other on the graph G which is an independent constraint. The subspace of hard-core fermions forms a representation for the simplices of the independence complex, and the Hamiltonian H_{\text{Lap}} projected onto the subspace of hardcore fermions forms a representation for the Laplacian of the independence complex [ 11 , 12 ] . Now the question about the minimum eigenvalue of the Laplacian can be rewritten as a constrained optimization problem using fermions as follows. Definition 3 (Minimum eigenvalue of the Laplacian of an independence complex) . Let G([n],E) be a graph with n vertices and an edge set E where the vertices label fermionic modes that can be occupied by spinless fermions. Let H_{\text{Lap}} be a supersymmetric Hamiltonian defined as \displaystyle H_{\text{Lap}}=\sum_{ij\in E}u_{i}u_{j}(a_{i}^{\dagger}a_{j}+a_{j}^{\dagger}a_{i})+\sum_{i\in V}u_{i}^{2}P_{i}\quad\text{where}\quad P_{i}=\prod_{j\mid ij\in E}\left(I-a^{\dagger}_{j}a_{j}\right)\quad\text{ and }\quad u_{i}\geq 0. (17) Then the problem of finding the minimum eigenvalue of H_{\text{Lap}} in the subspace of hard-core fermions can be written as a constrained optimization problem as follows \displaystyle\min_{\rho}\,\, \displaystyle\mathrm{Tr}\left[\left(\sum_{ij\in E}u_{i}u_{j}(a_{i}^{\dagger}a_{j}+a_{j}^{\dagger}a_{i})+\sum_{i\in[n]}u_{i}^{2}P_{i}\right)\rho\right] (18) \displaystyle s.t.\quad \displaystyle\mathrm{Tr}[a^{\dagger}_{i}a_{i}a^{\dagger}_{j}a_{j}\rho]=0\quad\forall\,ij\in E, (19) \displaystyle\mathrm{Tr}[\rho]=1,\,\,\rho\succeq 0. (20) There are two main differences between the above optimization problem and the definition 1 of Fermionic Independent Set. First, the weights for the hopping terms (a_{i}^{\dagger}a_{j}+a_{j}^{\dagger}a_{i}) in the objective have a vertex weighted product structure for edge weights i.e., w_{ij}=u_{i}u_{j}\,\forall ij\in E . Second, the objective Hamiltonian has additional diagonal terms \sum_{i\in V}u_{i}^{2}P_{i} . It was shown in [ 1 ] that the promise problem of deciding whether the optimal value to the above problem is zero or at least 1/\text{poly}(n) in a given k -particle subspace is QMA 1 -hard and is contained in QMA, and it was conjectured that the promise problem of deciding whether the optimal value is \leq a ( a need not be equal to zero) or \geq b for some a,b such that b-a\geq 1/\text{poly}(n) is QMA-hard. We resolve this conjecture in section 4 by showing that it is indeed QMA-hard to estimate the optimal value within an inverse polynomial additive precision even when it is nonzero. 3 Complexity of Fermionic Independent Set See 2 We show this by a reduction from XZ -Hamiltonian which was proven to be QMA-hard and universal for quantum simulation in [ 13 , 14 ] . The rest of this section contains the proof of theorem 2 . An overview of the perturbative gadget in the proof is as follows. 1. We start by encoding a qubit using three fermionic modes. The three modes have a pairwise independent set constraint between them as defined in eq. 5 and these constraints define the accessible subspace to be the span of single particle subspace and vacuum. In the accessible subspace, we encode a qubit as the low energy two-dimensional ground subspace of a single particle hopping Hamiltonian. 2. Next, we want to simulate the XZ interaction between any pair of encoded qubits. For every pair of encoded qubits between which we want to create XZ -interaction, we add three additional mediator modes. We also add additional independent set constraints as defined by the edges of the graph in fig. 2 and a perturbative single particle hopping Hamiltonian to create XZ -interaction at second order perturbation. This construction guarantees that the ground state energy of any given target XZ -Hamiltonian can be made arbitrarily close to the optimal value of the Fermionic Independent Set restricted to a k -particle subspace. Since estimating the ground state energy of a XZ -Hamiltonian is QMA-hard, Fermionic Independent Set when restricted to a k -particle is also QMA-hard. A key point in our analysis is that we do all our calculations in the accessible subspace defined by the independent set constraints. 3.1 Encoding a qubit Consider three fermionic modes labeled {1,2,3} , a constraint graph with edges (1,2) , (2,3) and (1,3) as in fig. 1 which requires at least two spinless fermions to satisfy the independent set constraints, 1 2 3 Figure 1 : Independent set constraint graph of three fermionic modes labeled 1,2,3. and consider a hopping Hamiltonian \displaystyle H_{0}=I+(a_{1}^{\dagger}a_{2}+a_{2}^{\dagger}a_{1})+(a_{2}^{\dagger}a_{3}+a_{3}^{\dagger}a_{2})+(a_{3}^{\dagger}a_{1}+a_{1}^{\dagger}a_{3}) (21) on the three modes which block diagonalizes into one, two, and three particle sectors. Among the eigenstates of H_{0} that satisfy the independent set constraints, there are two 1 -particle states with energy equal to 0 , one 1 -particle state with energy equal to 3 , and the vacuum with energy equal to 1 . Following are the corresponding eigenstates of H_{0} \displaystyle\ket{0}\,\, \displaystyle:=\,\,S_{0}\ket{vac},\quad\ket{1}\,\,:=\,\,S_{1}\ket{vac}, (22) \displaystyle\ket{2}\,\, \displaystyle:=\,\,S_{2}\ket{vac},\quad\ket{3}\,\,:=\,\,\ket{vac} (23) where \ket{vac} is the vacuum state and \displaystyle S_{0}:=\frac{1}{2\sqrt{3}}\left[(1-\sqrt{3})a_{3}^{\dagger}-2a_{1}^{\dagger}+(1+\sqrt{3})a_{2}^{\dagger}\right],\quad \displaystyle S_{1}:=\frac{1}{2\sqrt{3}}\left[(1+\sqrt{3})a_{3}^{\dagger}-2a_{1}^{\dagger}+(1-\sqrt{3})a_{2}^{\dagger}\right], (24) \displaystyle S_{2}:=\frac{1}{\sqrt{3}} \displaystyle\left[a_{3}^{\dagger}+a_{1}^{\dagger}+a_{2}^{\dagger}\right] (25) The states \ket{0} and \ket{1} have energy equal to 0 while the states \ket{2} and \ket{3} have energy equal to 3 and 1 respectively. We can now encode a qubit into the 2-dimensional low energy subspace spanned by the states \ket{0} and \ket{1} . 3.2 XZ -interaction between encoded qubits Consider sets of three fermionic modes labeled by \{i1,i2,i3\} for every logical qubit- i encoded using the isometry defined in the previous section. To simulate a two-qubit interaction between the qubits i and j , we add three empty mediator modes labeled x , y , z for every pair of i,j qubits and modify the independent set constraint graph by adding additional edges (i2,x) , (i3,y) , (j2,x) , (j3,y) , (i1,z) and (j1,z) as depicted in fig. 2 . i1 i2 i3 j1 j2 j3 x y z Figure 2 : Independent set constraint graph to create interaction between two encoded qubits i and j . We will consider the same hopping Hamiltonian H_{0,i}+H_{0,j} corresponding to \{i1,i2,i3\} and \{j1,j2,j3\} modes as defined in eq. 21 . Within the subspace defined by the independent set constraints of the graph in fig. 2 with 2 particles, the low energy subspace of H_{0,i}+H_{0,j} is 4 -fold degenerate with the following eigenstates \displaystyle\ket{00}_{ij}:=S_{i,0}S_{j,0}\ket{vac},\quad\ket{01}_{ij}:=S_{i,0}S_{j,1}\ket{vac}, \displaystyle\ket{10}_{ij}:=S_{i,1}S_{j,0}\ket{vac},\quad\ket{11}_{ij}:=S_{i,1}S_{j,1}\ket{vac}. (26) where S_{i,0},S_{i,1},S_{j,0} , S_{j,1} as in eq. 24 . Let \Pi_{-} be the projector onto the subspace spanned by these four encoded basis states and let \Pi_{+} be the projector onto the rest of the Hilbert space satisfying the independent set constraints of the graph in fig. 2 with 2 particles. To simulate a two-qubit interaction between the encoded qubits i and j , let us consider a perturbation \displaystyle V_{main}=V_{1}+V_{2} (27) where \displaystyle V_{1} \displaystyle=(a_{i2}^{\dagger}a_{x}+a_{x}^{\dagger}a_{i2})+(a_{j2}^{\dagger}a_{x}+a_{x}^{\dagger}a_{j2})+(a_{i3}^{\dagger}a_{y}+a_{y}^{\dagger}a_{i3})+(a_{j3}^{\dagger}a_{y}+a_{y}^{\dagger}a_{j3}). (28) \displaystyle V_{2} \displaystyle=(a_{i1}^{\dagger}a_{z}+a_{z}^{\dagger}a_{i1})+(a_{j1}^{\dagger}a_{z}+a_{z}^{\dagger}a_{j1}). (29) To first-order perturbation, there is no effect on the encoded qubits since (V_{main})_{--}=0 . At second-order perturbation, V_{main} can give rise to nontrivial interaction between the encoded qubits. To see the effect of V_{main} , let us first consider the effect of only a part of the perturbation V_{1}^{{}^{\prime}}=(a_{i2}^{\dagger}a_{x}+a_{x}^{\dagger}a_{i2}) as follows \displaystyle(V_{1}^{{}^{\prime}})_{+-}\ket{00}_{ij} \displaystyle=\frac{(1+\sqrt{3})}{12}a_{x}^{\dagger}\left[(1-\sqrt{3})a_{j3}^{\dagger}-2a_{j1}^{\dagger}\right]\ket{vac} (30) \displaystyle(V_{1}^{{}^{\prime}})_{+-}\ket{01}_{ij} \displaystyle=\frac{(1+\sqrt{3})}{12}a^{\dagger}_{x}\left[(1+\sqrt{3})a_{j3}^{\dagger}-2a_{j1}^{\dagger}\right]\ket{vac}, (31) \displaystyle(V_{1}^{{}^{\prime}})_{+-}\ket{10}_{ij} \displaystyle=\frac{(1-\sqrt{3})}{12}a^{\dagger}_{x}\left[(1-\sqrt{3})a_{j3}^{\dagger}-2a_{j1}^{\dagger}\right]\ket{vac}, (32) \displaystyle(V_{1}^{{}^{\prime}})_{+-}\ket{11}_{ij} \displaystyle=\frac{(1-\sqrt{3})}{12}a^{\dagger}_{x}\left[(1+\sqrt{3})a_{j3}^{\dagger}+2a_{j1}^{\dagger}\right]\ket{vac}. (33) The effect of operator (H_{0,i}+H_{0,j})^{-1} acting on above states can be calculated by writing them as a superposition of the following excited eigenstates of (H_{0,i}+H_{0,j}) , \displaystyle\frac{1}{\sqrt{2}}a^{\dagger}_{x}\left(a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)\ket{vac}\quad\text{ and }\quad\frac{1}{\sqrt{2}}a^{\dagger}_{x}\left(a^{\dagger}_{j1}-a^{\dagger}_{j3}\right)\ket{vac} (34) with eigenvalues 3 and 1 respectively. For example, \displaystyle(H_{0,i}+ \displaystyle H_{0,j})^{-1}(V_{1}^{{}^{\prime}})_{+-}\ket{00}_{ij} \displaystyle=(H_{0,i}+H_{0,j})^{-1}\frac{(1+\sqrt{3})}{12}a^{\dagger}_{x}\left[\frac{(3-\sqrt{3})}{\sqrt{2}}\frac{\left(-a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)}{\sqrt{2}}+\frac{(-1-\sqrt{3})}{\sqrt{2}}\frac{\left(a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)}{\sqrt{2}}\right]\ket{vac} (35) \displaystyle=\frac{(1+\sqrt{3})}{12}a^{\dagger}_{x}\left[\frac{(3-\sqrt{3})}{\sqrt{2}}\frac{\left(-a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)}{\sqrt{2}}+\frac{(-1-\sqrt{3})}{3\sqrt{2}}\frac{\left(a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)}{\sqrt{2}}\right]\ket{vac} (36) After some more similar calculations, we can express the effective interaction (V_{1}^{{}^{\prime}})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{1}^{{}^{\prime}})_{+-} in the matrix form as follows \displaystyle-(V_{1}^{{}^{\prime}})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{1}^{{}^{\prime}})_{+-}=\frac{-1}{54}\begin{pmatrix}4+\sqrt{3}&4+2\sqrt{3}&-5+2\sqrt{3}&-2\\ 4+2\sqrt{3}&16+9\sqrt{3}&-2&-5-2\sqrt{3}\\ -5+2\sqrt{3}&-2&16-9\sqrt{3}&4-2\sqrt{3}\\ -2&-5-2\sqrt{3}&4-2\sqrt{3}&4-\sqrt{3}\end{pmatrix} (37) where the rows and columns are index by \left\{\ket{00},\ket{01},\ket{10},\ket{11}\right\}_{ij} basis states defined in section 3.2 . Symmetrizing the interaction V_{1}^{{}^{\prime}} with respect to X_{i}X_{j} and SWAP(i,j) operators gives the effective interaction due to perturbation V_{1} as follows \displaystyle-(V_{1})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{1})_{+-} \displaystyle=\frac{-1}{27}\begin{pmatrix}8&-1&-1&-4\\ -1&32&-4&-1\\ -1&-4&32&-1\\ -4&-1&-1&32\end{pmatrix}. (38) \displaystyle=\frac{1}{27}\left(-20I+4X_{i}X_{j}+12Z_{i}Z_{j}+X_{i}+X_{j}\right). (39) The second equality in the above equation is a rewriting in the Pauli basis of the encoded qubits. A similar calculation for V_{2} shows that \displaystyle-(V_{2})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{2})_{+-}=\frac{1}{27}\left(-10I+8X_{i}X_{j}-X_{i}-X_{j}\right). (40) Since V_{1} perturbation uses x,y as mediator modes and V_{2} perturbation uses z mediator mode, they can be applied in parallel to get \displaystyle-(V_{main})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{main})_{+-}=-\frac{10}{9}I+\frac{4}{9}(X_{i}X_{j}+Z_{i}Z_{j}). (41) By theorem 6 with V_{extra}=0 , we can simulate the spectrum of a target XZ -Hamiltonian H_{target}=\sum_{ij}\frac{4}{9}\mu_{ij}(X_{i}X_{j}+Z_{i}Z_{j}) where \mu_{ij}\geq 0\forall i\neq j using Fermionic Independent Set with the objective Hamiltonian \displaystyle H=\Delta\sum_{i}H_{0,i}+\Delta^{1/2}\sum_{ij}\sqrt{\mu_{ij}}\,(V_{main})_{ij}. (42) Since estimating the ground energy of XZ -Hamiltonian is QMA-hard, this completes the proof that Fermionic Independent Set is QMA-hard. A detail that will be important in the next section is that in the above Hamiltonian H the weights of the hopping terms between different modes factorize product of single mode weights with the modes labeled by \{i1,i2,i3\}\,\forall i having a weight \Delta^{1/2} and the mediator modes between \{i1,i2,i3\} and \{j1,j2,j3\} having a weight \sqrt{\mu_{ij}} . 4 Complexity of Laplacian of an independence complex The main difference between the Fermionic Independent Set with the vertex-weighted product structure for the edge weights and the minimum eigenvalue problem of the Laplacian of the independence complex of a vertex-weighted graph is the extra diagonal terms in the objective. To prove QMA-hardness of the later problem, we will use the same gadget we used to prove the QMA-hardness of Fermionic Independent Set but with additional diagonal terms in the objective. The analysis of the gadget is very similar in both cases. So the reader is highly recommended to go through the analysis of the gadget for the Fermionic Independent Set before going through rest of this section as we will only explain the differences in the gadget here. Recall that in the gadget, every logical qubit i from the target Hamiltonian is encoded using three physical modes \{i1,i2,i3\} with a triangle graph as the independent set constraint graph. We modify the unperturbed Hamiltonian corresponding to each encoded qubit with diagonal terms compared to the case of the Fermionic Independent Set as follows \displaystyle H_{0}=(a_{1}^{\dagger}a_{2}+a_{2}^{\dagger}a_{1})+(a_{2}^{\dagger}a_{3}+a_{3}^{\dagger}a_{2})+(a_{3}^{\dagger}a_{1}+a_{1}^{\dagger}a_{3})+P_{1}+P_{2}+P_{3} (43) where \displaystyle P_{1}=(I-a_{2}^{\dagger}a_{2})(I-a_{3}^{\dagger}a_{3})...,\quad P_{2}=(I-a_{1}^{\dagger}a_{1})(I-a_{3}^{\dagger}a_{3})...,\quad P_{3}=(I-a_{1}^{\dagger}a_{1})(I-a_{2}^{\dagger}a_{2})... (44) The dots indicate other terms for mediator modes that we add to the gadget construction. For example, if we have two logical qubits i,j being encoded using six physical modes \{i1,i2,i3\} , \{j1,j2,j3\} , and we use an additional three mediator modes \{x,y,z\} to mediate the interaction between the encoded qubits i,j with a constrained graph in fig. 2 in section 3 , then \displaystyle P_{i1}=(I-a_{i2}^{\dagger}a_{i2})(I-a_{i3}^{\dagger}a_{i3}) \displaystyle(I-a_{z}^{\dagger}a_{z}),\quad P_{i2}=(I-a_{i1}^{\dagger}a_{i1})(I-a_{i3}^{\dagger}a_{i3})(I-a_{x}^{\dagger}a_{x}), \displaystyle P_{i3} \displaystyle=(I-a_{i1}^{\dagger}a_{i1})(I-a_{i2}^{\dagger}a_{i2})(I-a_{y}^{\dagger}a_{y}) (45) and similarly for encoded qubit j . In the subspace with no fermions in the mediator modes, the spectrum of eigenstates of H_{0} in eq. 43 that satisfy the independent set constraints remains the same as the unperturbed Hamiltonian in eq. 21 . Therefore, we will use the same isometry for encoding logical qubits as in the case of the Fermionic Independent Set. To create interaction between the two encoded qubits i and j , we will consider the same perturbation V_{main}=V_{1}+V_{2} as defined in eq. 27 via mediator modes. To see the effect of perturbation V_{main} at second order, we can go through a similar analysis as in the case of the Fermionic Independent Set. One difference is the action of (H_{0,i}+H_{0,j})^{-1} on the states (V_{main})_{+-}\{\ket{00},\ket{01},\ket{10},\ket{11}\} because of the change of the eigenvalues for the following eigenstates of (H_{0,i}+H_{0,j}) \displaystyle\frac{1}{\sqrt{2}}a^{\dagger}_{x}\left(a^{\dagger}_{j1}+a^{\dagger}_{j3}\right)\ket{vac}\quad\text{ and }\quad\frac{1}{\sqrt{2}}a^{\dagger}_{x}\left(a^{\dagger}_{j1}-a^{\dagger}_{j3}\right)\ket{vac} (46) from 3 and 1 respectively to 4 and 2. Taking into account the differences in these eigenvalues, we get the following second-order perturbative effects due to V_{1} and V_{2} \displaystyle-(V_{1})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{1})_{+-} \displaystyle=\frac{1}{72}\left(-28I+5X_{i}X_{j}+15Z_{i}Z_{j}+2X_{i}+2X_{j}\right), (47) \displaystyle-(V_{2})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{2})_{+-} \displaystyle=\frac{1}{72}\left(-14I+10X_{i}X_{j}-2X_{i}-2X_{j}\right) (48) Combining the effects of V_{1} and V_{2} , we get the effect due to V_{main} as follows \displaystyle-(V_{main})_{-+}(H_{0,i}+H_{0,j})^{-1}(V_{main})_{+-}=-\frac{7}{12}I+\frac{5}{24}(X_{i}X_{j}+Z_{i}Z_{j}) (49) Unlike the case of the Fermionic Independent Set where we had V_{extra}=0 , we will consider the remaining diagonal terms corresponding to the mediator modes as V_{extra} . For example in the case of two encoded qubits i,j with three mediator modes \{x,y,z\} , \displaystyle V_{extra}=P_{x}+P_{y}+P_{z} (50) where \displaystyle P_{x}=(I-a_{i2}^{\dagger}a_{i2})(I-a_{j2}^{\dagger}a_{j2}),\quad P_{y}=(I-a_{i3}^{\dagger}a_{i3})(I-a_{j3}^{\dagger}a_{j3}),\quad P_{z}=(I-a_{i1}^{\dagger}a_{i1})(I-a_{j1}^{\dagger}a_{j1}). (51) At first-order perturbation, \displaystyle(V_{extra})_{--}=(P_{x}+P_{y}+P_{z})_{--}=\frac{4}{3}I+\frac{1}{6}(X_{i}X_{j}+Z_{i}Z_{j}) (52) Putting it all together by theorem 6 , we can simulate the spectrum of a target XZ -Hamiltonian H_{target}=\sum_{ij}\frac{3}{8}\mu_{ij}(X_{i}X_{j}+Z_{i}Z_{j}) where \mu_{ij}\geq 0\,\forall i\neq j using k^{\text{th}} -Laplacian of an independence complex where k=n is the number of qubits in the target XZ -Hamiltonian. Since estimating the ground energy of XZ -Hamiltonian is QMA-hard, this completes the proof that estimating the minimum eigenvalue of the k^{\text{th}} -Laplacian of an independence complex is QMA-hard. Appendix A Perturbative Gadgets In this section we recall some perturbation theory based on Schrieffer–Wolff transformation [ 15 ] required for us in the context of Hamiltonian simulation. Here the word simulation is not to be confused with the simulation of Hamiltonian dynamics on a quantum computer. In our context, it means simulating the spectrum and eigenstates of a given Hamiltonian H_{target} using another Hamiltonian H_{sim} . Formally, we use the notion of simulation as defined in [ 16 ] which was later refined in [ 14 ] . Definition 4 ( [ 16 ] ) . Let H_{target} be a Hamiltonian acting on a Hilbert space \mathcal{H}_{\text{target}} of dimension N . A Hamiltonian H_{sim} with a well-separated N -dimensional low-energy subspace \mathcal{L}_{N}(H_{sim}) and an isometry (encoding) \mathcal{E}:\mathcal{H}_{target}\rightarrow\mathcal{H}_{sim} are said to simulate H_{target} with an error (\eta,\epsilon) if there exists an isometry \tilde{\mathcal{E}}:\mathcal{H}_{target}\rightarrow\mathcal{H}_{\text{sim}} such that 1. The image of \tilde{\mathcal{E}} coincides with the low-energy subspace \mathcal{L}_{N}(H_{sim}) . 2. ||H_{target}-\tilde{\mathcal{E}}^{\dagger}H_{\text{sim}}\tilde{\mathcal{E}}||\leq\epsilon . 3. ||\mathcal{E}-\tilde{\mathcal{E}}||\leq\eta . Constructively, we can use perturbative gadgets at different orders to construct H_{sim} that can simulate, as in definition 4 , a given H_{target} . We mention two theorems below one for simulation at first-order perturbation and another for second-order perturbation. Note that one can consider simulations at higher-order perturbations but we do not need them in this work. Let H_{0} be a Hamiltonian on Hilbert space \mathcal{H}_{sim} with an N -dimensional ground subspace. Let \Pi_{-} be the projector onto the ground subspace of H_{0} and \Pi_{+} be the projector onto the rest of the Hilbert space. For any given operator O acting on \mathcal{H}_{sim} , let \displaystyle O_{--}:=\Pi_{-}O\Pi_{-},\quad O_{-+}:=\Pi_{-}O\Pi_{+},\quad O_{+-}:=\Pi_{+}O\Pi_{-},\quad O_{++}:=\Pi_{+}O\Pi_{+}. (53) Assume that the lowest eigenvalue of H_{0} is equal to 0 which implies (H_{0})_{--}=0 and that the second lowest eigenvalue of H_{0} is greater than or equal to 1. Theorem 5 (First-order simulation [ 16 ] ) . Suppose one can choose an H_{0} , a V and an isometry \mathcal{E} such that \displaystyle||\mathcal{E}H_{\text{target}}\mathcal{E}^{\dagger}-(V)_{--}||\leq\epsilon/2. (54) Then H_{\text{sim}}=\Delta H_{0}+V simulates H_{\text{target}} with an error (\eta,\epsilon) provided that \Delta\geq O(\epsilon^{-1}||V||^{2}+\eta^{-1}||V||) . Theorem 6 (Second-order simulation [ 16 ] ) . Suppose one can choose H_{0} , V_{main} , V_{extra} and an isometry \mathcal{E} such that V_{extra} is block diagonal with respect to \Pi_{-} and \Pi_{+} , (V_{main})_{--}=0 and \displaystyle||\mathcal{E}H_{target}\mathcal{E}^{\dagger}-(V_{\text{extra}})_{--}+(V_{main})_{-+}H_{0}^{-1}(V_{main})_{+-}||\leq\epsilon/2. (55) Suppose the norms of V_{main} , V_{extra} is at most \Lambda . Then H_{sim}=\Delta H_{0}+\Delta^{1/2}V_{main}+V_{extra} simulates H_{target} with an error (\eta,\epsilon) provided that \Delta\geq O(\epsilon^{-2}\Lambda^{6}+\eta^{-2}\Lambda^{2}) . The condition in theorem 6 that V_{extra} should be block diagonal i.e., (V_{extra})_{+-}=0 can be relaxed to (V_{main})_{-+}H_{0}^{-1}(V_{extra})_{+-}=0 while the rest of the theorem still holds. Note that the definition 4 of simulation does not restrict the Hilbert space \mathcal{H}_{sim} to have underlying fermionic or a qubit structure. In the case of Fermionic Independent Set, we begin from a Hilbert space arising from fermionic modes but the independent set constraints define the accessible Hilbert space \mathcal{H}_{sim} .