Quantum Hamiltonian Complexity: Taming Quantum Systems

The exponential power of quantum systems, which makes quantum computers possible, also makes it prohibitively hard to classically simulate or even understand general quantum many body systems. How well can physics hope to understand Nature at the quantum level in view of this exponential complexity? We propose to exhibit a large class of "natural" quantum systems which do not suffer from this curse of exponentiality, by showing that they can be simulated efficiently on a classical computer. To do so, we will build upon our recent breakthrough (supported by Templeton Grant 21674) showing that (gapped) one dimensional quantum systems can be efficiently simulated. The new algorithm proceeds via the rigorous proof of an "area law" for such systems (Hastings 2007, Arad, Kitaev, Landau & Vazirani 2012). Moreover, the bounds for the 1D area law are finely poised so that the slightest further improvement would result in progress on the major challenge of proving an area law for 2 dimensional systems. These questions are major challenges in the area of Condensed Matter Physics (CMP), and are made accessible through an extraordinary convergence between CMP and quantum complexity theory. The exponential scaling of quantum systems raises another fundamental question: is the scientific method sufficiently powerful to verify a theory whose predictions are exponentially hard to compute? In a recent paper (Aharonov, Vazirani 2013), we argued that the answer was negative. We also conjectured that a modification of the standard scientific method (inspired by Aharonov, Ben-Or, Eban 2009) would lead to an affirmative answer. We propose to resolve this fundamental problem, building upon techniques from another recent paper (Reichardt, Unger, Vazirani Nature 2013). If successful, this would be a major step in revising the several century old paradigm of the scientific method, and demonstrate that it is possible to test quantum mechanics in the limit of high complexity.