From non-stoquastic to stoquastic Hamiltonians

Local stoquastic Hamiltonians are important both in practice and theory. Motivated by the problem of simulability by quantum Monte Carlo algorithms, we propose a definition of stoquasticity that emphasizes computational complexity. In its simplest form, we allow preprocessing on the description of the input Hamiltonian using polynomial classical computation to find and then apply the transformation that converts the Hamiltonian into a stoquastic Hamiltonian. We provide several examples and results motivating this definition.