Recent Discoveries in Quantum Hamiltonian Complexity

• Kitaev proved that k-LH is in QMA for k>=1 and QMA-hard for k>=5.
• Oliveira and Terhal showed that LH with Hamiltonians restricted to nearest neighbor interaction on a 2D grid is still QMA-complete.
• Aharonov, Gottesman, Irani and Kempe showed that 2-LH with nearest neighbor interactions on the line is also QMA complete if the local system have dimension of at least 12.
• Cubitt and Montanaro established a quantum variant of Schaefers Dichotomy Theorem.
• Bravyi defined Quantum k-SAT in which all local constraints are positive semidefinite, and the question is whether the ground state energy is zero.
• Aharonov and Eldar proved that approximating the ground state energy of commuting local Hamiltonians on good locally-expanding graphs is in NP.
• Gharibian, Landau, Shin and Wang showed that the commuting variant of the Stoquastic k-SAT problem is in NP for logarithmic k and any constant d.
• Yan and Bacon showed that LH with all commuting terms are products of Pauli operators is in P.
• Schuch and Verstraete showed that Hubbard Model has QMA hardness.
• Bravyi has given a Fully Polynomial Randomized Approximation Scheme for approximating the partition function of the transverse field Ising model.
• Baharonas works showed that finding a ground state and computing the magnetic partition function of an Ising spin glass in a nonuniform magnetic field are NP hard tasks.
• Whites discovered his celebrated Density Matrix Renormalization Group.
• Verstraete and Cirac Projected entangled pair states
• Schuch, Wolf, Verstraete and Cirac found that MPS and MERA networks can be efficiently contracted.
• Arad, Kitaev, Landau, Vazirani showed that MPS with sublinear bond dimension suffices to approximate the ground state.
• A combinatorial proof improving on Hastings result for the frustration-free case was later given by Aharonov, Arad, Landau and Vazarani.
• Cubitt, Perez, Garcia, Wolf showed that determining whether a translational-invariant, nearest-neighbor Hamiltonian on a 2D square lattice is gapped is undecidable.
• Gosset, Terhal, and Vershynina showed how to perform universal adiabatic quantum computation using space-time circuit-to-Hamiltonian construction.
• Fitzsimons and Vidick gave a multiprover interactive proof system for the Local Hamiltonian problem involving a constant number of entangled provers.
• Chubb and Flamia extended the works of Landau, Vazirani and Vidick and Huang to give a polynomial time algorithm for approximating ground space projectors of gapped 1D Hamiltonians with degenerate groun spaces.
• Gharibian and Sikora showed that given a local Hamiltonian and two ground states, is there a sequence of local unitaries mapping between the two states.
• Ge and Eisert showed that in two and higher dimensions, it is not general true that an area law for the Renyi entanglement entropy implies the ability to faithfully describe a quantum many-body state by an efficient tensor network.
• Aharonov showed that a generalized version of the area law fails to hold.
• Movassah and Shor showed that a generalization of Bravyis spin-1 model to integer spin-s chains yields a power law violation of the area law.
• Brandao and Cramer showed that the exponential decay in the specific heat capacity at low temperatures yields an area law for low-energy states
• Marien proved that the stability of the area law for entanglement entropy in quantum spin systems in the setting of adiabatic and quasi-adiabatic evolutions.