(*This post is based on part of a lecture delivered by Boriana Gjura and Prayaag Venkat. See also posts by Ben Edelman and Fred Zhang for more context on Quantum Hamiltonian Complexity.*)

# Introduction

In this post we present the Area Law conjecture and prove it rigorously,

emphasizing the emergence of approximate ground state projectors as a

useful and promising tool.

The difficulty of understanding many-body physics lies in this dichotomy

between the power of quantum on the one hand, and the fact that even

describing a quantum state requires exponential resources on the other.

A natural way to proceed is to ask if the special class of physically

relevant states admits succinct descriptions. As seen in a previous

post, the QMA-completenes of the -local Hamiltonian problem suggests

that even ground states of local Hamiltonians do not admit such

descriptions. Looking at these ground states, the following questions

arise naturally.

*When do the ground states of local Hamiltonians have a special
structure?*

*When does that structure allow for a meaningful short*

description?

description?

*When does that structure allow us to compute properties*

of them?

of them?

As stated informally, the answer to these questions is yes for (gapped)

1D systems, and it is an open problem to answer these in higher

dimensions.

# The Area Law

The Area Law is inspired by the Holographic principle in Cosmology,

which informally states that the total information in a black hole

resides on the boundary. That is, the complexity of the system depends

on the size of its boundary, not its volume.

## Preliminaries

For the sake of clarity, we assume that is a

2-local Hamiltonian on qubits, each is a

projection , is frustration free, (meaning that

, the lowest eigenvalue, is zero) and there is a unique

ground state .

These conditions simplify our proof. It will be easy to generalize to

and relaxing to -local on qudits (dimension

particles). The most significant assumption is that is

frustration-free: more work is necessary to make the proof work

otherwise.

To formalize our conjecture, we define a notion of von Neumman entropy

below.

Definition:Consider any state lying in a bipartite Hilbert space

, and perform a Schmidt

decomposition to obtain

.

The Von Neumann entanglement entropy of across region A

is defined as

Why is this a good notion of entropy? If

, then

, i.e. the product state has no entanglement. On

the other hand, the maximally entangled state

has entropy . In general, we have that

This is a

direct quantum generalization of the fact that a classical probability

distribution on elements has entropy at most , and this is

achieved by the uniform distribution.\

We can now state the Area Law.

Conjecture:Let be the ground state of , as defined above.

Then for any region (i.e. a subset of qubits),

where

denotes the boundary of the region , the set of qubits that interact

through with at least a qubit outside of region .

This conjecture is illustrated by the following figure.

We prove the 1-D version of this conjecture. Note that for a 1D system

(i.e. qubits on a line with nearest neighbor interactions) it suffices

to consider bipartitions of the Hilbert space defined by a “cut” (see

the figure below). By a cut, we mean a partition of the qubits into two

sets consisting of all the qubits to the left and right, respectively,

of a fixed qubit .

Theorem:Let be as above. Then for any cut ,

## Approximate Ground State Projectors

In the case where all commute, consider the operator

. This operator will project any product state

onto the ground state. Therefore, we can get a representation of the

ground state as a matrix product state (as we saw in a previous post on

tensor networks). Can we generalize this idea when the do not

necessarily commute?

A natural idea is to define an operator that approximately projects a

state onto the vector we want (the ground state), while shrinking it on

the other directions. We also want this operator to not increase

entanglement too much. The proof of the area law will involve

constructing a low-rank tensor approximate factorization of the ground

state by starting with a factorized state, which has a good overlap with

the ground state, and then repeatedly applying such an operator.

We first give a formal definition of an approximate ground state

projector. In the following, under the assumption of the existence of

such an object, we will prove the area law. At the end, we will show how

to construct it.

Definition:is a –approximate ground state projection(AGSP) if:

1.

2. For every such that

, then

.

3. has entanglement rank at most . That is, admits a Schmidt

decomposition of the form ,

where and act only on the particles to the left and

right of the cut, respectively.

The first step of the proof of the Area Law is to find a product state

that has a good overlap with the ground state. That is, it should have a

constant overlap that is not dependent on , the number of particles

in the system.

Lemma 1:Suppose there exists a -AGSP such that

. Fix a partition of the space

on which the Hamiltonian acts. Then there exists a product state

such that

**Proof:**

Let be a product state with the largest overlap in

, meaning that it maximizes.

and can be written as

where the latter is some state orthogonal to the ground state. We apply

to get

where and is normalized. By

the properties of the operator , the decomposition of

has at most terms. Using the Cauchy-Schwarz

inequality:

Therefore there exists a product state such that

,

which implies that , as desired.

Starting with a product state with a big enough overlap with the ground

state, the proof of the next lemma shows how we can repeatedly apply

AGSPs to bound the entropy across the cut.

Lemma 2:Suppose there exists a -AGSP such that

, and a product state

such that

. Then

But before we prove this, let’s state an intuitive result of Eckart and

Young, which provides an upper bound for the overlap of two states given

the Schmidt rank of one.

Lemma (Eckart-Young):Let be a normalized

vector with Schmidt decomposition

, where

. Then for any normalized

it holds that

Using this result, we continue the proof.

**Proof of Lemma 2:**

Write the -AGSP as . Given a state , we

denote by the normalized stated after applying

projections on the state, namely

By the way we’ve defined , the Schmidt rank of

increases by a power of , and this state has an improved overlap with

the ground state, that is:

Let be

the Schmidt decomposition of the ground state relative to the cut

, where . The

Eckart-Young theorem gives:

from which

We choose

such

that . Let’s now bound the

worst case entropy accross the AGSP cut. The first Schmidt

coefficients account for an entropy of at most . For the

remaining coefficients, we group them in chunks of size in

intervals indexed by . For each of

these intervals, the corresponding entropy can be upper bounded by

where here is an upper bound on the total

probability mass in the interval, and a lower bound on

the size of any Schmidt coefficient (squared) in the interval. This

follows from the fact that they are organized in descending order and

must sum to 1.

Therefore, the total entropy is

This bound depends on and . This is sufficient to imply the

Area Law because our AGSP constructions will have constant and

.

# AGSP Construction

In this section, our goal is to construct an AGSP with the correct

tradeoff in parameters. We briefly recall the intuition behind the

properties that an AGSP must satisfy. First, the AGSP should leave the

ground state untouched. Second, it shrinks states which are orthogonal

to the fround state. Third, it should not increase the entanglement

across the cut by too much (see the figure below).

A depiction of the third property in the AGSP definition for a 1D

system. The property that is a sum of tensor products of operators

which only act on one “side” of the

system.

We are interested in understanding a construction of an AGSP for three

reasons:

- As we saw before, we can prove a 1D area law assuming the existence

of an AGSP with good parameters. - AGSPs have been used a building block in an provably polynomial-time

algorithm for finding ground states of gapped 1D local Hamiltonians. - They appear to be a general purpose tool with potential applications

in other contexts.

## Details of the construction

One way to think about the the first two properties in the AGSP

definition is in terms of the relationship of the eigenvalues of and

the eigenvalues of (see the figure below). The first property says

that the ground state of should be an eigenvector of with

eigenvalue 1. The second property says that all other eigenvectors of

should be mapped to eigenvectors of with eigenvalue at most

.

In this plot, the horizontal axis represents the eigenvalues of

and the vertical axis represents the eigenvalues of . The ground

state of , which corresponds to the eigenvalue 0, should remain fixed

upon applying to

it.

In the following, we will aim to construct and AGSP whose tradeoff in

parameters allows us to achieve the following result.

Theorem:.

### Attempt 1

As a first attempt, we will evaluate the quality of the following

operator:

where is some natural

number that we will decide upon later. We now check the three properties

for this particular choice of .

First, it is clear that does not change the ground state, since the

ground state is an eigenvector of with eigenvalue 0

(frustration-free case). Second, because any other eigenvalue of is

at least (the energy gap), we have that

.

Third, for the time being, let us think of as roughly corresponding

to (we will formalize this later).

Unfortunately, these values and will not allow us to

achieve the desired tradeoff of . To see why

this is, observe that because we have local Hamiltonians, the term

could be on the order of (recall that

), so we would need to choose proportional

to to reduce to a constant (see figure below). Unfortunately, this will result in a

corresponding increase in , violating .

The first attempt an AGSP corresponds to the polynomial is depicted in

blue. This polynomial does not decay at a fast enough rate, so the

second attempt will replace it with another polynomials, depicted in

red, which decays much

faster.

### Attempt 2

In summary, the two weaknesses of the previous approach we need to

address are:

- The large term in the exponent substantially reduces the

shinking effect of applying the AGSP. We will address this using the

technique of*Hamiltonian truncation.* - For a fixed (roughly corresponding to the entanglement rank of

), the function does not decay

fast enough after the point (which is the ground state

energy). We will address this using*Chebyshev polynomials*.

As discussed before, the term is large because it involves

contribution from all local Hamiltonians. Intuitively, we might

believe that only the local Hamiltonians near the site of the cut itself

should play a large role in the entanglement of the ground state across

the cut. Specifically, if we write

, where

are the local Hamiltonians neighboring the cut and

and are the “aggregrated” Hamiltonians of all the remaining local

Hamiltonians to the left and right, respectively, of and

, then we are asserting that and contribute

significantly to but are not important when trying to

characterize the ground state (see figure below).

We keep track of the local Hamiltonians corresponding to the

qudits directly surrounding the cut. The remaining local Hamiltonians

are aggregated into the Hamiltonians and , whose eigenvalues

will be truncated to define

.

Mathematically, if we let

, where

denotes operator obtained by truncating all eigenvalues

of to be at most , we claim the following:

Claim:

1.

2. is a ground state of .

3. has gap

It is straightforward to verify the two first two claims, We omit the

proof of the third claim. Intuitively, we have chosen to be an

approximation of which has much smaller norm.

Next, we come to the task of designing a degree- polynomial which

decays faster than our first attempt

after the point . In other words, we would like to satisfy

(fixing the ground energy) and map the interval

to the interval for as small a

as possible. It turns out that the degree- Chebyshev

polynomial (of the first kind) is precisely the polynomial which has

this behavior (see the appendix for a review of Chebyshev polynomials).

Letting denote the degree- Chebyshev polynomial, we take our

polynomial to be a scaled and shifted version of it:

Given this definition of , we take our new candidate AGSP to be

, which has the following guarantees:

Claim:

1.

2. achieves

3. achieves

The first claim is straightforward to verify. The proof of the second

claim is ommitted; it involves calculations making use of standard

properties of Chebyshev polynomials. We remark that the dependence of

the exponent on has been reduced by a quadratic

amount, compared with the first attempt at an AGSP. We now sketch the

main ideas behind the proof of the third claim. After that, we will

choose values of and so that the desired tradeoff is

achieved.

We have defined as a degree- polynomial in , so we may write

it as: where are coefficients

whose particular values are not relevant to the analysis of the Schmidt

rank of across the given cut. It is straightforward to check that

the Schmidt rank of is bounded by the sum of the ranks of the

monomials (subadditivity). So, it suffices to analyze the

Schmidt rank of the monomial of the largest degree, .

From our expression for , we can expand this power to get:

where the summation is over all products of Hamiltonians from the

set . Now, one

natural approach to proceed is to analyze the Schmidt rank of each term

in the summation, and then sum over all the terms. Unfortunately, this

approach will not work because there are exponentially many terms in the

summation, so our estimate of will be too large. To address this

issue, it is possible to collect terms cleverly so that the total number

of terms is small. However, we will not provide the details here; we

will just sketch how analyze the Schmidt rank of an individual term.

The term consists of a product of

Hamiltonians. Since there are possible locations of a cut that is

crossed by one of the , an average cut will have

of the crossing it. For each Hamiltonian which

crosses this average cut, the Schmidt rank will be multiplied by a

factor of . Hence, the Schmidt rank of the term

is . This bound on the

Schmidt rank is for an average cut , not necessarily the cut we

fixed in the beginning. The two cuts are separated by at most

qudits because is one of the cuts surrouding (see figure

below), so one can relate the Schmidt rank across these two cuts. For

each Hamiltonian between the two cuts, the high-level idea is that the

entanglement rank is multiplied by at most a factor of . Because the

entanglement rank across is , the entanglement

rank across is .

The entanglement across cut is analyzed bounding the entanglement

across a nearby cut and then relating the

two.

Putting all the pieces together, we have that:

- By Hamiltonian truncation and the Chebyshev polynomial construction,

. - By the entanglement rank analysis, .

One can now check that if we set and

(where large enough constants are

hidden inside the ), then we achieve the desired tradeoff of

. Note that and are constants because

and are constants.

## Towards an area law in high dimensions

One of the major open problems in this line of work is to prove an area

law for 2D systems. We now discuss one potential line of attack on this

problem, based on a reduction to the 1D area law we have proven using

AGSPs.

Consider a 2D system, as depicted in the figure below. We can form a

sequence of concentric shells of qudits of increasing radii and

“contract” each shell into a single qudit of higher dimension. That is,

if each of the original qudits have dimension and we consider the

shell at radius , the dimension of the contracted qudit is roughly

because there are roughly qudits in the shell. The system of

contracted qudits is now a 1D system in the sense that the shell at

radius only interacts with the shells at radii and .

A 2D system can be reduced to a 1D system by decomposing it into a

sequence of concentric

“shells”.

Suppose that we were able to show an area law as discussed previously,

but with the following dependence on :

If we replace

with , the dimensionality in our new 1D system, we get that

which is exactly an

area law in 2D (recalling that surface area of a circle is proportional

to its radius). In fact, even the weaker result of proving that

for

some would imply a “sub-volume law”, already a major

breakthrough. This suggests that constructing AGSPs with better

parameters may be a plausible approach to proving an area law.

# Future Directions

In addition to proving an area law in 2D, there are several interesting

questions raised by what we discussed here. See the survey of Gharibian

et al. for more details.

- Do area laws hold for gapless (i.e. non-constant gap, or “critical”)

systems? No, there are known counterexamples. - Do area laws hold for degenerate systems (where the ground state is

not unique)? Yes, the AGSP approach still works for systems with

groundspaces of constant dimension. It is unknown whether area laws

hold when the groundspace is of dimension polynomial in . - Can one design practical algorithms for finding ground states of

gapped 1D local Hamiltonians? Yes, there is one approach based on

AGSPs. - Do area laws hold in general for systems where the interactions are

not necessarily described by a lattice? No, there are known

counterexamples to such a “generalized area law”?

# Acknowledgements

We would like to thank Boaz Barak and Tselil Schramm for their guidance

in preparing the talk on which this post is based.

Most of this post (including some figures) draws heavily upon the

following resources: lecture notes from courses taught by Thomas Vidick and Umesh Vazirani,

repectively, and a survey by Gharibian et al.

In these notes, we have opted to illustrate the main ideas, while

glossing over technical details. Our goal with this approach is to

prepare the reader to more easily understand the original sources and

highlight the some of the key concepts.

# Appendix: Background on Chebyshev Polynomials

The Chebsyhev polynomials are a family of

polynomials with many special properties. They are defined as

, and

The first few polynomials are plotted below (Source:

<https://en.wikipedia.org/wiki/Chebyshev_polynomials>).

Below, we state a property (proof ommitted) which provides some

intuition as to why Chebyshev polynomials are the “correct” choice for

our construction. Intuitively, it says that among all degree-

polynomials which are trapped inside on the interval ,

dominates outside of .

Claim:Let be a degree- polynomial

such that for all . Then for all

, .

# References

- Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin, et al. “Quantum Hamiltonian Complexity”. Foundations and Trends in Theoretical Computer Science, 10(3):159–282, 2015.
- Thomas Vidick. Lecture notes for CS286 seminar in computer science: “Around the quantum PCP conjecture”. http://users.cms.caltech.edu/~vidick/teaching/286_qPCP/index.html, Fall 2014.
- Umesh Vazirani. Lecture notes for CS294-4 “Quantum computation”. https://people.eecs.berkeley.edu/~vazirani/f16quantum.html, Fall 2016.

## 3 thoughts on “A 1D Area Law for Gapped Local Hamiltonians”