9
$\begingroup$

I have recently thought about "importing" some physics-related question into quantum CS:

The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some lattice, whose groundstate exhibits a property in which entanglement of any closed region is proportional to the surface of the region, and not its volume (as it would for a general state). A famous conjecture is whether all constant-gapped Hamiltonians exhibit this area-law property. For 1-dimensional systems, this question was answered in the positive by Hastings (arXiv:0705.2024).

Yet, the connection between such systems and complexity theory is very vague: while Hastings' result implies that 1-D area-law-abiding systems can be classically simulated, for general systems this is unknown. So my question is, is the quest to solve the area-law conjecture worthwhile? Or adversarially put, can one come up with a QMA-complete local Hamiltonian which is also area-law-abiding. A small glance at the known QMA-complete local Hamiltonians, which are essentially all based on Kitaev's quantum Cook-Levin theorem yields that these Hamiltonians do not have the area law property.

Improve this question
$\endgroup$
2
  • $\begingroup$ Hit the Enter key too quickly? :) $\endgroup$
    – Daniel Apon
    Nov 17, 2010 at 12:06
  • $\begingroup$ Please ignore my vote to close; Lior filled in the rest of his question! $\endgroup$
    – Daniel Apon
    Nov 17, 2010 at 12:27

2 Answers 2

Reset to default
10
$\begingroup$

One could consider the following slightly silly example of a 2d system which obeys an area law which is QMA-complete. Take a 2d system, one row of which is equal to one of the known QMA-complete 1d Hamiltonians (see Aharonov, Gottesman, Irani, Kempe), and all the other rows are in a product state. Then, this obeys an area law (consider drawing a rectangle which includes the given row, with k rows and l columns; the entanglement is bounded by a constant times l and the area is also at least equal to l).

However, this, in my opinion, certainly doesn't mean that proving an area law in 2d would be pointless from the point of view of complexity. Rather, I think it means that we need to consider not just the area law for entanglement entropy, but other entanglement properties also. One such property would be having a PEPS of polynomial bond dimension. Actually, proving that there is an area law in 2d does not imply having a PEPS of polynomial bond dimension. The implication in 1d relies on the fact that we can cut the system across various bonds, truncate to a polynomial Schmidt rank across each bond, and bound the error. This procedure doesn't work in 2d. So, proving the existence of a PEPS for a gapped system in 2d would be a next step. My feeling is that proving an area law in 2d would be a good first step to doing that.

In fact, it is well-studied in condensed matter physics that there exist gapless 2d Hamiltonians which obey an area law. While in 1d, the systems which are described by conformal field theory have a logarithmic behavior of the entanglement entropy, in 2d many critical systems show an area law and then the logs show up in subleading behavior, so the entropy is equal to L + const*log(L)+... That is, the interesting, universal terms in the entropy are not the leading terms, but the subleading, in such 2d theories.

Improve this answer
$\endgroup$
0
$\begingroup$

Thanks for the detailed and insightful answer, and sharpening the distinction between the area-law and polynomial bond-dimension.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.