(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? When does that structure allow us to compute properties
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.