b6b2bb2
POLYNOMIAL PEPS APPROXIMATION OF GAPPED SQUARE-GRID GROUND STATES
================================================================
A self-contained proof, rewritten for a reader who knows linear algebra
and is willing to work. Nothing is cited without being stated.
Version 2. September 2026.
WHAT IS PROVED, IN ONE PARAGRAPH
--------------------------------
Take an L x L grid of spins, each spin living in C^q. Put any Hermitian
Hamiltonian on it built from on-site and nearest-neighbour terms of
size at most J. Suppose the Hamiltonian has exactly one ground vector
Omega (up to phase) and a spectral gap Delta above it. Then Omega is
approximated to error L^{-1} in vector norm, after normalization, by a
projected entangled-pair state (PEPS) on the very same grid, with bond
dimension at most C L^c. The constants C, c depend only on q, J, Delta.
The tensors may be arbitrary complex numbers; nothing is claimed about
computing them or about contracting the network.
HOW TO READ THIS DOCUMENT
-------------------------
Part 0 says what the objects are and gives the shape of the argument
with no proofs. Read it first.
Parts 1-7 are the proof, in the order in which the pieces are used.
Part 8 records exactly what is imported from the area-law companion, so
that no gap in the citation is hidden.
Part 9 is a dependency map and a glossary.
A reader who wants only the logic should read Part 0, then Part 9, then
the first two pages of Part 7.
NOTATION
--------
Everything below is ASCII. Standard shorthand:
C^q the q-dimensional complex Hilbert space
|v| Euclidean norm of a vector
||M|| operator norm of a matrix
||M||_1 trace norm (sum of singular values)
||M||_2 Hilbert-Schmidt norm
Tr trace
id identity map
AB disjoint union of regions A and B
A^{+r} ambient points within sup-distance r of A
diam, dist sup-norm diameter and distance, always
S(A) von Neumann entropy of the marginal on A
I(A:C) mutual information
I(A:C|B) conditional mutual information
F(rho,sigma) root fidelity ||sqrt(rho) sqrt(sigma)||_1
D(rho||sigma) relative entropy
log natural logarithm
O(.) bounded by a constant times the argument, the constant
depending only on q, J, Delta and on explicitly fixed
numerical choices
A "polynomial" quantity is one bounded by C L^c with C, c independent
of L and of the Hamiltonian. Constants written C, c, C_1, ... may be
renamed between occurrences; each depends only on q, J, Delta and on
explicitly fixed numerical parameters.
================================================================
PART 0. THE OBJECTS, THE THEOREM, AND THE SHAPE OF THE PROOF
================================================================
0.1 The lattice and its Hamiltonians
-------------------------------------
Fix an integer q >= 2 and a length L >= 2. The physical system is the
square
Lambda = {1,...,L}^2
with open boundary conditions. Two sites are neighbours when they
differ by 1 in exactly one coordinate. E(Lambda) is the set of
neighbouring pairs ("edges"). The Hilbert space is
H_Lambda = tensor over v in Lambda of C^q.
A Hamiltonian of the class we allow is
H = sum_{v in Lambda} h_v + sum_{e in E(Lambda)} h_e , (0.1)
where each h_v is a Hermitian operator on the site v, each h_e is a
Hermitian operator on the two sites of e, and
||h_v|| <= J, ||h_e|| <= J.
Nothing else is assumed: no translation invariance, no frustration
freeness, no commutativity, no product-state parent.
The two spectral hypotheses are
(G1) H has a unique normalized ground vector Omega, up to phase,
with ground energy E_0;
(G2) the full-system gap: H - E_0 I >= Delta (I - |Omega><Omega|),
with Delta > 0.
Both hypotheses are about the whole system. The proof below will
apply H only to whole-system vectors. It never assumes a gap for the
restriction of H to any subregion, and it never assumes anything about
low-lying states.
0.2 What a PEPS is
-------------------
Attach to every edge e a positive integer D_e and a maximally
entangled pair vector
sum_{a=1}^{D_e} |a>|a> in C^{D_e} tensor C^{D_e},
one half of it at each endpoint of e. At every site v apply an
arbitrary linear map
A_v : tensor over e incident to v of C^{D_e} --> C^q .
Contracting all the pair vectors through all the maps produces a vector
in H_Lambda. Any vector obtainable this way is a PEPS on the grid.
Its bond dimension is max_e D_e.
Three remarks, all of them important later.
(a) The maps A_v need not be isometries. The resulting vector need
not have norm one. We always normalize by hand at the end.
(b) "Bond dimension at most D" is a statement about existence of some
choice of pair vectors and maps. It is not a statement about
an algorithm, and it does not bound the size of the entries of
the tensors.
(c) Bond dimension is a different resource from entanglement across
a single cut. Section 0.4 explains why the distinction matters.
0.3 The theorem
----------------
THEOREM 0.1 (main theorem).
Fix q >= 2 and J, Delta > 0. There exist constants C, c > 0, depending
only on q, J, Delta, with the following property. For every L >= 2,
and every Hamiltonian of the form (0.1) satisfying (G1) and (G2), there
is a nonzero PEPS Phi on the same grid Lambda with maximum bond
dimension at most C L^c and
min over theta in R of || Phi/||Phi|| - e^{i theta} Omega || <= L^{-1}. (0.2)
The theorem is an existence statement with three deliberate omissions.
It does not say the tensors can be found in polynomial time.
It does not say the resulting network can be contracted in
polynomial time. (General PEPS contraction is hard; see the
remark at the end of 0.5.)
It does not impose structure: the approximant need not be injective,
need not have a gapped parent Hamiltonian, and need not be
translation invariant.
What it does say is exactly what an approximation theorem should say:
the ground vector itself, as a vector, is close to a PEPS with small
virtual dimension on the prescribed edges.
0.4 Why an entropy area law is not enough
------------------------------------------
The input we are given, and the input we will use, is an area law: for
every region A,
S(A) <= C_A |boundary edges of A|. (0.3)
For a ground state of a gapped local Hamiltonian on the plane this is
proved in the companion paper and imported in Part 1. It is tempting
to think that (0.3) already gives a PEPS. It does not, and it is worth
being precise about why.
(i) An area law controls each cut separately. A PEPS controls all
cuts at once with a single set of tensors. Controlling one cut
only gives, at that cut, a truncation of the Schmidt spectrum.
Different cuts want different truncations, and there is no
reason for the truncations to be compatible.
(ii) Even at a single cut, bounded entanglement entropy does not
produce a small-bond approximation of the whole vector. For
chains, families of states with bounded block entropy and no
efficient global matrix-product approximation are known. In
two dimensions, families with strong area laws and no efficient
tensor-network description are known. Those examples are not
gapped ground states, but they show that genuine structure is
being used, not just entropy.
(iii) Condensation into a network requires both compatibility and
additive error control. Splitting, exchanging, and compressing
each inject error. If those errors were to accumulate over the
polynomially many steps of a protocol they would swamp the
target. So the construction must be designed so that every
error is either reset or spent only boundedly often.
The proof below is, essentially, an answer to (i), (ii), (iii): a
distributed description of the state, using operations that are each
approximated by pair resources, with an error budget managed so that
the total stays below L^{-1}.
0.5 The strategy in five steps
-------------------------------
The state Omega is described by a protocol in which auxiliary parties
hold pieces of the state and exchange pieces locally. At the end every
physical site is held by its own party. Then a compression theorem
turns the protocol into a tensor network, and a routing lemma places
the network on the grid. These are the five steps.
STEP A: small information between separated regions (Part 2).
The protocol's elementary moves (change of owner of a region; exchange
of two copies on a lens) are allowed only when the mutual information
between the moving region and the outside is negligible. Two
statements give that.
(A1) Coarse collar (Proposition 2.1). If a region is separated from
a remote system by distance u^{beta} with beta < 1, its mutual
information with the remote system is at most a constant.
This is imported.
(A2) Reset (Lemma 2.3). If I(R:C) <= b and one shrinks both systems
by a collar of width proportional to b + log L, then the mutual
information of the shrunken systems is at most L^{-p}. This
uses the full-system gap, and only the full-system gap. The
mechanism is Gaussian spectral filtering of the swapped
doubled ground state, followed by Lieb-Robinson localization.
Combining the two with an annular decomposition gives (Proposition
2.4) a statement of the shape: information is negligible when the
separation tapers linearly toward finitely many points but stays above
D log L.
STEP B: finite-rank constraints on logarithmic patches (Part 3).
Near any square of radius u <= O(log L) there is an orthogonal
projection P with ||(id-P) Omega|| <= L^{-p}, whose range is a sum of
at most CL^c mutually orthogonal cylinders, each cylinder being a
subspace on a nested square sample times the identity outside it. The
radii of the cylinders are allowed to vary. This adaptive form is
essential: at a single prescribed radius no accurate finite-rank
truncation is available. The mechanism is an optimized nested-filter
variational problem whose stationarity can be analysed without
commuting the filters, plus the area law for the constant-tail rank.
STEP C: from distributed protocol to tensor network (Part 4).
A "distributed construction" is a schedule of contraction gates between
parties. Theorem 4.2 shows that, provided each party takes part in
boundedly many nonprivate gates over its whole lifetime, and each gate
has a polynomial expansion into local contractions and normalized
bipartite resources, the resulting physical density is approximated in
trace norm by an operator tensor network with polynomial link
dimensions, where the approximation error is independent of all private
Hilbert-space dimensions and all source Schmidt ranks. The mechanism
is a Gaussian sample-and-average of each source operator combined with
a two-weight Schatten-Holder bound.
STEP D: frames, holes, and the elementary moves (Part 5).
A "frame" is a sheet of raw registers with an ownership assignment and
with small "holes" encoded by adaptive projectors. Three lemmas
implement the moves: a small-patch rewrite (change ownership near a
logarithmic patch, using only bounded parties), a homogeneous birth and
death (change ownership of a region of one owner into another owner,
using the reset information bound), and a two-sheet exchange (swap two
copies on a lens, using the same information bound).
STEP E: the protocol and the assembly (Parts 6 and 7).
Pass from the uniform assignment by 2n-blocks to the uniform assignment
by n-blocks, one repainting at a time, using an auxiliary sheet for the
long edges and small patches for the finitely many junctions. Each
party participates only at two adjacent scales, so its total
participation is bounded. Part 7 then telescopes the errors, extracts
one ket column of the compressed operator, and routes the remaining
graph on the grid with constant congestion.
REMARK ON CONTRACTION EFFICIENCY. General PEPS contraction is
computationally hard in the worst case. That statement is about
contracting a given network, and it does not classify the particular
networks constructed here. Theorem 0.1 is deliberately silent about
both finding and contracting the approximant. The distinction is
substantive, and the reader should not read Theorem 0.1 as an
algorithmic statement.
================================================================
PART 1. CONVENTIONS AND THE ENTROPY INPUT
================================================================
1.1 Regions, norms, and entropy
--------------------------------
Unsubscripted norms are the operator norm for maps and the Euclidean
norm for vectors; ||.||_1 and ||.||_2 are the trace norm and the
Hilbert-Schmidt norm. All Hilbert spaces are finite dimensional and
empty tensor products have dimension one.
The size parameter L always satisfies L >= 2 but may be enlarged when a
fixed threshold is required; "for all sufficiently large L" means there
is a fixed L_0 depending only on q, J, Delta and on the explicit
constants named so far. Every "polynomial" quantity is bounded by
C L^c with C, c uniform in the Hamiltonian.
Plane distances are sup-norm distances. For a plane set T,
T^{+r} = { x : dist_infinity(x,T) <= r }.
Sampling always means intersection with Lambda, and a physical sample of
an ambient set implicitly includes intersection with Lambda. The
distance to the empty set is +infinity. Region letters placed next to
each other denote a disjoint union. In entropy formulas complements
refer to the whole physical system unless another system is named
explicitly.
For a normalized state omega and a region A, rho_{omega,A} is the
marginal on A. The basic quantities are
S_omega(A) = -Tr rho_{omega,A} log rho_{omega,A},
I_omega(A:C) = S_omega(A) + S_omega(C) - S_omega(AC),
I_omega(A:C|B) = S_omega(AB) + S_omega(BC)
- S_omega(B) - S_omega(ABC).
Logarithms are natural, and 0 log 0 = 0. When the state is Omega we
write S(A), I(A:C), I(A:C|B).
Four standard facts are used repeatedly and are stated here so that no
external reference is needed.
(SSA) Strong subadditivity: I_omega(A:C|B) >= 0.
(CHAIN) Chain rule:
I_omega(A_1 A_2 : C | B)
= I_omega(A_1 : C | B)
+ I_omega(A_2 : C | B A_1).
(MONO) Monotonicity under discarding systems: if A' is contained in A
and C' in C then I_omega(A':C') <= I_omega(A:C).
(DUAL) For a pure state on ABCD,
I(A:C|B) = I(A:C|D).
Also used: |S(A|B)| <= log dim H_A, and hence the entropy cost of a
bounded set of individual sites is at most its size times log q.
1.2 The imported entropy area law
----------------------------------
The proof of the companion paper on the two-dimensional area law gives,
in the language of this document, the following statement. It is the
only geometric input we take from outside; everything else is either
proved here or is standard finite-dimensional information theory.
PROPOSITION 1.1 (entropy area law; companion, Theorem 1.1 and
Corollary 1.2).
Under (0.1), (G1), (G2) there is C_A = C_A(q,J,Delta) such that for
every region A subset of Lambda,
S_Omega(A) <= C_A |partial A|, (1.1)
where partial A is the set of neighbouring pairs with one endpoint in A
and one outside A. The same C_A works for every L and every H in the
class.
The companion theorem is stated, in the reference, for any finite
induced square-lattice domain, with one bounded Hermitian term per
support of bounded induced-graph diameter, and with the single spectral
assumption (G1), (G2). Our case is that statement with domain Lambda
and diameter bound one, so it is exactly what is needed. For a
physical sample X of a square of radius r, (1.1) gives
S_Omega(X) <= C (1+r), (1.2)
including squares that are clipped by the outer boundary of Lambda.
We will also use, in Part 2, the companion's sublinear collar bound and
its amplification step. These are not area-law statements in the
narrow sense: they are the technical engine behind the area law. Their
hypotheses and conclusions are recorded exactly in Part 8, and the
specific uses are checked when they arise. Their role in this
document is purely as a black box at one scale at a time, and they
never enter a statement that a subregion has a gap.
1.3 Fidelity, relative entropy, and splitting
---------------------------------------------
For normalized density operators rho, sigma put
F(rho,sigma) = ||sqrt(rho) sqrt(sigma)||_1,
D(rho||sigma) = Tr rho (log rho - log sigma),
with D = +infinity when the support condition fails.
LEMMA 1.2 (fidelity versus relative entropy, and splitting).
Let rho and sigma be normalized states on the same finite-dimensional
space, with supp rho subset of supp sigma. Then
F(rho,sigma) >= exp(-D(rho||sigma)/2). (1.3)
Moreover, after enlarging the purifying space if necessary, an isometry
on that space realizes overlap F(rho,sigma) between any prescribed
purifications of rho and sigma. In particular, if two states on AC
satisfy
D( rho_{AC} || rho_A tensor rho_C ) <= b,
then there is a purification of rho_A tensor rho_C that is within
distance sqrt(b) of a purification of rho_{AC}, after a phase choice.
PROOF.
Write the spectral decompositions as (p_i, |i>) and (q_j, |j'>). When
D = D(rho||sigma) is finite, define w_{ij} = p_i |<i|j'>|^2. Then with
w restricted to the pairs with p_i, q_j > 0,
D = sum_{ij} w_{ij} log(p_i/q_j).
Convexity of exp gives
Tr sqrt(rho) sqrt(sigma)
= sum_{ij} w_{ij} exp( - (1/2) log(p_i/q_j) )
>= exp( - D/2 ).
Terms with p_i = 0 contribute zero on both sides. The trace norm
dominates the absolute trace, so (1.3) follows; the infinite case is
immediate.
The relative-entropy identity D(rho_AC || rho_A tensor rho_C) = I(A:C)
follows by tracing the definition against log(rho_A tensor rho_C) =
log rho_A tensor id + id tensor log rho_C on the support of rho_AC.
For the isometry statement, the canonical purifications of rho and sigma
have coefficient matrices sqrt(rho) and sqrt(sigma); varying a unitary
U on a common purifying space of adequate size gives overlaps ranging
over Tr(sqrt(rho) sqrt(sigma) U) up to a transpose convention. Polar
decomposition gives the maximum absolute value ||sqrt(rho)
sqrt(sigma)||_1. Every other purification of rho comes from the
canonical one by an isometry on the purifying factor, and those
isometries extend to unitaries on any sufficiently large common factor,
so no minimality is required. The squared distance of two unit
purifications whose overlap has modulus F is 2(1-F). Together with
(1.3) and 2(1-exp(-b/2)) <= b, this gives the stated sqrt(b) form.
END PROOF.
The consequence we will actually use, in all the "splitting" arguments,
is the following corollary. It is a restatement of the last sentence of
Lemma 1.2.
COROLLARY 1.3 (splitting of a buffer with small mutual information).
Let T, U, E partition Lambda and let b = I_Omega(T:E). Then there are
finite-dimensional spaces B_T, B_E, an isometry
W : H_U --> B_T tensor B_E,
and normalized vectors s in H_T tensor B_T, s' in H_E tensor B_E, such
that
|| (id_{TE} tensor W) Omega - s tensor s' || <= sqrt(b). (1.4)
There is no bound on the dimensions of B_T and B_E.
END COROLLARY.
In every application W will act privately on U, i.e. all of U and both
factors B_T, B_E will belong to one party. That is the entire trick of
the frame operations in Part 5: a single party can absorb arbitrarily
large buffers as long as it does not have to speak to anyone else.
1.4 Two inequalities about entropies under perturbation
-------------------------------------------------------
Two continuity statements are used.
LEMMA 1.4 (entropy continuity).
Let rho, sigma be normalized finite-dimensional states on AB with
delta = (1/2) ||rho - sigma||_1 <= 1. Then
| S(A|B)_rho - S(A|B)_sigma |
<= 2 delta log dim H_A
+ (1+delta) h( delta/(1+delta) ), (1.5)
where h is binary entropy. In particular
| S(A|B)_rho - S(A|B)_sigma |
<= C sqrt(delta) log( e dim H_A ).
PROOF.
This is the tight uniform continuity theorem for conditional entropy.
The displayed (1.5) is its statement in the form we use; the cruder
sqrt(delta) consequence follows from h(x) <= C sqrt(x) for x in [0,1]
and from delta <= sqrt(delta). The dependence is only on
dim H_A, not on the purifying or conditioning system. END PROOF.
All physical logarithmic dimensions in this document are O(L^2), so the
entropy continuity cost of a trace-distance error delta is at most
C sqrt(delta) L^2. Every use of Lemma 1.4 is at delta = L^{-q} for
some fixed q; the L^2 factor is always absorbed by choosing the
relevant error power with a fixed slack.
1.5 The gap implies a vector-distance bound
--------------------------------------------
LEMMA 1.5 (gap versus distance).
Under (G1), (G2), for every normalized psi and some phase theta,
|| psi - e^{i theta} Omega ||^2
<= (2/Delta) < psi , (H - E_0 I) psi > . (1.6)
PROOF.
Decompose psi along Omega and its orthogonal complement. Let p =
|<Omega,psi>|^2. The excitation energy <psi,(H-E_0)psi> is at least
Delta (1-p), by (G2). Phase minimization gives |psi - e^{i theta}
Omega|^2 = 2(1-|<Omega,psi>|) = 2(1-sqrt(p)). Since
1-sqrt(p) <= 1-p for p in [0,1], the right side is at most
(2/Delta)<psi,(H-E_0)psi>. END PROOF.
Lemma 1.5 is where the full-system gap becomes a statement about vectors.
It is applied in Part 2 inside the Gaussian filter estimate and in
Part 3 when comparing a variational minimizer with Omega. Everywhere
else the gap enters only through the area law and through the
companion's collar estimates.
================================================================
PART 2. INFORMATION BETWEEN SEPARATED REGIONS
================================================================
Throughout Part 2, distances are sup-norm distances in the plane, and
"graph distance" is nearest-neighbour distance on the physical square,
used only in the Lieb-Robinson estimate. Every graph ball lies inside
the corresponding ambient sup ball. For a plane set F, F^{+r} is its
ambient radius-r enlargement, and the physical sample is
Lambda intersection F^{+r}. Rectangles and squares here include their
unoccupied locations.
The object of Part 2 is this sentence: information is negligible
between two regions whose separation tapers linearly toward a fixed
number of points, provided the separation never drops below a
sufficiently large multiple of log L. The proof has three layers.
(2.1) an imported coarse collar statement (Proposition 2.2);
(2.2) a conditional mutual information bound for one cell of a grid
with arbitrary exterior conditioning (Lemma 2.3);
(2.3) a reset of the information scale by the full-system gap
(Lemma 2.4);
(2.4) assembly into the tapering statement (Proposition 2.5).
Only (2.1) is taken from outside this document. Its hypotheses and its
conclusions are recorded in full, and Part 8 checks that the companion
paper proves exactly it.
2.1 The imported coarse collar estimate
----------------------------------------
We first recall the companion paper's template notion and its two
interface statements, because we will use them as black boxes with
precise hypotheses.
DEFINITION 2.0 (templates and cuts; companion, Sections 9 and 10).
A nonempty ambient lattice set
T = union_{a=1}^{N_0} ( P_a intersection Z^2 )
is an admissible template when the P_a are closed rectangles or
triangles with sup diameter at most s_0 and side slopes in
{0, infinity, 1, -1}, and
n >= C_tpl N_0 (s_0 + 1), diam_inf T <= n,
for a fixed template constant C_tpl. A cut is a physical region
A subset of Lambda; Z_A is the set of physical endpoints of edges
crossing A. The template-clearance assumption for a cut A is
dist_inf(T, Z_A) > 4 D_0 s_0,
for a fixed D_0. With epsilon_col = 10^{-5} and
ell = floor( n^{1 - epsilon_col} ), T_ell = T + [-ell,ell]^2,
the companion's Proposition "A sublinear collar bound" asserts, for all
sufficiently large scales:
I_Omega( A intersection T : Lambda \ (A intersection T_ell) )
<= C n^{1 - epsilon_col}. (2.0)
It also supplies |A intersection T_ell| <= C n^2 and C n upper bounds
for the number of physical crossing edges of each of the three cuts
X = A intersection T, Y = (A intersection T_ell) \ X, and
S_0 = A intersection T_ell. All constants are uniform in the domain,
the cut, and the admissible template.
DEFINITION 2.1 (amplification; companion, Section 10).
The companion's Proposition "Amplification" uses exactly these size,
three-cut, and information bounds, for any fixed common upper-bound
constant, and the exponents
beta_0 = 1 - 2 * 10^{-6}, alpha = k/(k+1) > 1 - 10^{-6},
where k is a sufficiently large fixed integer. Given the bounds above,
and any fixed integer M >= 1, it produces a graph radius r satisfying
ell + 2r = o( n^{beta_0} ),
I_Omega( X' : E ) <= C_M n^{-M}
for every X' subset of X and
every E subset of Lambda \ N_{2r}( S_0 ), (2.1)
where N_{2r} is the physical graph neighbourhood. The radius r and the
constant C_M do not depend on the remote set E or on the total volume.
Both statements require a positive system on the same physical grid.
The companion's Proposition "Positive replacement of the Hamiltonian"
supplies it for each prescribed integer k, using only the original
full-system eigenvector Omega and the full-system gap inequality (G2).
That replacement does not assume a gap for any restricted Hamiltonian,
and its constants depend only on the fixed k and on q, J, Delta. Our
on-site and nearest-neighbour Hamiltonian (0.1) has induced-graph range
one and one bounded term per designated support, so it satisfies the
bounded-interaction hypotheses of all three companion statements.
Part 8 restates all three companion statements in the same notation and
checks that (0.1), (G1), (G2) place us inside their hypotheses. From
here on, "imported" refers to them.
PROPOSITION 2.2 (coarse information outside a sublinear collar).
Fix an integer N_0 >= 1 and a constant A_0 >= 1. There exist
beta < 1, C < infinity, and u_0 < infinity such that the following
holds. Let u >= u_0 and let T be the full ambient lattice sample of a
union of at most N_0 axis-parallel rectangles, with
diam_inf T <= A_0 u. For every physical set E subset of Lambda
satisfying
dist_inf( E, T ) > u^beta , (2.2)
one has
I_Omega( Lambda intersection T : E ) <= C . (2.3)
The same conclusion holds for every subset of Lambda intersection T in
the first argument, for rectangles with consistently assigned open or
closed sides, and after a common translation of the lattice
coordinates.
PROOF.
If Lambda intersection T is empty, the first argument is the empty
system and the information is zero.
Otherwise discard empty pieces. Choose an integer s_0 comparable to
u and large enough that every piece has diameter at most s_0. Choose an
integer n comparable to a fixed large multiple of u, with the ratio
n / s_0 fixed. These choices arrange both template inequalities of
Definition 2.0. Take the prescribed cut to be the whole domain, A =
Lambda. Then Z_A is empty, so all template-clearance assumptions are
vacuous. Because the ratio n / s_0 is fixed,
ell = floor( n^{1 - epsilon_col} ) <= s_0
for all sufficiently large u, so the companion collar bound applies,
with a constant C_1 independent of u, and the three crossing-edge
bounds hold with the same uniformity.
The hypotheses of Definition 2.1 are therefore satisfied. Fix that
proposition's common upper-bound constant once and apply the
amplification with M = 1. Choose beta strictly between beta_0 and 1.
Since n is a fixed multiple of u,
ell + 2r < u^beta
for all sufficiently large u. A physical graph neighbourhood of S_0
of radius 2r is contained in the physical sample of the ambient
enlargement of T by ell + 2r. Hence any physical E obeying (2.2) is
contained in Lambda \ N_{2r}(S_0) and is therefore an allowable remote
set in (2.1). Since X' = Lambda intersection T is a subset of X, the
conclusion (2.1) with M = 1 reads
I_Omega( Lambda intersection T : E ) <= C_1 n^{-1} .
That quantity is bounded uniformly in u, giving (2.3). Discarding
part of the first system cannot increase mutual information
(monotonicity), and discarding part of E similarly cannot increase it.
That gives the subset version.
For open and closed sides: on the lattice, a rectangle with some sides
declared open has the same physical sample as a closed rectangle with
sides shifted arbitrarily slightly, unless an endpoint lies on a
lattice line, in which case the shift can still be chosen so as not to
change the sample. The diameter bounds change by at most a fixed
additive amount. Increasing u_0 and enlarging C absorbs the
difference. A common translation of lattice coordinates is undone
before applying the companion statements, so it likewise only changes
the constants. END PROOF.
Proposition 2.2 says, bluntly, that if the collar between T and E is
sublinear in the size of T then their mutual information is bounded by
a constant. A constant is not enough for the construction: at each
step we need an inverse power of L. Lemma 2.3, in the next subsection,
turns a constant into an inverse power at the price of a collar whose
width is proportional to b + log L, where b is the starting bound.
2.2 Conditional information of one cell, with arbitrary exterior
------------------------------------------------------------------
The next estimate is the only place where the ordering principle of the
companion's two-family construction is used in a new setting. The
reason it is needed here is specific. In Part 6, a region is transferred
from one owner to another, and the information hypothesis has to hold
uniformly in whatever the exterior looks like. The companion statement
is proved for a single cut of the whole domain; here we must allow an
arbitrary exterior conditioning system B, which is neither a cut nor a
region with any independent property. What we can hope for, and what
the Lemma gives, is a bound that depends only on the cell size s, and
not on the shape or size of B.
The Lemma also makes a point of order. In the companion's argument,
the two exterior colours are read in opposite orders. The same
opposite-order reading is what makes the two-family cancellation work
here, and the proof below works through the ordering carefully rather
than appealing to a convention. A reader who only wants the logic may
read the statement, the displayed tile cost (2.4), and the paragraph
headed "Why the ordering is the whole trick"; the rest is bookkeeping.
We use ambient colours. A boundary line belongs to no colour; a point
of the lattice is assigned to a chamber by resolving boundary ties with
one fixed infinitesimal generic displacement, chosen once for the whole
finite problem. Equivalently one works with open chambers, uses their
closures for distance estimates, and then samples with a common tie
convention. Only finitely many chamber boundaries occur at a fixed
instance, and this is the whole role of the convention. No colour is
given to a boundary of positive codimension.
LEMMA 2.3 (conditional information of one cell).
Fix c > 0. Tile the plane by an axis-parallel grid of squares of side
s >= 1. Let G be the physical sample of one cell, let B be the physical
sample of any union of other cells, and let C be a subset of
Lambda \ ( B union G )
satisfying
dist_inf( C, closure_amb(G) ) >= c s , (2.4)
where closure_amb(G) is the full closed ambient cell. There exist
constants C_1, K < infinity, depending only on q, J, Delta and on c, and
on no other data, such that
I_Omega( G : C | B ) <= C_1 ( 1 + log s )^K . (2.5)
The constants do not depend on which exterior cells form B, and do not
depend on the shape of C away from the cell.
PROOF.
Set-up and colouring. Colour every exterior cell in B with forbidden
colour 0, and every remaining exterior cell with forbidden colour 1.
This colours every physical site outside G, including the sites of C.
The inside of G is initially allowed. Let F_0 be the set of physical
sites of forbidden colour 0, and F_1 the set of physical sites of
forbidden colour 1. Later on, when a still-allowed region is assigned
to family i in {0,1}, it becomes forbidden colour i for all subsequent
stages.
What the construction will deliver. We will construct two ordered
families of tiles, F_0 and F_1 (the notation overloads; in the rest of
the proof the family names are curly F_0, F_1 and the exterior colour
sets are the plain sets above, distinguished by context), together with
a set of exceptional sites. Each tile is a physical subset inside G,
one family per allowed component of a stage; the order in a family is
its creation order. Each tile U of family i will satisfy
I_Omega( U : C union (external colour-i set)
union (earlier tiles of family i) )
<= C_2 , (2.6)
for a constant C_2 whose dependencies will be made explicit. Only two
things will be used to prove (2.6) at each tile: the coarse collar
estimate (Proposition 2.2) and the construction itself, which will
guarantee that each tile sits at distance at least u^gamma, gamma > beta,
from the exterior colour sets that obstruct it.
Why the ordering is the whole trick. Assume the partition exists.
Apply the chain rule for I(G:C|B) by listing, in order:
first, every tile of family 0 in creation order;
then, every exceptional site;
then, every tile of family 1 in reverse creation order.
At any stage of the list the chain-rule term for a newly added tile U is
I( U : C | Z ),
with Z the previously listed sites, together with B.
For a family-0 tile, since Z contains only forbidden-0 exterior sites
and earlier family-0 tiles,
I( U : C | Z ) = I( U : C union Z ) - I( U : Z )
<= I( U : C union Z ),
and C union Z is contained in C union (external colour-0 set) union
(earlier tiles of family 0), so (2.6) applies.
For a family-1 tile, purity on the whole physical system gives
I( U : C | Z ) = I( U : C | (U C Z)^c ).
The complementary conditioning set contains only forbidden-1 exterior
sites and still-unprocessed family-1 tiles. Because family 1 is
processed in reverse creation order, the "still-unprocessed" tiles are
exactly the ones created before U. Bounding the conditional mutual
information by the mutual information with C union (U C Z)^c, and
observing that this union is the one in (2.6), applies (2.6) again.
Each exceptional site contributes at most 2 log q, by the dimension
bound for a single site. Therefore, if the number of tiles plus
exceptional sites is at most C (1 + log s)^K, then (2.5) follows. The
rest of the proof constructs the partition and estimates that count.
Tile construction by ambient recursion. Fix
beta < gamma < gamma' < 1 ,
with beta the exponent of Proposition 2.2, chosen for bounded
rectangular unions. At any generation, all allowed residual material
lies in active axis-parallel squares of a common side u, distinct
active squares being at mutual distance greater than 10u. In the
ambient radius-u padding of each active square, the three labels
(allowed; forbidden 0; forbidden 1) are constant on chambers of
boundedly many horizontal and vertical lines. Square sides are
included, and distinct parallel lines are at least u/8 apart. At the
start there is one active square, the original cell, with side u = s;
its padded window meets only boundedly many grid lines, so the
chamber invariant holds regardless of how the exterior is coloured.
Choose a large fixed stopping threshold u_*. At a non-terminal square,
put t_0 = u^gamma. Increase u_* so that every inequality below holds
for u >= u_*. Around each represented line intersection within
distance 10 t_0 of the square, reserve a closed square of radius 4 t_0
for the next generation. Reserving a hole does not change a
previously fixed colour; only still-allowed material is ever reserved.
The hole squares are disjoint: they are centred on distinct
intersections that are separated by the line spacing.
The one-colour observation. Every allowed point of the active square
outside these holes sees at most one forbidden colour within distance
t_0. Indeed, it cannot see two parallel represented lines, because
2 t_0 < u/8. If it sees both orientations, their intersection is within
distance t_0 of the point, and that intersection belongs to a reserved
hole, a contradiction. Hence its t_0-neighbourhood sees at most one
line. The chamber on its own side is allowed, and the chamber on the
other side of that single line has at most one forbidden colour.
Assignment of tiles. Using the colours as they were at the start of
the current generation, assign to family 1 every remaining allowed
point within distance t_0 of forbidden colour 0. Assign to family 0
every other remaining allowed point. Then:
The new family-0 tile is at least t_0 from the old forbidden-0 set,
since the points near it went to family 1.
The new family-1 tile is at least t_0 from the old forbidden-1 set,
by the one-colour observation: a point within t_0 of colour 1 cannot
be within t_0 of colour 0 either, since that would mean seeing two
forbidden colours at once. So the definition of the tile as
"within t_0 of colour 0" ensures it clears colour 1 by t_0.
There is at most one tile of each family per active square. Tiles of
the same family in different active squares are farther apart still,
so within a generation they may be ordered arbitrarily.
Each new tile is a union of boundedly many rectangular chambers, after
deleting the bounded list of reserved holes, and has total diameter
O(u).
Verifying the tile cost (2.6). The ambient template of a new tile is
at distance at least t_0 from the physical old forbidden set of its own
family, as just checked. It is also at distance at least c s from C,
since it lies inside the original cell. Because u <= s and
gamma > beta, both distances exceed the collar u^beta required by
Proposition 2.2 after increasing u_*. This proves (2.6) with a constant
C_2 independent of the generation, the family, and the exterior colouring.
Descending to the next generation. The new active squares are the
reserved holes containing allowed material. Their side is
u' = 8 t_0 .
Distinct represented intersections are at least u/8 apart, so for large
enough u_* the new active squares are at mutual distance greater than
10 u'. Squares descending from different parents inherit even larger
separation.
The chamber invariant one level down. Consider a child's padded window,
which has radius u' about its centre, so radius 12 t_0. The old line
spacing implies that the only old horizontal and vertical lines in this
window are the two through its centre. New boundaries in the window
occur only at offsets
0, ± t_0, ± 4 t_0
from those two lines: these are, respectively, the distance test, the
reserved hole, and any clipping by the old active-square sides. Every
other hole and every other old parallel line is outside the window.
Hence the new parallel-line spacing is at least t_0 = u'/8, and the
number of lines is uniformly bounded. This is the invariant at the
next generation.
A reserved hole centred on or slightly outside a parent side is
handled by the same verification: old fixed colours are retained, and
only the allowed intersection is processed. No rule is broken at the
boundary.
Stopping and counting. At scale below u_*, stop and make every
remaining physical site exceptional. There are boundedly many children
per active square and boundedly many sites in a terminal square of side
below u_*. Choose u_* also so that
8 u^gamma <= u^{gamma'} for all u >= u_* .
The number of generations is therefore O(1 + log log (s + e)). Bounded
branching bounds the total number of tiles and exceptional sites by
C (1 + log s)^K for some fixed C, K.
The case s < u_*. Then the direct bound
I( G : C | B ) <= 2 |G| log q <= 2 s^2 log q
already has the form (2.5) after enlarging C and K, since s is bounded.
Boundary conventions. The infinitesimal tie convention used for
colours preserves every separation estimate on closures, since those
estimates are strict inequalities. Each sampled tile is a sampled
rectangular union, so Proposition 2.2 applies to it directly. This
closes the proof of (2.5). END PROOF.
Two remarks about what was and was not used.
First, the exterior conditioning system B is charged only through its
colour. Its size, its shape, and the number of cells it occupies
never enter the constants. This is exactly what is needed in Part 6,
where B changes from one repainting to the next while the cell does
not.
Second, no gap is used for anything except the original full-system
state, and that only through Proposition 2.2. The two-family
construction inherits its information input wholesale from the
companion's collar and amplification statements, which is the point
of the division of labour recorded in Part 8.
2.3 Reducing a collar information cost to an inverse power of L
-----------------------------------------------------------------
The reset lemma. If I(R:C) <= b for some two-region split of the whole
physical system, we may want to conclude that I(R_0:C_0) is small for
the shrunk cores R_0 subset of R, C_0 subset of C. Not free: the pair
(R_0,C_0) may itself be strongly correlated, even though the larger
pair (R,C) is barely correlated. What saves us is the full-system gap:
it forbids the cores from carrying correlations that would otherwise
hide from the primal cut. The mechanism is a Gaussian spectral filter
that transfers the swap operator on R into a swap operator on a buffer
of two copies, and the buffer can be chosen to avoid the cores because
the gap makes the transfer local.
We use Lemma 1.2 in the following form. For density operators with
supp rho subset of supp sigma,
|| sqrt(rho) sqrt(sigma) ||_1
>= exp( - (1/2) Tr rho ( log rho - log sigma ) ), (2.7)
and, after enlarging the purifying space if necessary, an isometry on
that space realizes the corresponding overlap with a prescribed
purification. The original purifying buffer need not be minimal. All
enlarged factors are removed before any Hamiltonian-locality estimate is
applied.
LEMMA 2.4 (information reset).
For every fixed p > 0 there is C_p < infinity with the following
property, for all sufficiently large L. Let R, C be disjoint subsets of
Lambda, let R_0 subset of R and C_0 subset of C, and suppose that
I_Omega( R : C ) <= b , b >= 0 .
If
dist_inf( R_0, Lambda \ R ) > w ,
dist_inf( C_0, Lambda \ C ) > w ,
w = C_p ( 1 + b + log L ) , (2.8)
then
I_Omega( R_0 : C_0 ) <= L^{-p} .
Only the original full-system gap is assumed.
PROOF.
Empty cores are trivial. If R_0 or C_0 is empty, the mutual
information of the pair is zero, and the conclusion holds with any
C_p.
Step 1: two replicas, and the target vector. Put
Psi = Omega tensor Omega , F = F_R , Phi = F Psi ,
where F_R is the unitary swap of the two replicas on every physical
site of R and the identity elsewhere. Both Psi and Phi are unit
vectors. The plan is to construct a unitary U, supported in the two
replicas outside the cores R_0 and C_0, for which U Psi is close to
Phi. Why that is enough: U leaves the joint core marginal in "one
replica" sense unchanged, and in Phi the two cores come from different
original replicas, so the joint marginal of (R_0 from the first
replica) with (C_0 from the second replica) is the product
rho_{R_0} tensor rho_{C_0}. Hence if U Psi is close to Phi, the
two-copy marginal on (R_0 in the first replica, C_0 in the second) has
to be close to that product, which is what forces small mutual
information between R_0 and C_0 in the original one-copy state.
We make that last sentence precise once the nonlocal part of U is in
hand; see Step 6.
Step 2: controlled overlap from the buffer. The relative entropy of
rho_{RC} from rho_R tensor rho_C is I_Omega(R:C) <= b. The required
support inclusion holds: positivity implies that a joint state is
supported on the tensor product of the supports of its marginals. For
example, the expectation of the positive joint state on the projector
onto the kernel of either marginal, tensored with the identity on the
other side, is zero, so that projector annihilates the joint state.
Apply Lemma 1.2 to rho_{RC} and rho_R tensor rho_C, both purified by
Omega against the buffer Q = (R union C)^c. Enlarge the purifying
spaces if needed by blank ancillas so that (i) the product purification
fits and (ii) an isometric image of the entire H_Q fits. We get an
isometry
V : H_Q --> B_R tensor B_C ,
and normalized vectors a_{R B_R}, a'_{C B_C} with
| < a tensor a' , (id_{RC} tensor V) Omega > |
>= e^{-b/2} . (2.9)
The factors B_R and B_C are finite-dimensional; no bound on their
dimensions is used or claimed.
Step 3: the buffer swap z. Let
Omega~ = (id_{RC} tensor V) Omega .
Its largest Schmidt probability across (R B_R) | (C B_C) is at least
| < a tensor a' , Omega~ > |^2 >= e^{-b};
hence the purity of the reduced state on R B_R obeys
Tr ( rho_{Omega~, R B_R} )^2 >= e^{-2b} .
Pull the swap on B_R back to the original two copies of the buffer:
W = ( V^dagger tensor V^dagger ) F_{B_R} ( V tensor V ) .
Then W is a Hermitian contraction on the two physical copies of Q. Why
it has disappeared from B_R and B_C entirely: W is the outer
conjugation of F_{B_R} by V tensor V, and V acts on H_Q, so the
result is an operator on two copies of H_Q. The auxiliary spaces have
gone.
The swap identity for purity, applied to Omega~ and to F_R F_{B_R},
gives the real positive number
z := < Phi , W Psi >
= < Omega~ tensor Omega~ , F_R F_{B_R} Omega~ tensor Omega~ >
= Tr ( rho_{Omega~, R B_R} )^2
>= e^{-2b} . (2.10)
The middle equality is the standard purity-as-swap-expectation identity:
for a unit vector omega~ on a bipartite system (R B_R) plus (C B_C), the
purity of the marginal on (R B_R) is the expectation of the swap on (R
B_R) in the doubled state. Because Omega~ = (id tensor V) Omega and V
acts outside R, the swap on (R B_R) pulls back to W on the doubled
buffer plus F_R on the doubled R; that is the first line.
Step 4: the doubled Hamiltonians. Write
HH = H tensor I + I tensor H (on the doubled space),
HH' = F HH F^dagger .
Treat the pair of replica registers at a physical site as one site of a
new lattice of the same shape; the local dimension is q^2. Then both
HH and HH' have range one and uniformly bounded interaction degree and
strength (at most 2J for each interaction). Their unique ground vectors
are Psi and Phi, their common ground energy is E_E = 2 E_0, and their
gaps are at least Delta, because
H - E_0 I >= Delta ( I - |Omega><Omega| )
implies the same for the tensor square, applied to the swap-symmetric
subspace. Their difference is supported at the endpoints of edges
crossing R:
HH' - HH = 2 * ( sum of terms on one side minus the same on the
other, supported on physical edges that cross R ).
Terms entirely inside R merely exchange the two identical replica terms,
and all other noncrossing terms are unchanged; only the crossing edges
contribute. The number of crossing edges is bounded by 4L, and each
contributes at most 2J.
Step 5: the Gaussian filter. Put
B_* = 1 + b + log L ,
r_* = 2p + 10 ,
and choose a fixed h = A B_* with A Delta^2 / 2 >= 10 + r_* + 20. Put
g_h(t) = ( 2 pi h )^{-1/2} exp( - t^2 / (2h) ) ,
M = integral over t in R of g_h(t) e^{it HH'} W e^{-it HH} dt .
M is a contraction: it is the average over t of a product of unitaries
and W, with W a contraction. The spectral theorem applied to each
factor of the integrand gives
M Psi = e^{-h (HH' - E_E)^2 / 2} W Psi ,
M^dagger Phi = e^{-h (HH - E_E)^2 / 2} W^dagger Phi .
Using Lemma 1.5, the distance of each right-hand side from its target
is at most e^{-h Delta^2/2}:
|| M Psi - z Phi ||, || M^dagger Phi - z Psi ||
<= e^{-h Delta^2 / 2} . (2.11)
Both bounds matter; we will need not only that M sends Psi close to
Phi, but that M is almost isometric on Psi. Already with (2.10) and
(2.11) we may correct a bit: writing D = M / z, we have
|| D Psi - Phi || <= e^{-8b} * e^{-h Delta^2/2} ... see below,
|| D^dagger Phi - Psi || <= e^{-8b} * e^{-h Delta^2/2} ... see below,
in a form we will make explicit in Step 8.
Truncation of the Gaussian. Cut the integral to |t| <= T = T_0 B_*.
The resulting operator norm error in the truncated M is at most
2 e^{-T^2 / (2h)} = 2 e^{-T_0^2 B_* / (2A)} .
Choosing T_0 after A with
T_0^2 / (2A) >= 10 + r_* + 20
makes that error at most e^{-10b} L^{-r_*}, up to a harmless fixed
factor. So we may work with the truncated integral without changing
the two-sided estimate (2.11) up to a factor we track in Step 8.
What remains is to localize the truncated integral off the cores
R_0 union C_0. That is Step 6 and Step 7.
Step 6: the Lieb-Robinson bound. This is the standard commutator
recursion, recorded so that no external reference is needed.
Let K stand for either doubled Hamiltonian HH or HH'. For a norm-one
operator B_y supported on a single site y, define
c_y(S,t) = sup { || [ tau_t(A), B_y ] || :
supp A subset S, ||A|| <= 1 } ,
tau_t(A) = e^{i t K} A e^{-i t K} .
Write the interaction terms of K as k_Z, one per support Z. Then
c_y(S,t)
<= c_y(S,0)
+ 2 sum_{Z : Z meets S} ||k_Z||
integral_0^t c_y(Z,v) dv . (2.12)
Why. Differentiate [tau_t(A), B_y] with respect to t and use the Jacobi
identity to write the derivative as the sum over interactions meeting
the support of A. The homogeneous part is the commutator by the
Hermitian operator sum_{Z : Z meets S} tau_t(k_Z), and is removed by a
unitary change of frame; what remains is a bound of 2||A|| ||k_Z||
c_y(Z,t) for each term Z. Negative times give the same bound.
Iterating (2.12) produces chains of overlapping interaction supports
with factorial time denominators. Only chains that reach y contribute
an initial commutator. The first support has at most C|S| choices,
each subsequent interaction support has at most a fixed number of
choices (bounded interaction degree), and a chain reaching site-graph
distance d_K(S,y) from S must have length at least a fixed multiple of
that distance, up to an additive constant. Bounding the resulting
exponential series with a weight on chain length gives constants
v, mu, C > 0, depending only on the local interaction bounds, with
|| [ tau_t(A), B_y ] ||
<= C |S| ||A|| exp( v|t| - mu d_K(S,y) ) . (2.13)
The remainder of the iteration vanishes by its factorial denominator.
The next step is to average away everything outside a ball. For a site
set D, let P_D be the conditional expectation onto operators supported
on D, defined by Haar-averaging over independent unitaries at every
site outside D. P_D is a contraction and preserves Hermiticity.
Successively averaging single sites, and applying (2.13) to each, gives
|| tau_t(A) - P_{N_l(S)} tau_t(A) ||
<= C |S| L^2 ||A|| exp( v|t| - mu l ) . (2.14)
The L^2 counts the sites outside N_l(S) that are averaged; no
Hilbert-space dimension appears in the bound.
Step 7: localizing the truncated integral. Let Z_R be the set of
endpoints of physical edges that cross R. Put
V(t) = e^{i t HH'} e^{-i t HH} .
Its left generator is
d/dt V(t) = i G(t) V(t) , G(t) = e^{i t HH'} (HH' - HH)
e^{-i t HH'} .
The difference HH' - HH is a sum of O(L) uniformly bounded terms, each
supported on at most two sites of Z_R (the constants are loose by fixed
polynomial factors; nothing below is sensitive to them). Applying
(2.14) term-by-term to those pieces, and using the size bound
|S| <= O(1) for a two-site support, replaces G(t) by a Hermitian
G_l(t) = P_{N_l(Z_R)} G(t) ,
with
|| G(t) - G_l(t) || <= C L^4 exp( v|t| - mu l ) .
Here the power 4 is the loose count of (physical crossing edges) times
(sites in a full physical sample) and is harmless in what follows.
Let V_l(t) be the unitary generated by G_l(t) with V_l(0) = id; it is
supported on N_l(Z_R). Duhamel's formula for two unitary evolutions
gives
|| V(t) - V_l(t) || <= C L^4 |t| exp( v|t| - mu l ) .
Next, localize the other factor. Apply the conditional expectation
P_{N_l(Q)} to e^{i t HH'} W e^{-i t HH'}, where Q = (R union C)^c is the
buffer on which W lives. The result is a contraction; the error is at
most C L^4 exp(v|t| - mu l), by (2.14) applied to W term-by-term. The
factorization
e^{i t HH'} W e^{-i t HH}
= ( e^{i t HH'} W e^{-i t HH'} ) V(t)
therefore has a contraction approximation supported on
S = N_l( Q union Z_R ) ,
with an operator-norm error at most
C L^4 (1 + |t|) exp( v|t| - mu l ) ,
uniformly for |t| <= T. If Q or Z_R is empty, its factor is already a
scalar or the identity and needs no localization; the estimate below
still holds.
Take
l = ceil( K_loc B_* ) ,
with K_loc a fixed large enough integer. Because log L <= B_* and
log(1+T) <= C + B_*, choosing K_loc after T_0 makes the last bound at
most C exp(-10b) L^{-r_*}. Averaging the resulting localized
integrands against the truncated Gaussian gives a square operator
M_loc, supported on S, with ||M_loc|| <= 1 and
|| M_loc Psi - z Phi || , || M_loc^dagger Phi - z Psi ||
<= C exp(-10b) L^{-r_*} . (2.15)
Combining three sources of error: the two-sided Gaussian estimate, the
truncation, and the localization. All three were chosen to land at the
same order.
Step 8: the polar factor. Set
D = M_loc / z .
Using z >= exp(-2b) from (2.10), and the two-sided bound (2.15),
|| D || <= exp(2b) ,
|| D Psi - Phi || <= C exp(-8b) L^{-r_*} ,
|| D^dagger Phi - Psi || <= C exp(-8b) L^{-r_*} ,
|| (D^dagger D - id) Psi || <= C exp(-6b) L^{-r_*} . (2.16)
The last line is the telescoping
D^dagger (D Psi - Phi) + (D^dagger Phi - Psi), with ||D^dagger|| <=
exp(2b). The large norm of D has been paid for explicitly; no unitary
dilation on an additional system is used.
Let
D = W |D| , |D| = (D^dagger D)^{1/2} ,
be the polar decomposition, with W a partial isometry whose support is
the orthogonal complement of ker |D|. Extend W to a unitary U on the
finite-dimensional Hilbert space H_S (its two support subspaces have the
same dimension, because D and D^dagger have the same rank, and their
orthogonal complements do too). Tensor U with the identity outside S.
Apply the scalar inequality (sqrt(x) - 1)^2 <= (x - 1)^2 for x >= 0 in
the spectral decomposition of D^dagger D. It gives
|| (id - |D|) Psi || <= || (id - D^dagger D) Psi || .
Because |D| annihilates ker |D| and U agrees with W on the complement of
ker |D|, an expansion of U Psi - D Psi as
W (id - |D|) Psi_{perp} + U Psi_{ker} ,
where Psi = Psi_{perp} + Psi_{ker} is the splitting along ker |D|,
gives
|| U Psi - D Psi || <= 2 || (id - |D|) Psi || .
Consequently
|| U Psi - Phi ||
<= 2 || (id - |D|) Psi || + || D Psi - Phi ||
<= 2 || (id - D^dagger D) Psi || + || D Psi - Phi ||
<= C exp(-6b) L^{-r_*} . (2.17)
So there is a unitary U on the doubled space, supported on S, that sends
Psi close to Phi, with an error controlled entirely by b and L.
Step 9: support check, and the trace-distance conclusion. First check
that S really misses the two cores in both replicas.
Every site of Q = (R union C)^c is more than w from R_0 and from C_0,
by the hypotheses (2.8). For an edge that crosses R, write its
endpoints as x in R and y notin R. Since y is notin R and
dist(R_0, Lambda \ R) > w, y is more than w from R_0, so x is more than
w - 1 from R_0. Since R and C are disjoint, x in C^c is more than w
from C_0, so y is more than w - 1 from C_0. Hence every site of Z_R is
more than w - 1 from both cores. Choose C_p in (2.8) strictly larger
than K_loc + 3. Then S = N_l(Q union Z_R) is at distance more than
zero from R_0 union C_0, so it is disjoint from both cores, in both
replicas, and so U leaves the (R_0 from one replica, C_0 from the other
replica) two-copy marginal unchanged.
What this machinery gives. In Psi = Omega tensor Omega, the joint
marginal on (replica-1 sites of R_0 union C_0) is rho_{Omega, R_0 union
C_0}. In Phi = F_R Psi, on the same sites, the R_0 part comes from the
other original replica, so the joint marginal is rho_{R_0} tensor
rho_{C_0}. Since U is the identity on those sites, and U Psi is within
C exp(-6b) L^{-r_*} of Phi in vector norm,
|| rho_{Omega, R_0 C_0} - rho_{R_0} tensor rho_{C_0} ||_1
<= 2 || U Psi - Phi || <= C exp(-6b) L^{-r_*}. (2.18)
Now apply the entropy continuity bound (Lemma 1.4) to the difference
(2.18). Letting
delta = (1/2) || rho_{Omega, R_0 C_0}
- rho_{R_0} tensor rho_{C_0} ||_1
<= C exp(-6b) L^{-r_*} <= C L^{-r_*} ,
and using I(R_0:C_0) = S(R_0) - S(R_0|C_0), the continuity gives
| I( R_0 : C_0 ) |
<= C sqrt(delta) L^2 <= C L^{2 - r_*/2} = C L^{-p-3} .
Here r_* = 2p + 10 was chosen with two units of slack. Therefore
I_Omega( R_0 : C_0 ) <= C L^{-p-3} <= L^{-p}
for all sufficiently large L. This proves the Lemma. END PROOF.
Remarks. Two points are easy to lose sight of.
First, the gap entered exactly once: in the two-sided Gaussian estimate
(2.11), through Lemma 1.5. No gap was assumed for R or for C or for
any subregion. The information hypothesis was the only non-spectral
input.
Second, no dimension appears anywhere in the constants. The private
spaces B_R and B_C could have been arbitrarily large; they disappeared
from W because W was defined as an outer conjugation by V tensor V,
and V acts on H_Q only. That disappearance is what makes Lemma 2.4
usable in the frame operations of Part 5, where the buffers are
private spaces of unbounded dimension.
2.4 Regions tapering toward finitely many points
-------------------------------------------------
The two ingredients just proved combine into the statement used by the
frame operations of Part 5. Informally: a region X, whose distance from
an exterior E shrinks toward a finite set of marked points V but never
falls below a fixed multiple of log L, carries negligible information
with E.
The statement is quantitative and its constants are intertwined. We
will choose
the cell size constant from Lemma 2.3,
the reset width constant from Lemma 2.4,
and only then the scale-floor constant D
in that order, so no constant is chosen as a function of L.
PROPOSITION 2.5 (information under angular separation).
Fix a > 0, A_0 >= 1, an integer m_0 >= 0, and p > 0. There is
D = D(a, A_0, m_0, p, q, J, Delta) < infinity with the following property
for all sufficiently large L. Let V be a set of at most m_0 marked
points in the plane, let X, E be disjoint subsets of Lambda, and let
D log L <= n <= A_0 L , diam_inf( X ) <= A_0 n .
Put s_min = D log L and
d_V(x) = min_{v in V} |x - v|_inf ,
with d_{empty} = +infinity. Suppose that for every x in X,
dist_inf( x, E ) >= a * max{ s_min, min( n, d_V(x) ) } . (2.19)
Then
I_Omega( X : E ) <= L^{-p} .
The constant D and the scale threshold are uniform in the marked points,
in the physical sets, and in the Hamiltonian.
PROOF.
Empty X or empty E is trivial, as is a case where X is a single point
and the information is bounded by 2 log q <= L^{-p} for large L. So
assume X is nonempty and E is nonempty.
Choice of the small clearance constants. Fix
a' > 0
with a' < min(a/100, 1/100), and then fix a small positive d with
d < a'/4. These depend only on a and on the fixed parameters.
Dyadic scales. Take dyadic scales
s_j = 2^{-j} n , 0 <= j <= m ,
decreasing from s_0 = n down to s_min, so that
s_min <= s_m < 2 s_min .
There is exactly one such m for each n and s_min, and it satisfies
m = O( log( n / s_min ) ).
Layered decomposition of X. Split X into layers ordered by distance
from the marked points, from farthest to nearest:
Layer 0: { x in X : d_V(x) >= n }.
For 1 <= j < m:
Layer j: { x in X : s_j <= d_V(x) < 2 s_j }.
Last layer: the remaining points, i.e. those with d_V(x) < 2 s_m.
Special case m = 0: there is only one layer, X itself.
Let A_j be the union of the first j+1 layers, i.e. the points of X
that have been processed at scale s_j (including the current layer).
Two facts about separation. First, in every case (2.19) and the
definition of A_j give
dist_inf( A_j, E ) >= (a/2) s_j . (2.20)
Indeed:
For layer 0, min(n, d_V(x)) = n, so max{s_min, n} = n, and
(2.19) gives dist(x,E) >= a n >= (a/2) s_0.
For 1 <= j < m, d_V(x) < 2 s_j <= s_0 = n, so min(n, d_V) = d_V >=
s_j, and max{s_min, d_V} >= s_j, so dist(x,E) >= a s_j.
For the last layer, min(n, d_V) may be as small as zero, but
max{s_min, min(n, d_V)} >= s_min, and s_m < 2 s_min, so
dist(x,E) >= a s_min > (a/2) s_m.
In every case dist(x,E) >= (a/2) s_j, so the same holds after
taking the minimum over A_j.
Second, each layer is covered by a bounded number of ambient squares
of side s_j, with a bound depending only on A_0 and m_0. For layers
1, 2, ..., m-1 and the last one, the layer lies inside the union of
the radius-2s_j squares about the at most m_0 marked points. For
layer 0, the diameter bound on X gives the cover.
The invariant. After processing scale s = s_j, we will establish
I_Omega( Lambda intersect A_j^{+a' s} :
Lambda intersect E^{+a' s} ) <= L^{-p} . (2.21)
This is what the induction proves. Once it holds at j = m, and since
A_m = X, we discard the padding from both arguments to obtain
I_Omega(X:E) <= L^{-p}. That is the conclusion.
Annular step from scale 2s to scale s. Fix j and suppose that the
previous scale 2s = s_{j-1} has been processed. At the first scale
take A_old = empty and run the same argument with the empty initial
group.
Cover. Take an ambient grid of cells of side d * s. Let
R = the physical sample of the union of all cells that touch
the ambient radius-1.5 a' s enlargement of A_j.
That is, R includes every cell that intersects A_j^{+1.5 a' s}, and then
includes the whole cell. Put
C = Lambda intersect E^{+1.5 a' s} .
Both R and C are unions of cells of the grid, and R contains the
physical radius-1.5 a' s enlargement of A_j, so it contains A_j^{+a' s}
in particular. Likewise C contains E^{+a' s}.
Initial group. Among the selected cells (the ones comprising R),
group together those that touch A_old^{+1.5 a' s}. Every such cell lies
inside the ambient radius-(1.5 a' + d) s enlargement of A_old, hence
inside its previous radius-2 a' s enlargement, since 1.5 a' + d < 2 a' by
d < a'/4. And C is contained in E^{+2 a' s}. By the induction
hypothesis and data processing:
I_Omega( initial group : C )
<= I_Omega( Lambda intersect A_old^{+2 a' s} :
Lambda intersect E^{+2 a' s} )
<= L^{-p} ,
by the invariant at scale 2s. (Edge case: when A_old = empty, the
initial group is empty and its mutual information with C is zero, so
the bound L^{-p} holds trivially.)
Data processing (monotonicity of mutual information under discarding
parts of either system) turns the previous invariant into the bound on
the initial group.
Remaining cells. Every other selected cell touches A_j^{+1.5 a' s}.
The enlargement of a union is the union of its enlargements, so the
remaining cells cover the layer being added, in the sense that they
include every cell that intersects (A_j \ A_old)^{+1.5 a' s}. By the
bounded-square cover of the layer and the fixed ratio d, there are
only boundedly many remaining cells.
Clearance. For any remaining selected cell, and for any x in the cell,
the point x is within (1.5 a' + d) s of A_j. So the distance of the
cell from E is at least
(a/2 - 1.5 a' - d) s > 0, (2.22)
by (2.20) and by d < a'/4 and a' < a/100. In particular, the cell's
distance from C is at least a fixed positive multiple of its side d s,
and R and C are disjoint.
Apply Lemma 2.3 to add each remaining cell, one at a time. Let the
previously included part be a union of whole cells; then its sites are
a union of cells, and the chain rule plus Lemma 2.3 applies at each
addition. For all sufficiently large L we have d s >= d D log L above
the Lemma's fixed scale threshold, and (2.22) above the Lemma's cell
clearance. After absorbing the initial contribution L^{-p} and the
bounded number of additions,
I_Omega( R : C ) <= C_b ( 1 + log s )^K . (2.23)
Here C_b and K are fixed, independent of D, L, and the current layer.
Apply the reset. Set
R_0 = Lambda intersect A_j^{+a' s} ,
C_0 = Lambda intersect E^{+a' s} .
The set R contains the physical radius-1.5 a' s enlargement of A_j, so
every site of R_0 is at distance at least a' s / 2 from the physical
complement of R. Likewise, every site of C_0 is at distance at least
a' s / 2 from the physical complement of C. We may take the available
width to be c_* s with c_* = a'/3, strictly smaller than a' / 2, as
the hypothesis of the reset requires.
In view of (2.23), the width required by the reset is at most
w(s) <= C_3 (1 + log s)^K + C_4 log L , (2.24)
with C_3, C_4 fixed (they absorb C_p and the fixed data).
Choice of D. We must have w(s) < c_* s for every scale s >= D log L.
First fix the constants in the cell bound and in the reset, including
K, C_3, C_4, c_*. Then choose the fixed integer D large enough that
D >= 4 C_4 / c_* .
The function
f(s) = (1 + log s)^K / s
has logarithmic derivative
f'(s) / f(s) = (1/s) * ( K / (1 + log s) - 1 ) ,
so it is decreasing for s > e^{K - 1}. Increase the fixed threshold
L_0 so that, for every L >= L_0,
D log L >= e^{max(K, 1)} ,
C_3 (1 + log(D log L))^K / (D log L) <= c_* / 2 .
Such an L_0 exists because (log log L)^K / log L -> 0 as L -> infinity
for every fixed K.
For every scale s >= D log L, we then have
w(s) / s <= C_3 f(D log L) + C_4 / D
<= c_* / 2 + c_* / 4
= 3 c_* / 4 < c_* .
Thus the reset hypotheses hold at every scale. Its conclusion gives
I_Omega( R_0 : C_0 ) <= L^{-p} ,
which is exactly the invariant (2.21) at scale s.
Induction. The argument above starts at the first scale with A_old =
empty and the base case giving I(initial group : C) = 0, and it produces
(2.21) at the next scale. By induction over j = 0, 1, ..., m,
(2.21) holds for every j.
Conclusion. At j = m we have A_m = X, so the invariant reads
I_Omega( Lambda intersect X^{+a' s_m} :
Lambda intersect E^{+a' s_m} ) <= L^{-p} .
Discarding the padding (monotonicity) gives I_Omega(X:E) <= L^{-p}.
END PROOF.
A concrete reading of the exponents. In every use of Lemma 2.4 in Part
6, the target error is L^{-60} (so p = 60). The reset lemma then
requires a collar of width C_60 (1 + log L). Proposition 2.5 provides
that collar, at separation floor D log L with D = D(a, A_0, m_0, 60,
q, J, Delta) fixed.
What the proposition says, in words. Suppose two physical sets X and E
are separated by a distance that is at least a fixed fraction of the
smaller of (a) the size of X itself and (b) the distance of the point
in question from the nearest of a fixed number of marked points. And
suppose this separation never falls below D log L. Then X carries only
L^{-p} of mutual information with E, regardless of the shapes of X and
E and regardless of the exterior conditioning. The tapered shape and
the logarithmic floor are the only things that matter, and D is fixed
once and for all.
================================================================
PART 3. FINITE-RANK CONSTRAINTS ON SMALL PATCHES
================================================================
A PEPS has a physical tensor at every site. Before we can distribute
registers among parties in Part 5, we need to substitute, near each
junction of a guide, a small finite-rank description of Omega. "Small"
means a rank bounded by a fixed power of L; "near a junction" means a
patch whose radius is at most a fixed multiple of log L.
The central point is that the accurate finite-rank truncation is not
available at a single prescribed radius. A truncation at radius u
would control the Schmidt spectrum of Omega across the boundary of a
fixed square of radius u; the resulting rank would depend on u and, in
general, on Omega. What is available is a truncation realized by a
projection supported in a slightly larger square, whose range is a sum
of subspaces at several radii u_1 <= u_2 <= ... <= u_m, each nested
inside the next, whose radii may vary with the term. The total rank
across all terms is bounded by a fixed power of L. This adaptive form
is what makes the construction in Parts 5 and 6 possible. The proof
goes through a regularized nested-filter variational problem, whose
stationary points can be analysed without ever commuting the filters.
For a center z in the plane and radius r >= 0 put
X(r) = { v in Lambda : |v - z|_inf <= r } ,
the physical square sample of radius r about z (possibly clipped by the
outer boundary of Lambda). For a subspace S of H_{X(r)}, the cylinder
S tensor H_{ Lambda \ X(r) }
has "inside rank" dim S.
3.1 The adaptive patch constraint
----------------------------------
PROPOSITION 3.1 (adaptive patch constraint).
Fix B_0 > 0 and p > 0. There exist constants C, c > 0, depending only
on q, J, Delta, B_0, p, with the following property. For every
L >= 2, center z in the plane, and radius
0 < u <= B_0 log L ,
there is an orthogonal projection P supported on X(2u) such that
|| (id - P) Omega || <= L^{-p} . (3.1)
Moreover, there are radii
u <= r_1 <= r_2 <= ... <= r_m <= 2 u ,
sets X_j = X(r_j), and unit vectors v_{j ell} in H_{X_j}, 1 <= ell <=
d_j, for which
P = sum_{j=1}^m sum_{ell=1}^{d_j}
|v_{j ell}><v_{j ell}|_{X_j}
tensor id_{ Lambda \ X_j} , (3.2)
sum_{j=1}^m d_j <= C L^c . (3.3)
All the summands of (3.2) have pairwise orthogonal ranges as operators
on H_Lambda. No bound on the internal tensor complexity of the
individual v_{j ell} is asserted.
3.2 The proof of Proposition 3.1
---------------------------------
PROOF.
Two elementary reductions. If u < 4, take P = id. Expanded in an
orthonormal basis of H_{X(u)} (which has at most 81 sites, hence
dimension at most q^81), it already has the form (3.2) with m = 1,
r_1 = u, and d_1 = q^{81}. This covers empty physical samples too. We
suppose henceforth that u >= 4.
Nested squares and the variational problem. Put
m = floor(u/2) + 1 ,
r_j = u + 2(j-1) , X_j = X(r_j) ,
a_j = kappa / m ,
where 0 < kappa <= 1/2 will be fixed below using only the physical
parameters. Then r_m <= 2u, m >= u/2, and sum_j a_j = kappa. The
samples X_j need not be distinct; nesting X_1 subset of X_2 subset of
... holds by construction.
For R >= 0 put b = e^{-R}. Minimize, over density operators x_j on
H_{X_j} chosen independently for each j, the quantity
N(R) = min over {x_1,...,x_m} || M(R,x) Omega || ,
M(R,x) = L_m ... L_1 ,
L_j = ( x_j + b id )^{-a_j / 2} . (3.4)
Operators on X_j are extended by the identity on the complement of X_j.
The variational problem is well posed. The feasible set (a product of
state spaces) is compact and every filter L_j is positive and
invertible (because b > 0). Since 0 <= x_j <= id,
(1 + b)^{-kappa/2}
<= || M(R,x) Omega || <= b^{-kappa/2} . (3.5)
The lower bound follows by multiplying the least singular values of the
factors and using ||Omega|| = 1; it does not require the L_j to
commute. Thus the minimum is attained and is positive.
At any minimizing tuple, set
phi = L_m ... L_1 Omega / N(R) ,
rho_j = Tr_{ Lambda \ X_j } |phi><phi| .
Every statement below about the minimizer holds for every minimizing
tuple, even when it is not unique.
The minimization problem was chosen for the following reason. Stationarity
of the filters will bound the excitation energy of phi independently of
R and of the choice of minimizer. The full-system gap then makes the
marginals of phi close enough to those of Omega that the area law can
bound a subspace of rank e^{O(1+u)} carrying all but a fixed small
fraction of each marginal. That will force log N(R) to grow slowly:
log N(R) <= kappa R/8 + O(1+u). We will then split each inverse filter
into a piece of inside rank at most e^R and a remaining piece of norm at
most (2e^{-R})^{a_j/2}. The "all-remaining" branch of the split decays
exponentially in R. Every other branch has a finite-rank factor and
lands in a cylinder at that factor's radius. This is the origin of the
adaptive form (3.2)-(3.3).
Step 1: stationarity does not require commuting filters. We prove, in
decreasing order of j from m down to 1, that
[ L_j , rho_j ] = [ x_j , rho_j ] = 0 . (3.6)
The trace identity behind the induction is this. If [L_k, rho_k] = 0
and T is an operator supported on X_k, then
< phi , L_k T L_k^{-1} phi >
= Tr( L_k^{-1} rho_k L_k T )
= < phi , T phi > . (3.7)
The middle equality is the trace-cyclicity identity
Tr(rho_k L_k T L_k^{-1}) = Tr(L_k^{-1} rho_k L_k T), which is
legitimate because the three factors are bounded. In a product of
outer conjugations, (3.7) is applied successively from the outermost
square inward: by nesting, the operator remaining inside each conjugation
is supported on that square.
Induction step. Assume (3.6) has been proved for all k > j, and let B
be any anti-Hermitian operator on X_j. Vary x_j by
x_j(s) = e^{sB} x_j e^{-sB}, keeping all other variables fixed. Functional
calculus gives
L_j(s) = e^{s B} L_j e^{-s B} ,
( dL_j(s)/ds )_{s=0} L_j^{-1}
= B - L_j B L_j^{-1} .
For a differentiable invertible M(s), its logarithmic norm derivative on
the fixed input Omega is
( d/ds log || M(s) Omega || )_{s=0}
= Re < phi , M'(0) M(0)^{-1} phi > .
Here M'(0) M(0)^{-1} is B - L_j B L_j^{-1} conjugated by L_m ... L_{j+1}.
Strip those outer conjugations using (3.7) for k = j+1, ..., m (each
with T supported on X_j, which is contained in X_k by nesting).
Stationarity at the minimum yields
0 = Re Tr( rho_j ( B - L_j B L_j^{-1} ) )
= Re Tr( rho_j B ) - Re Tr( L_j^{-1} rho_j L_j B ) .
The term Tr(rho_j B) is purely imaginary, being the trace of a Hermitian
times an anti-Hermitian. Hence
Re Tr( L_j^{-1} rho_j L_j B ) = 0
for every anti-Hermitian B. An operator whose real trace pairing with
every anti-Hermitian operator vanishes is Hermitian. So L_j^{-1} rho_j
L_j equals its Hermitian adjoint, and therefore
L_j^{-1} rho_j L_j = L_j rho_j L_j^{-1} ,
rho_j L_j^2 = L_j^2 rho_j .
Positivity of L_j gives commutation with L_j; functional calculus then
gives commutation with x_j. This starts at j = m with no outer filters
and proves (3.6) by induction. No commutation between two different
filters has been claimed.
Step 2: an effective potential for the filter eigenvalues. In a common
eigenbasis of x_j and rho_j, write x_i and p_i for the eigenvalues.
A diagonal variation of x_j within the probability simplex has
logarithmic norm derivative
- (a_j/2) sum_i p_i / ( x_i + b ) dx_i .
Again, this follows by stripping the outer conjugations using (3.7);
the diagonal variation commutes with x_j + b id. For two indices with
x_i, x_k > 0, mass can be moved in either direction, so the ratios
p_i / (x_i + b) agree. Moving mass from an index with x_i > 0 to any
zero coordinate gives the one-sided inequality. Thus there is a
Lagrange multiplier lambda > 0 with
p_i / (x_i + b) = lambda for x_i > 0,
p_i / b <= lambda for x_i = 0. (3.8)
If the common ratio on the positive coordinates were zero, the second
inequality would force every p_i to be zero, contradicting Tr rho_j = 1.
Writing r for the number of positive x_i, we also get
lambda ( 1 + b r ) = sum_{x_i > 0} p_i <= 1 ,
so 0 < lambda <= 1 .
Equivalently,
x_i + b = max{ p_i / lambda , b } . (3.9)
If ell_i = (x_i + b)^{-a_j/2} is the corresponding eigenvalue of L_j,
then for p_i, p_k > 0,
| log( ell_i / ell_k ) |
<= (a_j / 2) | log( p_i / p_k ) | . (3.10)
This follows because the map t -> max{t, log b} is 1-Lipschitz, applied
to log(p_i / lambda). The regularization keeps every ell_i finite,
including on zero marginal eigenspaces, so no ratio of zero probabilities
is ever formed.
Step 3: a dimension-free energy estimate. We next show that the
minimizing vector has uniformly small excitation energy. The two
distances |x - z|_inf and |y - z|_inf at the endpoints of a
nearest-neighbour edge differ by at most one. A closed square of
radius r cuts that edge only when
min{ |x - z|_inf , |y - z|_inf } <= r
< max{ |x - z|_inf , |y - z|_inf } .
Since selected radii differ by at least two, an interaction crosses at
most one selected square. If it crosses X_j, then its support is
disjoint from every X_k with k < j, and is contained in every X_k with
k > j. This holds including exact boundary equalities and repeated
clipped samples.
The ground equation gives
M H M^{-1} phi = E_0 phi .
For an interaction h that crosses X_j, remove the conjugations by the
containing outer filters using (3.7). The smaller filters commute with
h by disjointness. Therefore
< phi , M h M^{-1} phi > = < phi , L_j h L_j^{-1} phi > . (3.11)
For a term that crosses none of the selected squares the same argument
leaves its original expectation unchanged: strip the containing
filters, then commute past all disjoint ones. On-site terms never
cross a square.
Step 4: pairwise estimate for the filter action on a Hermitian
interaction. Consider a Hermitian nearest-neighbour term h crossing
X_j. Use the Schmidt decomposition of phi across X_j and its
complement:
phi = sum_{ i : p_i > 0 } sqrt(p_i) e_i tensor f_i ,
with the e_i chosen in a simultaneous eigenbasis of L_j and rho_j (which
is legitimate by (3.6)). Put h_{ik} = < e_i tensor f_i , h ( e_k tensor
f_k )>. Hermiticity gives h_{ki} = conjugate(h_{ik}). Pairing the
(i,k) and (k,i) terms consequently gives
Re< phi , L_j h L_j^{-1} phi > - < phi , h phi >
= sum_{ i,k : p_i p_k > 0 } sqrt( p_i p_k )
( cosh( log( ell_i / ell_k ) ) - 1 )
Re h_{ik} . (3.12)
For 0 <= alpha <= 1, the power series of the hyperbolic cosine shows
that
cosh( alpha y ) - 1 <= alpha^2 ( cosh y - 1 ) <= alpha^2 cosh y .
Using (3.10) and the identity
sqrt(p_i p_k) cosh( (1/2) log( p_i / p_k ) ) = (p_i + p_k) / 2, the
nonnegative coefficient in (3.12) is bounded by
sqrt(p_i p_k) ( cosh( log(ell_i / ell_k) ) - 1 )
<= (a_j^2 / 2) (p_i + p_k) . (3.13)
Zero Schmidt probabilities contribute zero to the expectation and need
no separate limiting argument.
Step 5: the rank-free Cauchy-Schwarz. Here is the step that prevents a
Schmidt-rank factor from entering. For operators A on X_j and B on its
complement, let A_{ik} = < e_i , A e_k > and B_{ik} = < f_i , B f_k >,
restricted to the displayed Schmidt vectors. Cauchy-Schwarz in a row
and in a column gives
sum_k | A_{ik} B_{ik} | <= ||A|| ||B|| ,
sum_i | A_{ik} B_{ik} | <= ||A|| ||B|| .
It follows that
sum_{i,k} (p_i + p_k) | A_{ik} B_{ik} |
<= 2 ||A|| ||B|| . (3.14)
Expand h in matrix units on its endpoint inside X_j:
h = sum_{a,b = 1}^q |a><b| tensor h_{ab} ,
||h_{ab}|| <= ||h|| <= J.
The other factors are extended by identities within their respective
sides of the cut. Combining (3.12)-(3.14) term by term yields the
explicit bound
| Re< phi , L_j h L_j^{-1} phi >
- < phi , h phi > |
<= q^2 J a_j^2 . (3.15)
Step 6: total excitation energy, and the marginal closeness of phi to
Omega. The ambient sample of a square of radius at most 2u has at most
16 u + 4 crossing lattice edges. Intersecting with the physical square
cannot add a physical crossing edge. Hence, using the ground equation,
(3.11), and (3.15),
0 <= < phi , (H - E_0 I) phi >
<= q^2 J (16 u + 4) sum_{j=1}^m a_j^2
<= 36 q^2 J kappa^2 . (3.16)
The last inequality uses m >= u/2 and u >= 4. This bound is
independent of R, of the private dimensions of the filters, and of the
choice of minimizer.
Set C_E = 36 q^2 J and now fix
0 < kappa <= min{ 1/2 , sqrt( Delta / (1024 C_E) ) } . (3.17)
The full-system gap, by Lemma 1.5, implies
1 - |< Omega , phi >|^2 <= C_E kappa^2 / Delta .
Up to a phase, || phi - Omega || <= (2 C_E / Delta)^{1/2} kappa.
The trace norm distance between the two pure-state density operators is
2 (1 - |<Omega,phi>|^2)^{1/2}. After partial trace, (3.17) therefore
gives
|| rho_j - rho_{Omega, X_j} ||_1 <= 1/16
for every j = 1, ..., m. (3.18)
Only the original full-system gap has been used.
Step 7: constant-tail ranks from the area law. Proposition 1.1,
together with the crossing-edge count, gives a constant C_S >= 1,
depending only on the physical parameters, such that
S_Omega( X_j ) <= C_S ( 1 + u ) .
Let Q_j be the spectral projection of rho_{Omega, X_j} onto eigenvalues
at least exp(-16 C_S (1+u)). Summing the retained eigenvalues shows
rank Q_j <= exp( C_Q (1+u) ) , C_Q = 16 C_S .
Markov's inequality for the marginal surprisal gives
Tr( rho_{Omega, X_j} (id - Q_j) ) <= 1/16 .
By (3.18),
Tr( rho_j (id - Q_j) ) <= 1/8 . (3.19)
Note that Q_j came from the original ground state. No entropy
continuity was applied to the filtered state.
Step 8: the regulator trace. At a minimizer define the commuting
positive product
T_j = rho_j b ( x_j + b id )^{-1} .
Equation (3.8) shows that its eigenvalues obey
0 <= p_i b / (x_i + b) <= b ,
p_i b / (x_i + b) <= p_i .
Thus 0 <= T_j <= b id and T_j <= rho_j. The projector Q_j need not
commute with T_j, but the positive operator inequalities suffice:
Tr T_j = Tr( Q_j T_j ) + Tr( (id - Q_j) T_j )
<= b rank Q_j + Tr( (id - Q_j) rho_j )
<= exp( -R + C_Q (1+u) ) + 1/8 . (3.20)
Choose, for example,
C_0 = C_Q + log 8 , R_start = C_0 ( 1 + u ) .
Then Tr T_j <= 1/4 whenever R >= R_start, uniformly over all minimizers.
Step 9: growth of the minimum. The regulator estimate will bound the
growth of log N(R). Its rate must stay below kappa/2, the exponential
decay rate of the inverse-filter remainder described below. Write
f(R,x) = log || M(R,x) Omega || , g(R) = log N(R) = min_x f(R,x) .
We justify the envelope calculation without choosing a continuous family
of minimizers. For fixed x,
d L_j / d R = (a_j / 2) b ( x_j + b id )^{-1} L_j ,
|| d L_j / d R || <= (a_j / 2) || L_j || .
On 0 <= R <= T, the product rule and (3.5) give
|| d M / d R || <= (kappa/2) exp( kappa T / 2 ) ,
|| M Omega || >= 2^{-kappa/2} .
Consequently
| d_R f(R,x) | <= (kappa/2) 2^{kappa/2} e^{kappa T/2} ,
for 0 <= R <= T. (3.21)
The bound holds for every feasible x and is independent of all Hilbert-
space dimensions and of m. The minimum g inherits the same Lipschitz
bound on each bounded interval, and is therefore locally absolutely
continuous.
Fix R and any minimizing tuple x_R. For h > 0,
g(R+h) - g(R) <= f(R+h, x_R) - f(R, x_R) .
The upper-right Dini derivative of g is therefore at most
d_R f(R, x_R). At the minimizer, the descending trace rule (3.7)
removes the outer filters in each term of the product derivative, giving
d_R f(R, x_R)
= sum_{j=1}^m (a_j / 2) Tr( rho_j b (x_j + b id)^{-1} ) .
By (3.20), this is at most kappa/8 for R >= R_start. At every point
where g is differentiable its derivative has this upper bound, so
absolute continuity permits integration. Using the trivial bound
g(R_start) <= kappa R_start / 2 from (3.5), we obtain
g(R) <= (kappa/2) ( R_start + R/4 ) for R >= R_start. (3.22)
Neither differentiability of a minimizing tuple nor uniqueness of that
tuple is required.
Step 10: the ordered expansion, and the all-tail remainder. Choose
R >= R_start and a minimizing tuple at that value. Let Pi_j be the
spectral projection of x_j onto eigenvalues at least b = e^{-R}.
Split the inverse filter, on its inside space, as
F_j = L_j^{-1} ,
F_j^h = F_j Pi_j ,
F_j^t = F_j (id - Pi_j) .
Since Tr x_j = 1,
rank F_j^h <= b^{-1} ,
|| F_j^t || <= (2b)^{a_j/2} . (3.23)
The rank in this display is on H_{X_j}, before extension by the outside
identity.
Inverting the ordered filter product gives
Omega = N(R) F_1 ... F_m phi .
Expand by the first head in the left-to-right order:
F_1 ... F_m
= sum_{j=1}^m
F_1^t ... F_{j-1}^t F_j^h F_{j+1} ... F_m
+ F_1^t ... F_m^t . (3.24)
This identity uses distributivity only, and it never changes the order
of noncommuting factors. Every factor preceding the j-th head acts
inside X_j. Hence the j-th summand applied to phi lies in
Cyl_j = S_j tensor H_{ Lambda \ X_j } ,
dim S_j <= b^{-1} ,
where S_j is the range on H_{X_j} of F_1^t ... F_{j-1}^t F_j^h. The
preceding factors may alter the head subspace, but cannot increase its
dimension.
The remaining vector has norm at most
N(R) prod_j || F_j^t ||
<= N(R) (2b)^{kappa/2} .
By (3.22), its logarithm is at most
(kappa/2) [ C_0 (1+u) + log 2 - 3 R / 4 ] . (3.25)
Step 11: explicit radius and the final distance bound. Set
R_0 = (4/3) [ C_0 ( B_0 + 1/log 2 )
+ 1 + 2 p / kappa ] ,
R = R_0 log L . (3.26)
For L >= 2 and u <= B_0 log L,
C_0 (1+u) <= C_0 ( B_0 + 1/log 2 ) log L ,
log 2 <= log L ,
so R >= R_start, and (3.25) is at most -p log L. Writing
E = sum_j Cyl_j, we have consequently proved
dist( Omega , E ) <= L^{-p} ,
dim S_j <= L^{R_0} . (3.27)
Step 12: orthogonalization at variable radii. Let P be the orthogonal
projection onto E. We finish by putting it into the required form,
keeping the radius associated with each summand. Process the cylinders
in increasing j. By nesting, the span of the earlier cylinders can be
written
E_{j-1} := sum_{i<j} Cyl_i
= W_j tensor H_{ Lambda \ X_j }
for a subspace W_j of H_{X_j}. Let P_{W_j} be the orthogonal projection
onto W_j, and define
S~_j = (id - P_{W_j}) S_j .
This is the projected image of S_j, not its intersection with
W_j^perp; it has dimension at most dim S_j and
E_{j-1} + Cyl_j = E_{j-1} + ( S~_j tensor H_{Lambda \ X_j} ) ,
with the right-hand side being a direct sum on H_Lambda. Choose an
orthonormal basis v_{j ell} of each S~_j. If S~_j is zero, there are no
terms for that j. The resulting cylinder ranges are pairwise orthogonal
and their direct sum is E, proving (3.2). Because X_j is contained in
X(2u), this projection is supported on X(2u). Equation (3.27) gives
its stated error.
Finally,
sum_j d_j <= m L^{R_0}
<= ( (B_0 / 2) log L + 1 ) L^{R_0}
<= C L^{R_0 + 1} .
Enlarging C absorbs the previous bounded-u case. The choices of
kappa, C_0, R_0 depend only on the fixed parameters in the proposition,
and all bounds are uniform in the center, in the Hamiltonian, and in L.
END PROOF.
A reader's summary. What the proposition delivers, in one sentence.
Near any center, at any scale u <= B_0 log L, we can project Omega onto
a subspace whose "inside" description uses at most CL^c dimensions,
where the inside description is a sum of small subspaces on nested
squares of possibly different radii. The projection error is L^{-p}.
The mechanism is a variational filter that is optimal but not
necessarily commuting, plus the area law for the tail ranks, plus the
gap for the marginal closeness of the filtered state.
================================================================
PART 4. COMPRESSION OF DISTRIBUTED DENSITY NETWORKS
================================================================
Parts 5 and 6 will describe Omega through a distributed protocol in
which auxiliary parties hold pieces of the state and swap pieces
privately. At the end of the protocol each party holds only a small
physical register; every other register is private. Tracing out the
private parts gives a physical density operator.
The purpose of Part 4 is to show that, whatever protocol we used, if
(a) each party participates in boundedly many nonprivate gates over its
whole lifetime, (b) each gate has a polynomial sum expansion into local
contractions and normalized bipartite resources, and (c) every party's
intended physical output is polynomially small, then the resulting
physical density is approximated, to any fixed inverse power of L, in
trace norm, by an operator tensor network with polynomial link
dimensions on the party graph. The approximation constants depend only
on the number of parties, the number of gates, the participation bound,
and the polynomial bounds on the expansion, and not on the private
Hilbert-space dimensions or on the Schmidt ranks of the bipartite
resources.
4.1 Distributed constructions
-------------------------------
A party is a label for a collection of registers. At every time the
memory is a tensor product of the parties' current Hilbert spaces.
A gate has specified input and output spaces for each participating
party; these spaces may differ. Registers outside the participating
parties are spectators. A private gate has one participating party.
Gates are linear contractions. Registers that are to be discarded are
retained as part of their owner's memory until the end, so the entire
construction is a pure linear calculation before any partial trace is
taken.
An allowed monomial in a gate expansion is a finite composition of
(i) local contractions (private maps),
(ii) preparations of normalized vectors shared between two
participating parties (pair sources),
(iii) contractions by normalized bras shared between two
participating parties (pair effects).
A transferred register of dimension d can also be allowed when d is
uniformly polynomial: expand its identity transfer as
sum_{a=1}^d |a>_{receiver} <a|_{sender} .
Each summand consists of local norm-one maps. A bounded number of such
transfers therefore changes a polynomial gate expansion by only a
polynomial factor. We always make this expansion first whenever such
messages occur.
The following lemma converts pair effects to pair sources while
approximating the gate in operator norm. The trick is to replace a
single effect by an average over m insertion slots of the same pair
state, with a control on the norm error. A common garbage vector makes
the errors summable across branches.
LEMMA 4.1 (elimination of normalized pair effects).
Let G be a contraction with an expansion G = sum_xi c_xi M_xi into K
allowed monomials on a fixed set of parties, and suppose each monomial
has at most r pair effects. For every integer m >= 1 there is a gate
G~_m, with additional garbage registers, and a fixed normalized garbage
vector Gamma_m, such that
|| G~_m - G tensor |Gamma_m> ||
<= (r / sqrt(m)) sum_xi |c_xi| . (4.1)
The gate G~_m has an expansion using only local contractions and
normalized pair sources, with at most K m^r monomials. The absolute
coefficient sum of these monomials is at most sum_xi |c_xi|. Its
additional registers are owned by the original participating parties.
All sources on the same pair of parties may be combined into one
normalized pair source.
PROOF.
One effect, one dimension. First consider a single normalized pair
vector eta in U tensor V. Its effect consumes a pair of registers in
this space. Append m-1 copies of eta, and average the m cyclic
permutations of the m pair registers. Each permutation is the tensor
product of the same cyclic permutation of the U registers at one party
and of the V registers at the other. Denote the resulting map by
T_m : U tensor V --> (U tensor V)^{tensor m} .
It is a contraction, being an average of isometries. It sends eta to
eta^{tensor m}. If v is perpendicular to eta, its m insertion positions
among the copies of eta are pairwise orthogonal, each with norm ||v||.
Consequently
|| T_m - |eta>^{tensor m} <eta| || = m^{-1/2} . (4.2)
If the perpendicular subspace is zero, the left side is zero. This
operator-norm estimate is unchanged by adjoining spectators. The
permutation average has m terms, each with coefficient 1/m and
consisting of local unitaries after normalized source preparation.
The whole gate. Index every prescribed effect occurrence by its
monomial and by its position within that monomial. For each such
occurrence, give the branch its own output stack of m pair registers,
with the dimensions and endpoint parties of its vector eta. In the
branch that uses that occurrence, replace its effect by T_m and leave
the stack idle thereafter. In every other branch, append the full
fixed stack eta^{tensor m} as a pair source. Thus every branch has the
same additional output space, and its ideal additional output is the
fixed vector
Gamma_m = tensor over prescribed occurrences o of
eta_o^{tensor m} .
Different branches may consume different internal registers in their
original effects; the occurrence-specific output stacks still give a
common external output space. No subsequent operation acts on a stack.
Telescoping. All original monomial factors, their ideal augmented
replacements, and the maps T_m are contractions. Telescoping the
at most r replacements in one monomial bounds its error by r/sqrt(m).
Summing with the original coefficients proves (4.1). Expanding the
active permutation averages creates at most m^r terms per original
monomial. Their averaging coefficients are nonnegative and sum to one,
so this expansion does not increase the absolute coefficient sum. The
inactive stacks require no extra summation labels. Finally, a tensor
product of normalized pair vectors on a fixed pair of parties is a
normalized pair vector on the tensor products of their respective
half-spaces. END PROOF.
The reason Lemma 4.1 is plausible, in words. A pair effect is a
projection onto a specific entangled state; on average, imposing that
specific state at one slot of m possible slots costs a norm error
1/sqrt(m), and m-1 pure pair sources can be supplied as shared resource.
Because the substitution is applied uniformly across branches of the
gate expansion, the telescoping bound depends on the number of effects
per monomial, not on the shape of the monomial or the dimension of any
space.
4.2 The distributed density-compression theorem
------------------------------------------------
THEOREM 4.2 (distributed density compression).
Consider a family of distributed constructions indexed by L >= 2 with
the following uniform properties.
(1) The number of parties and gates is uniformly polynomial. The
initial vector is a tensor product of normalized private vectors,
one at each party, and every gate is a contraction.
(2) There is a constant b such that each nonprivate gate involves at
most b parties, and each party participates in at most b
nonprivate gates over the entire construction.
(3) Each nonprivate gate is a sum of uniformly polynomially many
allowed monomials with uniformly polynomially bounded scalar
coefficients. There is a constant r bounding the number of pair
sources, pair effects, and polynomial-dimensional messages in
each monomial. All constituent local maps are contractions.
(4) At the end, the intended physical output space of each party has
uniformly polynomial dimension. All other registers are traced
out, party by party.
Write rho for the resulting physical output density operator; it is
positive and may have trace less than one. For every fixed p > 0 there
is an operator tensor network sigma satisfying
|| sigma - rho ||_1 <= L^{-p} . (4.3)
It has one node per party, a bounded number of incident virtual links
at each node, and uniformly polynomial link dimensions. Every link
joins two parties which participate in a common nonprivate gate of the
original construction. The physical legs at a node are the ket and bra
legs of that party's intended output. The constants in these bounds
depend only on p and on the fixed uniform data in the assumptions,
including b, r, and the polynomial bounds, and not on private
dimensions or on source Schmidt ranks.
The same conclusion holds if the gate expansions in assumption (3) are
available to every fixed inverse-polynomial operator-norm accuracy,
with uniform polynomial bounds at each fixed accuracy.
PROOF.
Error budget. We prove the assertion for a target error
0 < epsilon <= 1 whose inverse is uniformly polynomial, and then take
epsilon = L^{-p}. Expanding small messages as in Section 4.1
preserves all constant incidence and participation bounds, and gives a
uniformly polynomial absolute coefficient sum for every gate. We do
that first, and never revisit it.
The burden of the proof is in Step 5. In brief, after eliminating
effects (Step 1) we replace each source operator |eta><eta~| in the
density calculation by an unbiased sum of k product operators. We
estimate the resulting physical output, allowing the sampled factors
themselves to have large norms. Expanding the error by the positions
where a centered correction is used makes the lifetime participation
bound decisive: s corrected positions have at most 2s endpoint
parties, which together participate in at most 2bs nonprivate gates.
We expand only those gates into monomials; all other gates stay
aggregate contractions. Thus the coefficient and physical-output
choices cost a fixed polynomial per corrected position, rather than a
product over every gate in the construction.
For each fixed choice, the remaining task is a mean trace-norm estimate
of k^{-s/2}. Normalized probability weights from the corrected
endpoints and the exact sources crossing the boundary of their party
set make this estimate independent of all private dimensions. Summing
over correction positions then gives a small error with polynomial k.
Step 1: reduction to source-only gates. Let M bound the number of
nonprivate gates. If M = 0, the output is a product of private
densities and the assertion is immediate. Otherwise choose
delta = epsilon / (8 M) .
Apply Lemma 4.1 at every nonprivate gate, choosing one sufficiently
large polynomial integer m so that its error is at most delta. This
choice is made using the original coefficient sum and number of
effects (before expanding the permutation averages), so it is not
circular. Afterward there are polynomially many monomials, and their
absolute coefficient sum has not increased.
The gate G~_m has norm at most 1 + delta. Replace it by
G~_m / (1 + delta), a contraction within 2 delta of the original gate
with its fixed garbage appended. Keep these garbage registers idle.
The augmented original circuit has the same physical output density as
the original circuit, because all the appended garbage vectors are
fixed and normalized. Telescoping products of contractions shows that
the two final pure vectors differ by at most 2 M delta.
For vectors of norm at most one,
|| |v><v| - |w><w| ||_1 <= ( ||v|| + ||w|| ) || v - w ||
<= 2 || v - w || .
Partial trace does not increase this norm. Hence the source-only
circuit's physical density, denoted rho', satisfies
|| rho' - rho ||_1 <= 4 M delta <= epsilon / 2 . (4.4)
The number of gates and the list of participating parties have not
changed. The new polynomial exponents are now fixed. The sampling
parameter introduced in Step 5 is chosen only after this reduction.
Step 2: canonical source-gate form. Each nonprivate gate of this new
circuit can be written
G_g = sum_{xi in Xi_g} c_{g,xi}
( tensor_P B_{g,P,xi} )
[ ( tensor_{e in E_g} |eta_{g,e,xi}> )
tensor id_in ] , (4.5)
|| G_g || <= 1 .
Here E_g contains one slot for each pair of participating parties,
each eta_{g,e,xi} is normalized, and every B_{g,P,xi} is a local
contraction. Unused pairs have a one-dimensional source.
To obtain this form: prepare each monomial's sources in fresh registers
before their first use, and tensor the preceding local maps with
identities on those registers. This preserves their norms and their
chronological action. Then combine sources on each pair, and compose
the local maps at each party. Fresh registers are stored; existing
source halves are never commuted through earlier maps.
Step 3: common private slot spaces. The dimension of a source slot may
depend on xi. For each endpoint P of the pair e, embed its half-space
for branch xi isometrically into
H_{g,P,e} = direct sum over xi in Xi_g of H_{g,P,e,xi} .
Embed the branch source accordingly, and extend B_{g,P,xi} by
orthogonal projection onto its branch's source sectors. Its norm
remains at most one. All external gate input and output spaces are
already fixed by the memory layout and, in Step 1, by the common
inventory of stacks. The form (4.5) therefore has one fixed ambient
space for each slot. The direct sums are private spaces; no bound on
their dimensions is used or claimed.
Step 4: polynomial bounds. Fix uniformly polynomial bounds B(L) and
d(L) such that
sum_{xi in Xi_g} |c_{g,xi}| <= B(L) ,
dim H_{P,phys} <= d(L) , (4.6)
for all gates and parties. The cardinalities |Xi_g| are also uniformly
polynomial, and we may increase B and d to be at least one.
Step 5: a random replacement for one density source. Consider a
single source operator X = |eta><eta~| in the density calculation, one
ket branch and one bra branch at a slot. Write the Schmidt
decompositions in their respective bases as
|eta> = sum_a sqrt(lambda_a) |u_a> |v_a> ,
|eta~> = sum_c sqrt(mu_c) |u~_c> |v~_c> . (4.7)
Both probability lists sum to one; their lengths need not agree.
Let g_{ac}^{(j)}, for 1 <= j <= k, be independent standard circular
complex Gaussians, normalized by E|g_{ac}^{(j)}|^2 = 1. Put
U_j = sum_{a,c} (lambda_a mu_c)^{1/4} g_{ac}^{(j)}
|u_a><u~_c| ,
V_j = sum_{b,d} (lambda_b mu_d)^{1/4} conjugate(g_{bd}^{(j)})
|v_b><v~_d| ,
X^ = (1/k) sum_{j=1}^k U_j tensor V_j ,
X = |eta><eta~| ,
Delta = X^ - X . (4.8)
The matrices act between the corresponding bra and ket source supports
in the common ambient half-spaces of Step 3. No bound on their
sampled operator norms is claimed or needed.
Because E[g_{ac} conjugate(g_{bd})] = delta_{ab} delta_{cd},
E[X^] = X . (4.9)
The centered coefficient of Delta with ket endpoint indices (a,b) and
bra endpoint indices (c,d) is
(lambda_a lambda_b mu_c mu_d)^{1/4}
( (1/k) sum_j g_{ac}^{(j)} conjugate(g_{bd}^{(j)})
- delta_{ab} delta_{cd} ) .
For composite Gaussian indices alpha, beta, gamma, delta, the complex
Gaussian pairing formula (Isserlis) gives the fourth-moment identity
E[ ( g_alpha conjugate(g_beta) - delta_{alpha beta} )
conjugate( g_gamma conjugate(g_delta)
- delta_{gamma delta} ) ]
= delta_{alpha gamma} delta_{beta delta} . (4.10)
Indeed, independence, circular symmetry, and E|g_alpha|^4 = 2 give
the two Gaussian pairings
delta_{alpha beta} delta_{gamma delta}
+ delta_{alpha gamma} delta_{beta delta},
and centering removes the first.
Therefore the coefficient covariance is diagonal, and its diagonal
entry is
(1/k) sqrt(lambda_a lambda_b mu_c mu_d) . (4.11)
Take fresh independent samples for each slot location and each ordered
pair of monomial labels at that gate. Nothing below depends on any
joint law across different slots or different monomial pairs.
Step 6: expansion by corrected positions. Let
E = { (g, e) : e in E_g }
be the set of slot locations of the whole construction, and N = |E|.
The set E is uniformly polynomial in L.
In the density calculation for each gate, substitute X + Delta for each
source operator, inside its sum over ket and bra labels. Expanding
these products throughout the circuit gives
rho^ - rho' = sum_{ nonempty S subset of E } F_S . (4.12)
A set S specifies which positions use centered corrections; it does
not specify their monomial labels. At a gate with no selected
position, summing its labels gives exactly G_g (.) G_g^dagger.
Fix S, write s = |S|, and let A be the set of parties that are
endpoints of the slots in S. Then |A| <= 2 s. Expand the ket and bra
labels at every nonprivate gate touching A, whether or not that gate
has a selected slot. There are at most 2 b s such gates (by the
lifetime participation bound). All other gates lie entirely in the
exterior and remain their exact aggregate contractions. Also fix ket
and bra basis entries x, y of the physical outputs at parties in A.
The total weighted cost of these choices is at most
B(L)^{4 b s} d(L)^{4 s} = Q(L)^s ,
Q(L) := B(L)^{4 b} d(L)^4 . (4.13)
Here each expanded gate contributes at most
( sum_{xi in Xi_g} |c_{g,xi}| )^2; the number of physical matrix
entries is at most d(L)^{2 |A|}. Scalar coefficients are removed from
the maps and charged in this bound.
From now on fix one such deterministic choice of labels and physical
entries. The samples used at its different corrected positions are
independent. There is no sample-dependent selection of a branch.
The triangle inequality over these choices means no cross-branch
covariance assumption is needed.
Step 7: the two separated contractions. Both ends of every corrected
source lie in A. All sources crossing from A to its exterior are
therefore exact: their tensor product is a normalized pure vector on
the ket side and a possibly different normalized pure vector on the
bra side. In their Schmidt bases let the tau and tau~ be the
respective probability matrices. Their diagonal entries sum to one.
Empty lists are represented by a one-dimensional space and the scalar
probability one.
For every corrected slot retain both ket endpoint indices as free
indices; collect them in i. Similarly collect the bra endpoint
indices in l. Define normalized product probability lists p_i and
p~_l by giving a corrected slot the respective factors
lambda_a lambda_b and mu_c mu_d. In particular the two endpoint
indices are independent summation indices, even though an exact pure
source would identify them.
If z_{il} denotes the product of the centered coefficients at these
slots (with the (1/k)-fold averaging absorbed into z_{il}), then
independence and (4.11) give
E[ z_{il} conjugate(z_{i'l'}) ]
= k^{-s} sqrt( p_i p~_l ) delta_{ii'} delta_{ll'} . (4.14)
Let I be the ket space with basis i, T the affected-side ket
Schmidt-support space with basis t for tau; use tildes for their bra
analogues. Including the final physical basis projection, the affected
calculations give contractions
A_x : I tensor T --> F ,
A~_y : I~ tensor T~ --> F .
The codomain F contains all affected discard registers. It is the
same on ket and bra because the external memory spaces are fixed; the
inventory construction ensured this also for the added garbage.
These are contractions on all free inputs: each operation in their
construction is a contraction, an isometric preparation, an identity
on an idle register, or a physical basis projection. No normalization
of any output vector has occurred. Therefore
O := A~_y^dagger A_x :
I tensor T --> I~ tensor T~ ,
|| O || <= 1 . (4.15)
Write its blocks as O_{li} : T --> T~.
The exterior calculations similarly give contractions from their
crossing-source half-spaces to the exterior physical output and
garbage. In the matching Schmidt coordinate spaces denote them by K
and K~. They can differ on ket and bra but do not depend on i, l.
For any rectangular operator Z between the two exterior input spaces,
|| Tr_garbage( K Z K~^dagger ) ||_1 <= || Z ||_1 . (4.16)
To see this, test the output against an arbitrary matrix M of operator
norm at most one. The pulled-back test K~^dagger (M tensor id) K has
norm at most one. Trace-norm duality proves the inequality even when
Z is neither Hermitian nor positive.
Step 8: the second-moment bound. Density-weighted comparisons between
trace and Hilbert-Schmidt norms also occur in privacy amplification and
decoupling; here we use a two-weight rectangular form of Schatten
Hoelder, proved in the display below. Tracing the affected garbage
gives the following exterior input operator for the fixed labels and
x, y:
Z = sum_{i,l} z_{il}
tau^{1/2} O_{li}^T tau~^{1/2} . (4.17)
Indeed its (t,t') coefficient is
sum_{i,l} z_{il} sqrt(tau_t tau~_{t'})
< A~_y(l,t') , A_x(i,t) > .
The transpose in (4.17) is the ordinary full matrix transpose in these
bases, including when the matrix is rectangular; it preserves all
Schatten norms.
For an operator W between these coordinate spaces, Schatten Hoelder
with exponents 4, 2, 4 gives
|| tau^{1/2} W tau~^{1/2} ||_1
<= || tau^{1/4} ||_4
|| tau^{1/4} W tau~^{1/4} ||_2
|| tau~^{1/4} ||_4
= || tau^{1/4} W tau~^{1/4} ||_2 . (4.18)
The subscript 2 denotes the Hilbert-Schmidt norm, and the
quarter-power Schatten-4 norms equal one because the probability
matrices have trace one. Applying this and transposing the middle
matrix in (4.17) yields
|| Z ||_1 <=
|| sum_{i,l} z_{il}
tau~^{1/4} O_{li} tau^{1/4} ||_2 .
By (4.14), the expected square of the right side is
k^{-s} sum_{i,l} sqrt( p_i p~_l )
|| tau~^{1/4} O_{li} tau^{1/4} ||_2^2 . (4.19)
Define trace-one positive diagonal matrices on the full free input
spaces by
R = diag( p_i ) tensor tau ,
R~ = diag( p~_l ) tensor tau~ .
The sum in (4.19) is exactly || R~^{1/4} O R^{1/4} ||_2^2: its (l,i)
block is p~_l^{1/4} p_i^{1/4} tau~^{1/4} O_{li} tau^{1/4}, and the
Hilbert-Schmidt squares of disjoint blocks add. Another application
of Schatten Hoelder and (4.15) gives
|| R~^{1/4} O R^{1/4} ||_2
<= || R~^{1/4} ||_4 || O || || R^{1/4} ||_4
<= 1 . (4.20)
This bound contains no rank or dimension of a source, an input, or a
discard space. Cauchy-Schwarz for the expectation now proves
E || Z ||_1 <= k^{-s/2} . (4.21)
Applying the exterior map preserves this bound by (4.16). Reinserting
the affected physical matrix unit |x><y| preserves the trace norm,
since that matrix unit has trace norm one.
Step 9: summation and realization as a network. Summing over the
fixed choices with (4.13) gives
E || F_S ||_1 <= Q(L)^{|S|} k^{-|S|/2} .
Consequently
E || rho^ - rho' ||_1
<= ( 1 + Q(L) / sqrt(k) )^N - 1 . (4.22)
If N = 0, there is no sampling error. Otherwise choose an integer k
with
Q(L) / sqrt(k) <= epsilon / (8 N) .
It is uniformly polynomial. The right side of (4.22) is at most
e^{epsilon/8} - 1 <= epsilon/4. Hence there is a realization with
|| rho^ - rho' ||_1 <= epsilon/2, for example by Markov's inequality.
Fix one such realization and set sigma = rho^. Together with (4.4)
this proves the asserted error.
Step 10: the network realization. Each sampled corrected source
X^ = (1/k) sum_j U_j tensor V_j is a sum of k product monomials,
so the total product structure of the sampled density calculation is
a polynomial sum of product circuits. Each such circuit is an
operator network on the party graph: one node per party, ket and bra
legs for its physical output, and virtual links crossing the slots.
Because every link corresponds to one slot, which corresponds to one
pair of parties in a common nonprivate gate, the link placement is as
asserted. Its dimension is at most k times the ambient slot
dimension, which is uniformly polynomial.
The remaining question is a constraint on the number of sampled
positions. At each source X^ there are k factors, so the total number
of monomials grows as k^N, which is uniformly polynomial. This is
absorbed by choosing the network at the level of the whole sum,
without ever writing out its k^N branches individually.
Approximate expansions. If the gate expansions of assumption (3) are
available to every fixed inverse-polynomial operator-norm accuracy,
apply the same argument to expansions at accuracy delta' chosen
so that N delta' is at most epsilon/4. All constants and incidence
bounds remain as stated. END PROOF.
================================================================
PART 5. ENCODED FRAMES AND THE THREE LOCAL OPERATIONS
================================================================
A frame records which party owns which physical site, plus a finite
collection of encoded "holes" that hide complicated structures inside
small squares at true vertices. The three local operations below --
change of frame on a small patch, birth/death of a homogeneous owner,
and exchange of two sheets along a lens -- are the only moves used by
the planar protocol of Part 6. The information estimates of Part 2
are exactly what makes each move cost nothing in vector norm.
5.1 Physical sites, ownership, and encodings
---------------------------------------------
Let Lambda be the L x L grid with coordinates translated so that the
physical sites are at cell centres (i + 1/2, j + 1/2), 0 <= i, j < L.
For an ambient subset A of the plane, write
A ^ r = { x : dist_inf( x, A ) <= r } ,
A ^ <r = { x : dist_inf( x, A ) < r } .
Physical samples are A intersect Lambda.
A one-sheet frame is a map from Lambda to a finite set of parties. The
raw owner of a site is its image under this map. Registers are
canonical: for each site v there is a formal register H_v of dimension
q, and the memory of a party is the tensor product of the registers it
owns, over all sites it owns.
A hole is a pair (c, h) with a centre c in the plane and a radius
h > 0. Its inner square is D(c,h) = c + [-h,h]^2, and its outer
square is X(c,h) = D(c, 2h). A hole is owned only if its tag register
belongs to a specific party.
DEFINITION 5.0 (hole encoder; companion to its simple explicit form).
Let h > 0, let c be a centre, and let the inner square D = D(c,h) and
outer square X = D(c,2h) be given. Suppose there is a decomposition
H_X = direct sum_{j=1}^J S_j tensor H_{ D }
( as tensor factors ), (5.0)
in which S_j is a subspace of H_{X \ D} of dimension d_j. Choose an
orthonormal basis { v_{j ell} } of S_j, one for each j, 1 <= ell <= d_j.
The hole encoder at (c, h) is the linear map
K_{c,h} = sum_{j, ell}
| j, ell >_tag tensor | v_{j ell} >_X . (5.1)
The tag register has orthonormal basis {| j, ell >}. It records the
branch j and the vector ell.
Two properties of (5.1) are used exactly once each.
(a) K_{c,h}^dagger K_{c,h} = P_{c,h} is the orthogonal projection
onto the branch decomposition (5.0), hence || K_{c,h} || <= 1.
Raw registers are kept at every site; only the outside factor
is re-encoded.
(b) When the outer square is empty (that is, X intersect Lambda is
empty), we use the identity encoding with a one-dimensional
tag. When D is empty the encoding is trivial and its tag is
one-dimensional.
An encoded frame consists of:
(i) a one-sheet frame f : Lambda --> Parties,
(ii) a finite list of holes H = { (c_i, h_i) }, with pairwise
disjoint outer squares, each of which is assigned to the same
party as its tag,
(iii) for each hole, a hole encoder (5.1) acting on its outer square.
The raw owner of the frame is the underlying map f. The set
H^-(F) and H^+(F) are the unions of inner and outer hole squares
over all holes of F. The reference vector of the frame is
Omega_F = ( tensor over holes i
K_{c_i,h_i} acting on X(c_i,h_i) ) Omega . (5.2)
Every branch (tag) has been kept; the reference is the encoded pure
state with tags attached.
DEFINITION 5.1 (bounded change). A change of frame is bounded by a
fixed list P of parties when: it is realized by a fixed number of
contraction gates involving at most that list of parties; each gate
belongs to the class admitted by Theorem 4.2 (a polynomial sum of
allowed monomials in a fair coefficient sum); and the number of
normalized pair resources per monomial is fixed. Its accuracy may be
any fixed inverse power of L; scaling by 1 + O(L^{-a}) restores
contractivity.
5.2 A group-tensor decomposition bound
---------------------------------------
The following elementary bound replaces a complicated patch network by
pair resources without depending on the dimensions of its open wires.
It is used exactly once, in the proof of the small-patch rewrite below.
The subtlety it addresses: a normalized vector shared by three or more
parties is not itself a permitted pair resource, so we must pass to a
sum of products whose factors are each supported on at most two
parties. The proof only truncates whole open-leg groups, keeping
internal contractions exact.
For a matrix M write ||M||_1 for its sum of singular values and ||M||_2
for its Hilbert-Schmidt norm.
LEMMA 5.2 (whole-group tensor bound).
Let a finite graph carry at each vertex a Hilbert-space tensor of norm
at most one. Contract internal edges by coordinate pairing, with no
self-loops. Group open legs according to their original vertices.
The resulting tensor Z has norm at most one, and has matrix nuclear
norm at most one across every bipartition into whole open-leg groups.
If there are g nonempty open-leg groups, then for every integer k >= 1
there are subspaces of dimension at most k in the respective group
spaces whose tensor-product projection sends Z to Z_k with
|| Z - Z_k || <= g / sqrt(k) . (5.3)
In orthonormal bases of those subspaces, Z_k is a sum of at most k^g
product terms with coefficients of absolute value at most one.
PROOF.
Flatten Z across one open-leg group and its complement. Let
s_1 >= s_2 >= ... be the singular values. By the whole-group nuclear
bound, sum_j s_j <= 1, and
sum_{j>k} s_j^2 <= s_{k+1} sum_{j>k} s_j
<= 1 / (k+1) .
Projection onto the first k left singular directions has error at most
k^{-1/2}. Do this for every original open-leg group. The projections
act on disjoint tensor factors, so telescoping their product gives
(5.3). The result has norm at most one; every coefficient in any
product orthonormal basis of the truncated subspaces therefore has
absolute value at most one. Empty or one-group cases reduce to the
trivial interpretation. END PROOF.
5.3 The small-patch rewrite
---------------------------
The small-patch rewrite is the leitmotif of the frame operations. Two
encoded frames may differ by an operation localized on a small bounded
patch -- a hole resizing, a true-vertex rearrangement, a change of
which party holds a small tag. The rewrite turns that difference into
a contraction gate, with error controlled by the size of the patch and
not by the dimensions of any hole. Two technical requirements make it
work. The patch has at most two raw owners on each side outside the
inner holes; and all involved parties are up to a fixed B_0 log L scale.
LEMMA 5.3 (small-patch rewrite).
Let F_old and F_new be one-sheet encoded frames. Suppose that only a
bounded number of their holes are affected; all untouched holes agree,
including their encodings and tag owners. Suppose that the following
hold for m = O(1) additional square patches (c_i, u_i) with
0 < u_i <= B_0 log L.
(1) Every patch's outer square avoids the physical outer footprints
of the untouched holes. Affected old and new holes also avoid
those untouched footprints.
(2) The union of the patch inner squares contains every site whose
raw owner changes, and the entire physical outer footprints of
every affected old or new hole.
(3) In each patch's outer square, sites outside H^-(F_old) have at
most two old owners, and separately, sites outside H^-(F_new)
have at most two new owners.
(4) All raw owners on the involved patch and affected-hole
footprints, and all affected tag owners, are drawn from a
specified bounded list of parties.
Then there is a canonical contraction M between the two layouts, with
|| M Omega_{F_old} - Omega_{F_new} ||
<= (m + r_old) epsilon , (5.4)
where r_old is the number of affected old holes, and epsilon is the
base-patch accuracy of Proposition 3.1. For every fixed a > 0 there
is a contractive approximation M_a with ||M_a - M|| <= L^{-a} and a
polynomial sum expansion of the kind required by Theorem 4.2, using
only the specified parties. In particular the rewrite has
reference-vector error at most L^{-20} against the specified target.
PROOF.
Write K_old, K_new for the products of just the affected hole
encoders, and K_0 for the common untouched encodings. Let
P_1, ..., P_m be the projectors of Proposition 3.1, one for each
additional patch, again at base-patch accuracy epsilon. Fix any order
of the patches and set
M = K_new P_m ... P_1 K_old^dagger . (5.5)
This formula uses canonical raw indices between its factors, and
interprets the final raw and tag indices with their new owners. It is
the identity on all other registers. Every factor is contractive.
The error is easy to bound. Insert P_j as identity plus its error:
|| P_j Omega - Omega || <= epsilon .
Similarly K_old and K_new differ from the identity on their outside
tensor factors by epsilon. Summation of the errors over the m patches
and r_old holes gives
|| M Omega_{F_old} - Omega_{F_new} ||
<= ( m + r_old ) epsilon . (5.6)
Sum expansion. We now build the polynomial monomial expansion of M.
Expand each tag and each patch projector using (5.1). There are
polynomially many complete branch choices, because the number of
factors is bounded. Fix one such branch.
On each selected old-hole square, the branch of K_old^dagger consumes
the input tag by its basis bra, consumes the raw inputs by product
zero-state bras, and supplies a decoded normalized ket v_{j ell}. On
a new-hole square, the branch of K_new contracts against a normalized
bra < v_{j ell}| and supplies product zeros and a fixed tag. A
selected patch term has a normalized bra and a normalized ket on its
selected square; keep these as two distinct tensor vertices.
Factor out the fixed tag bras and kets, the one-site zero bras and
kets, and every raw wire that continues directly from an input to an
output without encountering any selected action. The first two are
private norm-one maps. Every direct wire is private as well: a
changed site belongs to some patch inner square, so it belongs in
every radius branch of that patch, and cannot be such a wire. The old
and new owners of a remaining direct wire are therefore equal. In
particular, no factor of the form id_{H_A} with a large
Hilbert-Schmidt norm needs to enter a tensor norm estimate.
Apply Lemma 5.2. The only remaining vertices with open legs are
patch bras and patch kets, and possibly hole-encoded bras and kets.
A patch bra can have only raw input legs, and a patch ket can have
only raw output legs. An input site inside an old inner hole is
consumed by the old decoder's zero-state bra in every branch, since
every selected hole square contains its inner square, so it is not an
open input of a patch bra. Consequently all open inputs of a patch
bra lie in that patch's outer square outside the old inner holes. By
treatment condition (3), the raw owners of these inputs are at most
two. Similarly, at most two new owners contribute to the open legs
of a patch ket. Intersections of selected patches only add internal
ket-to-later-bra wires; they do not change these statements about
open legs.
Let Z be the remaining open tensor, with groups given by these
original vertices. Lemma 5.2 supplies an approximation Z_k with error
g/sqrt(k), where g = O(1), and a monomial expansion of at most k^g
product terms. An output group vector in such a term is a normalized
state on one party, or a normalized bipartite state on its two owners.
An input group vector is a normalized private covector, or a normalized
bipartite covector on two owners. Their order may be chosen as
follows: first contract all input effects, then append all output
states, since the groups have disjoint open legs. After restoring the
factored private maps and direct identities, each product term is
precisely an allowed monomial of Theorem 4.2. It uses only boundedly
many pair states and effects; its scalar coefficient has absolute
value at most one. A scalar residual tensor is already a coefficient
of absolute value at most one.
Hilbert-space error versus operator-norm error. For any branch, its
Hilbert-space error on Z bounds its operator-norm error on the whole
contraction. Consume the factored input bras, apply the residual
tensor reshaped as a map, tensor with the direct identities, and
append the factored output kets. All the outer maps are contractions,
and the operator norm of a matrix is at most its Hilbert-Schmidt norm.
Tensoring with a direct identity preserves its operator norm. Hence
the branch error is at most g/sqrt(k), with no factor involving the
dims of the bypassing wires.
Therefore summing.
Let N_br <= L^{C_1} bound the number of branches, absorbing fixed
prefactors by enlarging C_1 for L >= 2, and let g <= g_0. Summing
their errors gives operator-norm error at most N_br g_0 / sqrt(k).
Choose the polynomial k so that this is at most (1/2) L^{-a}.
Since M is contractive,
Let M~ be the truncated expansion, satisfying || M~ || <= 1 + (1/2)L^{-a}.
Then M_a := M~ / (1 + (1/2)L^{-a}) satisfies || M_a || <= 1 and
|| M_a - M || <= L^{-a} .
The total number of monomials is at most N_br k^{g_0}, their
coefficients are bounded, and their participating parties are those in
the specified list. Taking a = 20 proves the last assertion.
END PROOF.
5.4 Splitting a buffer, restated
---------------------------------
The birth and exchange operations below both reduce to the splitting
consequence stated as Corollary 1.3 in Part 1. We restate it here in
the language of frames.
LEMMA 5.4 (splitting, restated).
Let T, U, E partition Lambda. Let b = I_Omega(T:E). Then there are
finite-dimensional spaces B_T, B_E, an isometry W : H_U --> B_T tensor
B_E, and normalized vectors s in H_T tensor B_T, s' in H_E tensor B_E,
with
|| (id_{TE} tensor W) Omega - s tensor s' || <= sqrt(b) . (5.7)
No bound is placed on the dimensions of B_T or B_E.
PROOF. This is Corollary 1.3 verbatim. END PROOF.
The use in what follows. In every frame operation, the buffer U is
private to a single party P_circ. All of B_T and B_E are therefore
held by P_circ, and the isometry W is a private action at P_circ. The
two factors s and s' become normalized resources that P_circ and one
other party share across the new cut. The error sqrt(b) may be any
fixed polynomial; with b = L^{-60}, it is L^{-30}.
5.5 Birth and death of a homogeneous owner
-------------------------------------------
The simplest change of the planar protocol is a transfer of ownership
on a region that currently has a single owner, in surroundings that
already know about that single owner and no other. Birth and death
are inverse operations; we state them together.
LEMMA 5.5 (homogeneous birth and death).
In an encoded frame, let T be a set of raw sites owned by P_circ and
disjoint from every outer hole footprint. The proposed birth changes
only the ownership of T, from P_circ to Q_circ. Every hole, its
encoding, and its tag owner are kept fixed. Define
E = { x : the old raw owner of x is not P_circ }
union H^+(F) ,
U = Lambda \ ( T union E ) . (5.8)
If
I_Omega( T : E ) <= L^{-60} , (5.9)
then the birth is a bounded change involving only the two parties
P_circ and Q_circ, with reference-vector error at most L^{-30}. The
reversed death obeys the same bound whenever these ownership and
information conditions hold in its surrounding frame, namely the
frame after the death.
PROOF.
Put V = id_{TE} tensor W, with W from Lemma 5.4, and use its vectors
s, s'. All of T, U initially belong to P_circ. At P_circ, perform
the following sequence of private contractions:
(1) apply V on U,
(2) contract T tensor B_T against < s |,
(3) supply the normalized pair state s on T tensor B_T, with T now
held by Q_circ and B_T still held by P_circ,
(4) apply V^dagger on B_T tensor B_E at P_circ.
Step (3) is a pair source between the two specified parties. Steps
(1) and (4) involve only P_circ. Step (2) is a private contraction
at P_circ.
The associated canonical map
B = V^dagger ( |s><s|_{T B_T} tensor id_{E B_E} ) V (5.10)
is a Hermitian contraction. Writing Pi for the middle projector
(the rank-one projection onto |s><s| on T B_T, extended by identity),
|| (B - id) Omega ||
<= || (Pi - id) V Omega ||
= || (Pi - id)( V Omega - s tensor s' ) ||
<= || V Omega - s tensor s' ||
<= L^{-30} ,
using the fact that Pi fixes s tensor s' and is a contraction. This
bound holds for the unencoded reference vector Omega. Every hole
encoder is supported in E, on whose raw registers this map
acts as the identity. It also acts as the identity on tags. Commuting
the encoders through the map therefore gives the same error bound on
the encoded reference vectors, by their contractivity. END PROOF.
Two observations about the lemma.
(1) The operation involves only two parties. Every other party is
a spectator. This is what "bounded" means in the sense of
Definition 5.1.
(2) The error of L^{-30} comes solely from the quality of the
splitting, i.e. from the information hypothesis (5.9), whose
right side was chosen as L^{-60} and whose square root is
L^{-30}. No dimension of any hole or source enters the
constant.
5.6 Exchange of two sheets along a lens
----------------------------------------
The last operation is the one that lifts information from one sheet to
another when the two sides of a region want to change owners. It is
needed for the repainting in Part 6 because some ownership changes
cannot be done with a single birth, only with an auxiliary sheet whose
sectors can be arranged to match.
LEMMA 5.6 (two-sheet exchange).
Consider two encoded frames F_1, F_2, and a plane region Y. Suppose
every hole's entire outer square lies on one side of the boundary
partial Y. Inside Y, exchange the two raw ownership assignments and
the two lists of encoded holes, including their tag owners; outside Y,
keep both frames unchanged.
Let P_circ be a party. On the physical square put
Z = { x : the two old raw owners of x are not both P_circ }
union H^+(F_1) union H^+(F_2) ,
T = Z intersect Y ,
E = Z setminus Y ,
U = Lambda setminus Z . (5.11)
If
I_Omega( T : E ) <= L^{-60} , (5.12)
then the exchange can be implemented by private contractions and
register renaming, with reference-vector error at most 4 L^{-30}. It
uses P_circ and the owners of the registers and tags being renamed.
When these parties form a bounded list, it is a bounded change in the
sense of Definition 5.1.
PROOF.
Let K_in and K_out denote the products of the two frames' encoders
before and after the exchange. For A subset of Lambda, write F_A for
the unitary that swaps the two raw sheets at the positions in A.
Sheet renaming. First rename the two sheets inside Y, together with
each tag of a hole there, leaving every physical register at its
present party. Call this map R. This is a private identification of
tensor factors: the output owner of sheet 1 at x in Y is precisely the
old owner of sheet 2 there, and conversely. The same assertion holds
for a tag moved with its whole hole. In canonical raw coordinates the
exact intertwining identity is
R K_in = K_out F_{Y intersect Lambda} . (5.13)
It follows by checking each site outside holes and each whole hole
encoding separately. For a hole within Y, all selected raw squares
and its tag change sheet together; for a hole outside Y, nothing
changes. The assumption on the outer square ensures this for every
selected radius.
Replacing the raw swap by a private correction. Apply Lemma 5.4 with
the partition T, U, E of (5.11). Let
V = id_{TE} tensor W : H_{Lambda} --> H_{T E} tensor B_T tensor B_E
be the corresponding embedding, and s, s' its vectors. All of U is
held by P_circ, so V is a private contraction at P_circ. The exchange
is:
(1) apply V,
(2) apply the two-copy unitary on T tensor B_T that swaps the ket
and bra positions within the reduced inner product,
(3) apply V^dagger.
We are using the two-copy representation of a swap, and we now state
the bound it gives.
Put zeta = s tensor s' and delta = || V Omega - zeta || <= L^{-30}.
Both vectors are normalized, so
|| (V Omega)^{tensor 2} - zeta^{tensor 2} || <= 2 delta .
The vector zeta^{tensor 2} is fixed by F_{T B_T}, which swaps the two
identical s factors. Since (V^{tensor 2})^dagger V^{tensor 2} = id,
|| (V^{tensor 2})^dagger F_{T B_T} V^{tensor 2} Omega^{tensor 2}
- Omega^{tensor 2} ||
<= || ( F_{T B_T} - id )(
( V Omega )^{tensor 2} - zeta^{tensor 2} ) ||
<= 4 delta . (5.14)
Multiplication by the contraction K_out and identity (5.13) give the
claimed error between the product of the old encoded reference vectors
and the product of new ones. END PROOF.
A note on the party discipline. All actual operations are private: preparation
of V, its adjoint, and the pair source s, all at P_circ; renaming of
sheets and tags, at the owners of the affected registers. No raw
register is transferred by the renaming. The apparent partial raw
swap was induced by the change of sheet names and corrected using the
common owner's buffer. This is what makes it a bounded change.
5.7 Lifetime bounds for frame operations
-----------------------------------------
The three lemmas above are used in Part 6 as atomic steps. Each has a
fixed number of marked corners, its own small-patch treatment of every
mark, and (in the case of the exchange) an auxiliary sheet. Two facts
hold uniformly, and they are what the compression theorem of Part 4
requires.
LEMMA 5.7 (frame operation lifetimes).
Each elementary frame operation -- birth, death, exchange -- involves a
fixed number of linked gates. The set of participating parties is a
fixed list determined by the local diagram of the operation, and each
listed party participates in at most a fixed number of linked gates
per operation. The small-patch rewrites replace each mark's dense
description by arbitarily accurate polynomial expansions in bounded
patch families. The auxiliary sheet used at an exchange is
initialized, used in its one edge construction, returned to its final
frame, and permanently retired; it participates in no further linked
gate.
PROOF.
The claim is a bookkeeping consequence of Lemma 5.3, 5.5, 5.6, and
Proposition 3.1. Count: birth and death use one party each of
P_circ, Q_circ plus the affected tag holders, at most a fixed bounded
number by hypothesis (4) of Lemma 5.3. Exchange uses P_circ, the two
sheet owners, and the affected tag holders, again a bounded list. Each
of those operations is a bounded list of monomials by Lemma 5.3,
applied at the fixed patches of Proposition 3.1. END PROOF.
================================================================
PART 6. A FINITE PLANAR DISTRIBUTION PROTOCOL
================================================================
The compression theorem of Part 4 works for any distributed
construction whose parties participate in only boundedly many gates
over the whole lifetime. The purpose of this Part is to construct such
a construction, whose reference vector matches Omega to within a fixed
inverse power of L.
The construction is an ownership distribution on Lambda. At the start,
one party holds the whole vector. At the end, every physical site has
its own party. Along the way, each party acts privately, and pairs of
parties exchange resources through the frame operations of Part 5.
The discipline is that each pair participates in only boundedly many
such exchanges, and their physical positions are close in a dyadic
sense. Both conditions are achieved by arranging the schedule to move
along a fixed dyadic hierarchy.
6.1 The padded dyadic hierarchy
--------------------------------
Translate the lattice so that its sites are the cell centres
(i + 1/2, j + 1/2), 0 <= i, j < L. Let N be a power of two with
L <= N < 2L. Consider the aligned squares in [0, N]^2 whose sides are
dyadic powers 2^j, j = 0, 1, ..., log_2 N, and whose corners lie on
the lattice points { (2^j r, 2^j s) : 0 <= r, s < N / 2^j }.
Unoccupied cells of the padded square (those outside [0, L]^2) carry
no registers.
Each dyadic square is assigned a party; the assignment is one-to-one.
The order of the dyadic squares is the order of increasing scale, and
within each scale any fixed order.
The address of a dyadic square S of side n = 2^j and cell indices
(r, s) is
a(S) = ( n r + n/2 , n s + n/2 ) if j >= 1,
a(S) = ( r, s ) if j = 0. (6.1)
The same address is used for the additional parties attached to S.
A guide on a sheet is a function from the padded square [0, N]^2 to a
finite set of parties. It is constant on chambers of a finite list of
ambient interface lines. It is uniform on n-blocks at every level
n that has been processed so far. "Uniform on n-blocks" means: each
open n x n dyadic block has a single label, except that the boundary
column/row may be trimmed to fit its neighbours.
A true vertex of a guide is a point in the closure of the augmented
set of at least three distinct labels. Guides with only finitely many
true vertices are what we construct. Holes are encoded at true
vertices, and their outer squares are separated on the current scale.
Sizes. Fix once and for all constants D > 0 and epsilon_0 > 0, with
D chosen in Part 6.7. Put
t = D log L ,
h_n = epsilon_0 min( n, t ) . (6.2)
A hole at an original true vertex has inner radius h_n and outer
radius 2 h_n. We require epsilon_0 small enough that the outer squares
are disjoint within each guide.
6.2 The protocol
-----------------
This subsection states the target. Its proof is divided into
subsections 6.3-6.7.
PROPOSITION 6.1 (distribution through a dyadic hierarchy).
For all sufficiently large L, there is a protocol with the following
properties. All constants in this statement are uniform in the
Hamiltonian and in L.
(1) There are O(L^2) parties, one for each dyadic square in the
padded hierarchy and at most a fixed number of additional
parties for each repainting of a square. Initialization is a
pure product across parties. One party initially holds the main
copy of Omega; all auxiliary copies are initialized privately at
their designated parties.
(2) The schedule has at most C L^3 changes. Each change is a
bounded change in the sense of Definition 5.1: a fixed number of
contraction gates involving at most a fixed number of parties,
with polynomial expansion of the kind admitted by Theorem 4.2.
Each party participates in at most a fixed number of gates
involving other parties over its whole lifetime.
(3) Every linked gate involves parties at the same or adjacent
dyadic scales. Parties at a gate have addresses at distance
O(n), where n is either endpoint's scale. Additional parties
have the scale and address of the square to whose repainting
they belong.
(4) There is a designated reference vector at every stage, formed
from the main encoded frame and the auxiliary encoded frames.
All its factors have norm at most one. Each change takes its
# ^C interrupted by user!