The information-theoretic view on quantum matter has had widespread impact in physics. For instance, tools from quantum Shannon theory have provided insights into the black-hole paradox [26] and the notion of topological entanglement entropy has been crucial for understanding and classifying phases of matter [28]. This viewpoint has also permeated the computational side of condensed matter physics, and has led to the identification of entropic properties known as the area laws, which are hallmarks of classical simulability in many physically relevant settings. A state of a lattice spin system is said to satisfy an area law if its entanglement entropy with respect to any bipartition scales with the size of its boundary. This restricts the quantum correlations arising in the state, and enables an efficient classical representation of the state for one-dimensional (1D) lattice systems [36]. A breakthrough result of Hastings [24] established an area law for gapped ground states in one dimension. Subsequent improvements were obtained in Refs. [8,9] using new tools from combinatorics and approximation theory. This led to an efficient classical algorithm for computing ground states [10,30], providing a rigorous justification for the success of the DMRG algorithm [37]. Recently, area law was also shown for the ground states of 1D long range hamiltonians [29].
The area law conjecture for two or higher dimensional systems has remained a significant open question, see e.g., Refs. [13,17,20,32]. It can be motivated by the following "locality intuition":
Locality of correlations in the vicinity of the boundary of a region should imply an area law for the region.
In particular, this suggests that the area law should hold for gapped ground states since they possess a finite correlation length [23]. Whether or not this intuition can be made rigorous remains to be seen [25]. While correlation decay has been shown to imply an area law in 1D [14], the locality intuition has no formal support in higher dimensions.
In this work, we prove that the unique ground state of any frustration-free, locally gapped 2D lattice spin system satisfies an area law scaling of entanglement entropy with respect to a vertical cut that partitions the system into left and right regions, see Fig. 1.
Theorem 1.1 (Informal). Consider a locally gapped, frustration-free Hamiltonian with geometrically local interactions in 2D and a unique ground state. The ground state entanglement entropy with respect to a vertical bipartition of length 𝑛 is at most 𝑛 1+𝑂 1 polylog (𝑛) .
A frustration-free quantum spin system has the property that its ground state has minimal energy for each term in the Hamiltonian. Such a system is said to be locally gapped if there exists a positive constant that lower bounds the spectral gap of any subset of the local Hamiltonian terms. We believe that our techniques readily generalized to rectangular bi-partitions on the lattice. This can then be used to prove area laws for other bi-partitions via appropriate tiling, including those featuring gapless edge excitations [11]. Using the techniques introduced in [10] and further developed in [1], Theorem 1.1 readily extends to degenerate ground states. We note that a previous work [18] established the area law for the special case of spin-1/2 frustration-free systems, using an exact characterization of the ground space from Ref. [15]. The area law is known to be false on general graphs [3,7].
The proof of Theorem 1.1 is obtained via new insights in the approximation theory of quantum ground states. For a Hamiltonian with unique ground state |Ω⟩, an 𝜖-approximate ground state projector (AGSP) is an Hermitian operator 𝐾 such that 𝐾 |Ω⟩ = |Ω⟩ and ∥𝐾 -|Ω⟩⟨Ω|∥ ≤ 𝜖. In Ref. [9] it has been shown that an AGSP with small error 𝜖 and low entanglement with respect to a given bipartition of the lattice -as measured by its Schmidt rank SR(𝐾) 1 -implies an upper bound on the entanglement of the ground state itself across the bipartition. In particular, Ref. [9] shows that if 𝜖 • SR(𝐾) ≤ 1/2 then the entanglement of the ground state is at most 𝑂 (1) • log(SR(K)), see the full version [5,Theorem 4.1] for a precise statement. In this way the study of entanglement in quantum ground states can be reduced to the study of entanglement in low-error AGSPs. We consider AGSPs which are multivariate polynomial functions
In general, this kind of polynomial is a linear combination of monomials of the form
As discussed above, in order to bound the entanglement of the ground state, it suffices to construct an AGSP with sufficiently small error and sufficiently small entanglement. Moreover, the techniques 1 The Schmidt rank SR(𝐾) of an operator 𝐾 with respect to a bipartition of the system is the minimal number 𝑅 of tensor product operators 𝐴 𝛼 ⊗𝐵 𝛼 such that 𝐾 = 𝑅 𝛼 =1 𝐴 𝛼 ⊗ 𝐵 𝛼 . of Ref. [8] suggest that polynomial degree can be taken as a proxy for entanglement in AGSPs of this type. Thus, we ask: what is the minimal polynomial degree 𝑠 needed to approximate the ground state projector to within a given error 𝜖?
Following Ref. [8], it is instructive to consider the special case in which our AGSP (1) can be expressed as 𝐾 = 𝑝 (𝐻 ) where 𝑝 is a univariate polynomial. This kind of AGSP has the nice feature that it commutes with 𝐻 and can therefore be diagonalized in the same basis. Using this fact we see that such a polynomial is an 𝜖-AGSP iff
Here .
(
This scaling of error with degree is optimal, a consequence of the extremal property of Chebyshev polynomials [33,Proposition 2.4].
Here we did not use any properties of the Hamiltonian except the fact that Spec(𝐻 ) ⊆ [𝛾, 𝑛]. We see that a spectral gap lower bounded by a positive constant ensures a good 𝜖 = 𝑂 (1) approximation by a 𝑂 ( √ 𝑛)-degree polynomial. This form of locality in the ground state is somewhat distinct from finite correlation length.
Remarkably, the tradeoff Eq. ( 3) between polynomial degree and error can be improved in certain important special cases. For example, suppose the Hamiltonian terms are commuting projectors, i.e., [𝐻 𝑖 , 𝐻 𝑗 ] = 0 and 𝐻foot_0 𝑖 = 𝐻 𝑖 . In that case the problem of approximating the ground state is formally equivalent to the problem of approximating the multivariate AND function of 𝑛 binary variables (equivalently, the OR function), see the full version [5, Section 3.1] for details 2 . The distinguishing feature of the commuting case for our purposes is that, crucially, all eigenvalues of 𝐻 are integers between 0 and 𝑛 and by exploiting the fact that Spec + (𝐻 ) ⊆ {1, 2, . . . , 𝑛} one can construct a suitable univariate polynomial 𝑝 that achieves Eq. ( 2) with
This improves upon Eq. ( 3) in the low-error regime 𝑠 ≫ √ 𝑛 and is known to be optimal in the commuting case [27].
More generally, for a collection of possibly non-commuting operators {𝐻 𝑗 } 𝑛 𝑗=1 let us call a degree-𝑠 multivariate polynomial AGSP (1) optimal if the approximation error matches Eq. ( 4). Our first result establishes that one-dimensional frustration-free locallygapped ground states can be optimally approximated in this sense.
Theorem 1.2 (Optimal approximation of 1D ground states, informal). For any constant 𝛿 ∈ (0, 1/2) and 𝑠 ∈ ( √ 𝑛, 𝑛 1-𝛿 ), there is a degree 𝑂 (𝑠) polynomial which approximates the ground state projector of a locallycally gapped 1D frustration-free quantum spin system to within error Eq. ( 4).
We emphasize that the AGSP in the above theorem is a multivariate polynomial of the form (1), and as far as we know cannot be expressed as a univariate polynomial function of 𝐻 . This is because we may have [𝐻 𝑖 , 𝐻 𝑖+1 ] ≠ 0, and -in contrast with the commuting case -the spectrum Spec + (𝐻 ) does not appear to have a nice characterization that allows us to improve upon Eq. ( 3) by a suitable choice of univariate polynomial 𝑝. We construct our AGSP via a recursive application of the robust polynomial method of Ref. [4] (where a subvolume law for the same class of systems was shown). The resulting polynomial, which is detailed in the full version [5, Section 3.2], has a structure which is reminiscent of a renormalization group flow.
Although it concerns 1D systems, Theorem 1.2 turns out to be just what we need to establish the area law in two dimensions. The key insight is captured by the following modified locality intuition that we propose, which asserts a direct link between linear-degree optimal polynomial approximations and area laws:
A linear-degree optimal polynomial approximation for the ground state in the vicinity of the boundary of a region should imply an area law for the region.
Here we mean linear in 𝑛, the number of inputs of the multivariate polynomial (cf. Eq. ( 1)). To understand where this comes from, suppose we can construct an optimal linear-degree polynomial 𝑃 that approximates the ground state projector and is localized in a width ∼ 𝑤 neighborhood of the boundary of the bipartition of interest (here we are intentionally vague about the meaning of localized, see the full version [5, Section 4] for details). Thus, the degree of 𝑃 is ∼ 𝑤 • area and its error is 𝜖 ≤ 𝑒 -Ω (𝑤 •area) , where 'area' is the size of the boundary. Now consider an AGSP 𝐾 = 𝑃 𝑞 for some positive integer 𝑞. The total polynomial degree of 𝐾 is thus 𝐷 = 𝑞𝑤 • area, and its error is 𝜖 ′ = 𝜖 𝑞 ≤ 𝑒 -Ω (𝑞𝑤 •area) . Now we shall assume that the polynomial 𝐾 𝑞 is nicely behaved in a certain sense first identified in Ref. [9]. In particular, we assume that its Schmidt rank is amortized over the width 𝑤 neighborhood of the boundary, in that it scales as SR ∼ 𝑒 𝑂 (𝐷/𝑤+𝑤 •area) . Choosing 𝑞 = Ω(𝑤) (say) and letting 𝑤 be a large constant, we can ensure 𝜖 ′ • SR ≤ 1/2, with log(SR) = 𝑂 (area). Thus, applying the aforementioned method from Ref. [9] we would obtain the desired upper bound 𝑂 (area) on the ground state entanglement entropy.
Since the boundary of a region on a 2D lattice is one-dimensional, the above argument suggests that the 2D area law should follow from optimal linear-degree polynomial approximations in 1D. To make this work, we show how our 1D approximation can be used "in the vicinity of the boundary of the region" and we relate the entanglement of the resulting AGSP to the polynomial degree. The area law is then established using the aforementioned method from Ref. [9]. The astute reader may note that Theorem 1.2 does not quite provide a linear-degree optimal polynomial as the degree must be 𝑛 1-𝛿 for some 𝛿 ∈ (0, 1/2); a careful treatment of the 𝛿 → 0 limit leads to the slight deviation 𝑛 1+𝑜 (1) from area law behaviour in Theorem 1.1.
Discussion. There are at least three significant questions left open by our work. Firstly, one may ask if the assumption of a local spectral gap can be removed or replaced with one concerning the global spectral gap of the Hamiltonian. We believe that this could lead to a generalization of our techniques to frustrated systems. To make progress here may require a deeper understanding of the interplay between the local spectral gap and the gap of the full hamiltonian. Secondly, it is natural to ask if ground states of locally gapped frustration-free systems can be approximated by efficiently representable tensor networks such as PEPS of small bond dimension [35]. While it is known that a 2D area law does not imply such a representation [21], a more detailed study of the optimal polynomial approximations considered here may provide insight into this question. Finally, a natural open question is to extend our results to local hamiltonian systems on higher dimensional lattices. As mentioned earlier, this is closely related to the question of approximating ground states by linear-degree optimal polynomials.
In this section we describe methods for approximating multivariate functions by polynomials. We first describe polynomial approximations with real-valued variable inputs. Then we generalize these methods to the local Hamiltonian setting by allowing operatorvalued inputs.
Following Ref. [4] we shall build polynomial approximations by combining two well-known ingredients: the univariate Chebyshev polynomials and a robust polynomial [34].
We will use a rescaled and shifted Chebyshev polynomial defined as follows. For every 𝑠 ∈ R ≥0 and 𝜂 ∈ (0, 1) we define a polynomial
where 𝑇 𝑗 is the Chebyshev polynomial of the first kind. To ease notation later on, the parameter 𝑠 which determines the degree is not required to be an integer. The polynomial Eq. ( 5) has the following property which is a direct consequence of Lemma 4.1 of Ref. [8].
). For every 𝑠 ∈ R ≥0 and 𝜂 ∈ (0, 1) we have 𝑇 𝜂,𝑠 (0) = 1 and
Next, we describe the robust polynomial. Our starting point is the function 𝐵 : [0, 1] → {0, 1} defined by
.
This function rounds 𝑥 to a bit in a one-sided fashion. Using (6) we define a (one-sided) "robust product" that takes real inputs 𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑚 ∈ [0, 1] and outputs 1 if and only if they are all equal to 1:
We note that since 𝐵(𝑥 𝑗 ) 2 = 𝐵(𝑥 𝑗 ) we may also express Eq. ( 7) as Rob(𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑚 ) = 𝐵(𝑥 𝑚 )𝐵(𝑥 𝑚-1 ) . . . 𝐵(𝑥 1 ) 𝐵(𝑥 1 )𝐵(𝑥 2 ) . . . 𝐵(𝑥 𝑚 ) .
The left-right symmetric expression will be useful to us momentarily when we extend the definition of the function to allow operatorvalued inputs.
The robust polynomial of interest is an approximation to Eq. ( 7). To this end, let
Note that for any 𝑥 ∈ [0, 1] we have 𝐵(𝑥) = lim 𝑖→∞ 𝑖 𝑗=1 𝐵 𝑗 (𝑥). Define
The above expression is obtained by starting with Eq. ( 8), substituting 𝐵 ← ∞ 𝑗=1 𝐵 𝑗 , and then truncating the summation so that the total degree of the polynomial is at most 3𝑚 (this is somewhat arbitrary). This polynomial is a good approximation to Rob in the following sense.
Let us now extend our definitions from the previous section to allow operator-valued inputs. Suppose 𝑂 is a Hermitian operator with all eigenvalues in the interval [0, 1]. The operator-valued Chebyshev polynomial 𝑇 𝜂,𝑠 (𝑂) is defined in the usual way by substituting 𝑥 ← 𝑂 in Eq. (5). By applying Lemma 2.1 to each eigenvalue of 𝑂, we obtain the following. Lemma 2.3. Let 𝑠 ∈ R ≥0 and 𝜂 ∈ (0, 1). Suppose that 𝑂 is an Hermitian operator with eigenvalues in the interval {0} ∪ [𝜂, 1] and let Π be the projector onto the nullspace of 𝑂. Then 𝑇 𝜂,𝑠 (𝑂)Π = Π and ∥𝑇 𝜂,𝑠 (𝑂) -Π∥ ≤ 2𝑒 -2𝑠 √ 𝜂 .
For the robust polynomial, we start by defining 𝐵(𝑂) to be the projector onto the eigenspace of 𝑂 with eigenvalue 1. For Hermitian operators 𝑂 1 , 𝑂 2 , . . . , 𝑂 𝑚 such that each 𝑂 𝑖 has eigenvalues in the interval [0, 1], we define a Hermitian robust product which generalizes Eq. ( 8):
where
Note that due to the possible non-commutativity of the {𝑂 𝑖 } operators, Rob(𝑂 1 , 𝑂 2 , . . . , 𝑂 𝑚 ) is generally not the projector onto the intersection of the +1 eigenspaces of these operators.
We also define the operator-valued polynomial 𝐵 𝑖 (𝑂) for positive integers 𝑖 by substituting 𝑥 ← 𝑂 in Eq. ( 9). The robust polynomial is defined in parallel with (10)
One can easily check that the operator in Eq. ( 11) is Hermitian. The following error bound is established in the full version [5].
Throughout this section we consider the following scenario. We are given a set of Hermitian operators
which act on some finite-dimensional Hilbert space H . We are interested in the nullspace of the operator
Let us write Π for the projector onto the nullspace of 𝐻 . In other words, Π projects onto the intersection of the nullspaces of all operators 𝐻 𝑗 (we are interested in the case where Π is nonzero).
Our goal is to approximate Π by a low-degree polynomial in the operators {𝐻 𝑗 }.
In Sec. 3.1 and Sec. 3.2 we work in a general setting and in particular we do not assume a tensor product structure of the Hilbert space H or geometric locality of the operators {𝐻 𝑗 }. In Sec. 3.1 we consider the simplest case in which all operators 𝐻 𝑗 are mutually commuting and we describe the known optimal tradeoff between approximation degree and error. Then, in Sec. 3.2 we show that optimal approximations can be obtained more generally for noncommuting operators which satisfy certain gap and merge properties. These properties themselves assert a kind of one-dimensional structure with respect to the given ordering 1 ≤ 𝑗 ≤ 𝑛 of the operators. In Sec. 3.3 we describe how a direct application of these results provides optimal ground state approximations for one-dimensional, locally-gapped, frustration-free qudit Hamiltonians. Later we will see how the results of Sec. 3.2 can provide low-entanglement approximations of ground states in the 2D setup.
We begin with the easy case in which all {𝐻 𝑖 } are commuting projectors:
In this case (𝐼 -𝐻 𝑖 ) is the projector onto the nullspace of 𝐻 𝑖 , and due to the commutativity Eq. ( 13) we may express Π exactly as the degree-𝑛 polynomial Π = 𝑛 𝑖=1 (𝐼 -𝐻 𝑖 ). Our goal is to construct a lower degree polynomial 𝑃 that approximates Π. Since all operators {𝐻 𝑖 } commute and have {0, 1} eigenvalues, we may work in a basis in which they are simultaneously diagonal and the problem reduces to that of approximating the product of binary variables 𝑥 ∈ {0, 1} 𝑛 which label the eigenvalues of {𝐼 -𝐻 𝑖 } 𝑛 𝑖=1 . (Note that here we do not require any properties of the basis which simultaneously diagonalizes these operators, only that it exists). In other words, the problem of approximating the ground space projector for a Hamiltonian which is a sum of commuting projectors, reduces to the problem of approximating the boolean AND function
We are faced with the task of constructing a multilinear polynomial 𝑝 which 𝜖-approximates AND in the sense that |𝑝 (𝑥)-AND(𝑥)| ≤ 𝜖 for each 𝑥 ∈ {0, 1} 𝑛 . Remarkably, it is possible to achieve an arbitrarily small constant error 𝜖 = 𝑂 (1) using a polynomial of degree 𝑂 ( √ 𝑛) [31]. For example, one can use the Chebyshev polynomial 𝑇 1/𝑛,𝑠 1 𝑛 𝑛 𝑖=1 𝑥 𝑖 of degree ⌈𝑠⌉ which achieves an approximation error 𝜖 = 𝑒 -Ω(𝑠/ √ 𝑛) as can be seen from Lemma 2.1. Similarly, the acceptance probability of the standard Grover search algorithm [22], viewed as a function of the input bit string 𝑥 provided as an oracle, constructs such an approximating polynomial [12]. However, neither of these polynomials has optimal degree in the low-error regime where 𝜖 decreases with 𝑛. In that regime an optimal polynomial can be constructed via a low-error refinement of Grover search [16,19] (see also Ref. [27]).
Here we provide a different family of polynomials that give an optimal approximation to the AND function. These polynomials are obtained in a simple way by combining the Chebyshev polynomial 𝑇 𝜂,𝑠 and the robust polynomial Rob from Sec. 2.1. Soon we will see how this construction can be extended to the non-commuting case. It is unclear to us whether one can alternatively extend the known optimal polynomials constructed in Refs. [16,19,27]. Theorem 3.1 (Optimal approximation of AND). Let 𝑛 be a positive integer. For every real number 𝑠 ∈ √ 𝑛, 𝑛 , there exists a polynomial 𝑃 (𝑥) of degree 𝑂 (𝑠) such that
𝑛 ) for all 𝑥 ∈ {0, 1} 𝑛 .
Proof. Define the positive integer 𝑡 = ⌈ 𝑛 2 𝑠 2 ⌉ and note that 1 ≤ 𝑡 ≤ 𝑛 due to the specified bounds on 𝑠. Let 𝑝 (𝑦)
for all
Since 𝑡 ≤ 𝑛, we may construct a partition
where 𝜉 def = ⌈𝑛/𝑡⌉ and |𝐼 𝑘 | ≤ 𝑡 for all 1 ≤ 𝑘 ≤ 𝜉. Our polynomial approximation to AND is defined as
Now we observe that the 𝑘th input to the Rob function on the RHS approximates the AND of all bits in the set 𝐼 𝑘 . To see this, note that 1 -1 |𝐼 𝑘 | 𝑗 ∈𝐼 𝑘 𝑥 𝑗 = 0 when 𝑥 𝑗 = 1 for all 𝑗 ∈ 𝐼 𝑘 , and
Using this fact and Eq. ( 14), we see that for each 1 ≤ 𝑘 ≤ 𝜉 we have
Now applying Lemma 2.2 with 𝜀 = 1/20, and noting that Rob(𝑥) = AND(𝑥) we see that, for each 𝑥 ∈ {0, 1} 𝑛 ,
The degree of the polynomial is at most 3𝜉 • 2
We now consider a more general case in which the operators {𝐻 𝑗 } 𝑛 𝑗=1 still satisfy (12), but may not be projectors and are not assumed to commute. For any subset 𝑆 ⊆ [𝑛] of the operators, we define the corresponding Hamiltonian
and the projector Π 𝑆 onto its nullspace. Similarly, we define gap(𝐻 𝑆 ) to be the smallest nonzero eigenvalue of 𝐻 𝑆foot_1 . A crucial difference between our setting here and the commuting setting considered previously, is that a product Π 𝑆 Π 𝑇 is not in general equal to Π 𝑆∪𝑇 .
We require our operators to satisfy two properties which are defined with respect to the given ordering 1 ≤ 𝑗 ≤ 𝑛. To describe these properties it will be convenient to define an interval as a contiguous subset { 𝑗, 𝑗 + 1, . . . , 𝑘 -1, 𝑘 } ⊆ [𝑛]. The gap property states a lower bound Δ on the smallest nonzero eigenvalue of any interval Hamiltonian 𝐻 𝑆 . The merge property asserts that Π 𝑆 Π 𝑇 ≊ Π 𝑆∪𝑇 for overlapping intervals 𝑆,𝑇 , with error decreasing exponentially in the size of the overlap region. We now state these properties more precisely. Definition 3.2. Operators {𝐻 𝑗 } 𝑛 𝑗=1 satisfy the gap and merge properties if, for some Δ ∈ (0, 1], the following conditions hold for all intervals 𝑆 ⊆ [𝑛] and any partition 𝑆 = 𝐴𝐵𝐶 into three consecutive intervals:
Note that the parameter Δ in this definition appears in both the gap and merge properties. One could alternatively consider a more general definition where each of these properties has its own parameter, though we will not need to.
In the following we show that the optimal scaling 𝑒 -Ω 𝑠 2 𝑛 of error with degree 𝑠 can be recovered in this noncommutative setting, by a recursive use of the robust polynomial, with one use of the Chebyshev polynomial and gap property in the base level of the recursion. The analysis uses the merge property to bound the error in the recursion. The following theorem describes our results for the case where the approximation degree scales less than linearly in 𝑛. Theorem 3.3 (Less than linear degree). Suppose {𝐻 𝑗 } 𝑛 𝑗=1 satisfy Eqs. (12,16,17) for some Δ ∈ (0, 1]. Let 𝛿 ∈ (0, 1/4) be fixed and let 𝑠 be a real number satisfying
) There is a degree 𝑂 (𝑠) Hermitian multivariate polynomial 𝑃 in the operators {𝐻 𝑗 } 𝑛 𝑗=1 such that
In the above, the big-O notation hides a constant which depends only on 𝛿. We shall also be interested in a case where 𝛿 is taken very close to 0 and the degree is close to linear. This almost-linear degree approximation will be used to establish the area law for twodimensional spin systems. For that application it will be useful to describe the structure of the polynomial 𝑃 in more detail. To this end, we first define certain families 𝑃 (𝛼, 𝛽) of elementary polynomials as follows. Definition 3.4. For 𝛼, 𝛽 > 0, let P (𝛼, 𝛽) denote the set of polynomials of the form (𝐻 𝑆 1 ) 𝑗 Theorem 3.5 (Near-linear degree). Suppose {𝐻 𝑗 } 𝑛 𝑗=1 satisfy Eqs. (12,16,17) for some Δ ∈ (0, 1] and that 𝑛 ≥ 𝐶Δ -1 , where 𝐶 > 0 is some absolute constant. There exist real numbers
(20) such that the following holds. There exists a Hermitian multivariate polynomial 𝑃 in the operators {𝐻 𝑖 } 𝑛 𝑖=1 of degree at most 𝛼 such that
and such that 𝑃 can be expressed as a linear combination of at most (2𝛼) 𝛽 elements of P (𝛼, 𝛽).
Theorems 3.3 and 3.5 are proven in the full version [5].
As a prototypical application of the results of the previous section, here we specialize to the case of frustration-free one-dimensional quantum spin systems with a local gap. Consider a 1D system of 𝑛 + 1 qudits of local dimension 𝑑 ≥ 2.
The Hilbert space is C 𝑑 ⊗𝑛+1 and the Hamiltonian is 𝐻 = 𝑛 𝑗=1 𝐻 𝑗 , where each operator 𝐻 𝑗 satisfies 0 ≤ 𝐻 𝑗 ≤ 𝐼 and acts nontrivially only on qudits 𝑗 and 𝑗 + 1 (and as the identity on all other qudits). The local gap 𝛾 is defined as the minimum spectral gap of a subset of Hamiltonian terms
By definition, operators {𝐻 𝑗 } 𝑛 𝑗=1 satisfy the gap property Eq. ( 16) with Δ = 𝛾. In the full version [5], we show that the merge property is satisfied with Δ = 𝛾/80 (a consequence of the "detectability lemma" [2,6]). Therefore we may substitute Δ = 𝛾/80 in Theorems 3.3 and 3.5 to obtain optimal approximations to the ground state projector Π, as claimed in Theorem 1.2.
Here we consider a 2D locally gapped, frustration-free quantum spin system along with a bipartition of the qubits into two regions. We use the results of Sec. 3.2 to construct a polynomial approximate ground state projector (AGSP) which has a kind of 1D structure along the boundary of the bipartition. We show that this AGSP has low enough error as a function of its Schmidt rank across the bipartition, to establish the area law as stated in Theorem 1.1 using the method from Refs. [2,8,9].
Consider a system of qudits of local dimension 𝑑 arranged at the vertices of an 𝐿 × (𝑛 + 1) grid with 𝑛 + 1 rows and 𝐿 columns, as shown in Fig. 1. The Hilbert space is C 𝑑 ⊗𝐿 (𝑛+1)
, and we index qudits by their (column, row) coordinates (𝑖, 𝑗) ∈ [𝐿] × [𝑛 + 1]. We consider a Hamiltonian which acts as a sum of local projectors 4
where ℎ 𝑖 𝑗 acts nontrivially only on the qudits in the set {𝑖, 𝑖 + 1} × { 𝑗, 𝑗 + 1}. We assume that 𝐻 0 has a unique ground state |Ω⟩ such that 𝐻 0 |Ω⟩ = 0. Since ℎ 𝑖 𝑗 ≥ 0 , the latter condition is equivalent to the frustration-free property ℎ 𝑖 𝑗 |Ω⟩ = 0 for all 𝑖, 𝑗. Our results depend on the local gap of 𝐻 0 :
(recall gap(𝑀) denotes the smallest nonzero eigenvalue of a positive semidefinite operator 𝑀.) We note that for our purposes it would in fact be sufficient to consider a local gap in which the minimization is restricted to rectangular regions. We consider a bipartition of the lattice into left and right regions, corresponding to a "vertical cut" between a given column 𝑐 and 𝑐 + 1, as depicted in Fig. 1. In the following we write SR(𝑀) for the Schmidt rank of an operator with respect to the cut.
To bound the entanglement entropy of |Ω⟩, we use the powerful method of approximate ground state projectors (AGSP) developed in Refs. [2,8,9,24]. The following theorem is obtained by specializing Corollary III.4 of Ref. [9] to the case of Hermitian 𝐾. We use the results of Sec. 3.2 to construct a suitable AGSP 𝐾. To this end we construct a system of operators {𝐻 𝑗 } 𝑛 𝑗=1 which has the gap and merge properties Eqs. (16,17). See the full version [5] for details. 4 This is without loss of generality. Consider a frustration-free hamiltonian 𝐻 ′ = 𝑖,𝑗 ℎ ′ 𝑖,𝑗 , where 𝑐𝐼 ≥ ℎ ′ 𝑖,𝑗 ≥ 0 are not projectors. Let ℎ 𝑖,𝑗 be the projector onto the span of ℎ ′ 𝑖,𝑗 , so that 𝑐ℎ 𝑖,𝑗 ≥ ℎ ′ 𝑖,𝑗 . The local spectral gap of 𝐻 0 is at least 1 𝑐 times the local spectral gap of 𝐻 ′ and they have the same ground space.
The 𝜖-approximate degree of AND has the remarkable low-error behaviour deg 𝜖 (AND) = 𝑂 ( 𝑛 log(𝜖 -1 ))[16,19]. The log under the square root reflects the fact that the error probability of Grover's search algorithm can be reduced using a better strategy than the naive parallel amplification.
We use the convention that gap(ℎ) = 1 if ℎ = 0.