The PI plans to apply the grant money towards a one-year visit to UC-Berkeley, where he intends to closely collaborate with Umesh Vazirani and his colleagues and students on two fundamental issues about ground states of local Hamiltonians - whether they satisfy the quantum analog of the PCP theorem, and whether they satisfy an area law. To gain the needed insight into the ground states of local Hamiltonians, the PI will employ his knowledge of classical PCP theory, a deep theory in computer science that he helped develop, and couple it with the expertise of the colleagues in Berkeley on quantum information theory.
A quantum analog of the PCP theorem would say something profound about quantum systems. Besides its implications in quantum information theory, it would also have more direct implication in physics, such as the realization, that quantum systems retain their exponential complexity at high temperature. In addition, an area law would explain the often localized behavior of wave functions for many-body systems.
If the PI and colleagues are successful in their efforts, this would be a development akin to the invention of classical PCP theory, that should attract a number of computational complexity theorists, and connect them with quantum computing. A deeper understanding of the behavior of ground states of local Hamiltonians should effect disciplines ranging from quantum chemistry to black hole physics.
A sweeping concecture in condensed matter physics, and one of the most important open questions in quantum Hamiltonian complexity theory, is the so-called Area law, which asserts that ground states of quantum many body systems on a lattice have limited entanglement. The generalized area law (a folklore conjecture) transitions from this physically motivated phenomenon to a very clean and general graph theoretic formulation, where in place of edges of the lattice, the terms of the Hamiltonian correspond to edges of an arbitrary graph. With Dorit Aharonov, Aram Harrow, Zeph Landau, Daniel Nagaj and Umesh Vazirani the PI has disproved the general area law. The research has also given an unexpected connection between the above area law problem and the quantum information theory problem, which asks if Alice and Bob can test whether their joint state is maximally entangled while exchanging only a constant number of qubits. Another significant outcome of the project is the discovery of a far-reaching connection between the Theory of Judgment Aggregation (more generally, Evaluation Aggregation), and a relatively young but rapidly growing field of universal algebra, that was primarily developed to investigate constraint satisfaction problems (CSPs). The connection yields a full classification of non-binary evaluations into possibility and impossibility domains both under the idempotent and the supportive conditions. This connects voting theory and universal algebra in an elegant way. The discovery was due to the PI's inspiring stay in the Simons institute, thanks to the current grant. It was obtained jointly with the RA of the PI, Yixin Xu. The PI has a work in progress with Piyush Shrivastava that connects two types of Ising models. When done, it will be a very significant generalization of the famous Lee-Yang theorem, and it will also shed new light on a well known combinatorial theorem, the so-called Lovasz Local Lemma. A byproduct of the above research, a short proof of a theorem, that computing mean magnetization for minimal energy states for ferromagnetic Ising models is hard, is already published. The PI has found new indications that computing mean values in the thermodynamic limit for shift-invariant local Hamiltonians is not possible. The above results, except the second one, connect physisics and complexity theory in novel ways. The most striking example to this is the first quoted outcome that uncovers a connection between the Area Law (physics) and entanglement testing (computer science). These outcomes complement very practical efforts of computing properties of condensed matter. The second result has an impact affecting economy and social sciences. It does not only provide a far-reaching generalization of the famous impossibility result of economist Kenneth J. Arrow, but shows that the right language of discussing this generalization is universal algebraic. The newly developed tool lets the PI and co-author (his grad student) superseed a previous generalization of Arrow's theorem by Elad Dokow and Ron Holzman that has appeared in the prestigious Journal of Economic Theory.
