Monte Carlo Quantum Computing
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
It is shown that a particular class of so-called strongly frustration-free manybody Hamiltonians can be Monte Carlo simulated efficiently on a classical computing machine, because the ground state of such a Hamiltonian is locally determined in the sense of having a nodal structure that is efficiently computable locally by solving a small subsystem associated with a low-dimensional configuration subspace. It is further demonstrated that strongly frustration-free Hamiltonians can be designed to implement universal ground state quantum computation. The two results combined have effectively solved the notorious sign problem in Monte Carlo simulations, and proved that all bounded-error quantum polynomial time algorithms admit bounded-error probabilistic polynomial time simulations.