We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error ϵ by a degree O(sqrt{nlog(1/ϵ)}) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
Ground-state entanglement governs various properties of quantum many-body systems at low temperatures and is the key to understanding gapped quantum phases of matter. Here we identify a structural property of entanglement in the ground state of gapped local Hamiltonians. This property is captured using a quantum information quantity known as the entanglement spread, which measures the difference between Rnyi entanglement entropies. Our main result shows that gapped ground states possess limited entanglement spread across any partition of the system, exhibiting an area-law scaling. Our result applies to systems with interactions described by any graph, but we obtain an improved bound for the special case of lattices. These interaction graphs include cases where entanglement entropy is known not to satisfy an area law. We achieve our results first by connecting the ground-state entanglement to the communication complexity of testing bipartite entangled states and then devising a communication scheme for testing ground states using recently developed quantum algorithms for Hamiltonian simulation.
As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have k copies of unknown states rho, sigma (acting on a d dimensional Hilbert space) respectively. Their goal is to estimate Tr(rho sigma) up to additive error eps, using local quantum operations and classical communication. In th
