We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>

Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely ... more >>>

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the $\QMA$-complete Local Hamiltonian problem \cite{KSV02}. For the $\beta$-gapped, frustration-free case, \citet{BBT06} showed that the problem is $\MA$-complete when $\beta= \frac{1}{\poly(n)}$. \citet{AG19} derandomized this algorithm and proved membership in $\NP$ for constant gap $\beta = ... more >>>