Free fermions behind the disguise

An invaluable method for probing the physics of a quantum many-body spin system is a mapping to non-interacting effective fermions. We find such mappings using only the frustration graph G of a Hamiltonian H, i.e., the network of anti-commutation relations between the Pauli terms in H in a given basis. We prove theorems based solely on the graph G to identify when H is a free-fermion-solvable model, even when no Jordan-Wigner transformation exists. Specifically, when G is (even-hole, claw)-free and contains a simplicial clique, we construct an explicit free-fermion solution for H using only this structure of G. The solution method is generic in that it applies for any values of the couplings. This mapping generalizes both the classic Lieb-Schultz-Mattis solution of the XY model and an exact solution of a spin chain recently given by Fendley, dubbed "free fermions in disguise." Like Fendley's original example, the free-fermion operators that solve the model are generally highly nonlinear and nonlocal, but can nonetheless be found explicitly using a transfer operator defined in terms of the independent sets of G. The associated single-particle energies are calculated using the roots of the independence polynomial of G, which are guaranteed to be real by a result of Chudnovsky and Seymour. Furthermore, recognizing (even-hole, claw)-free graphs and finding a simplicial clique in one can be done in polynomial time, so recognizing when a spin model is solvable in this way is efficient. We give several example families of solvable models for which no Jordan-Wigner solution exists, and we give a detailed analysis of such a spin chain having 4-body couplings using this method.