$1-\delta$, we can learn all operators $\hat{W}_{A_{i}}$ within sufficient
precision, using a dataset size of

$N=\frac{2^{\mathcal{O}((8kd)^{k})}n^{2}\log(n/\delta)}{\varepsilon^{2}}.$
(226)

Next, each $\hat{W}_{A_{i}}$ is classically compiled into a circuit, and they
are combined together according to the order in Lemma 18, such that the
learned circuit has total depth $(k+1)(2d+1)+1$. This classical postprocessing
procedure takes a total time of

$\mathcal{O}(nN)+\left(n/\varepsilon\right)^{\mathcal{O}(8kd)^{k+1})},$ (227)

which is polynomial in $n$ and $1/\varepsilon$. If we do not compile
$\hat{W}_{A_{i}}$ to the shorter-depth circuit $\hat{W}_{A_{i}}^{\prime}$ and
use $\hat{W}_{A_{i}}$ directly, then the classical postprocessing procedure
only requires a computational time of

$\mathcal{O}(nN),$ (228)

but the learned circuit will have a total depth of $(k+1)4^{4(8kd)^{k}}+1$.
This concludes the proof of the first part of Theorem 7.

####  5.5.2 Finite gate sets

The algorithm and the proof closely follow that of arbitrary $\mathrm{SU}(4)$
gates. When one considers a finite gate set with a constant size, a key
simplification is the following: for any given $i\in\\{1,\ldots,L\\}$ and
$P_{A_{i}}\in\\{I,X,Y,Z\\}^{|A_{i}|}$, $U^{\dagger}P_{A_{i}}U$ only takes on a
constant number of options. Let $\varepsilon_{i,P_{A_{i}}}=\Omega(1)$ be the
minimum distance in spectral norm between any pair of distinct
$U^{\dagger}P_{A_{i}}U$.

From the same algorithm and proof in Step 1: Learning, we can ensure that

$\left\|\hat{O}_{i,P_{A_{i}}}-U^{\dagger}P_{A_{i}}U\right\|_{\infty}\leq\frac{\varepsilon_{i,P_{A_{i}}}}{3},\quad\forall
i\in\\{1,2,\dots,L\\},\quad P_{A_{i}}\in\\{I,X,Y,Z\\}^{|A_{i}|},$ (229)

holds with probability at least $1-\delta$ using a sample complexity of

$N=\mathcal{O}\left(\frac{\log(n/\delta)}{\varepsilon_{i,P_{A_{i}}}^{2}}\right)=\mathcal{O}\left(\log(n/\delta)\right).$
(230)

From the definition of $\varepsilon_{i,P_{A_{i}}}$, we can identify
$U^{\dagger}P_{A_{i}}U$ exactly from $\hat{O}_{i,P_{A_{i}}}$. This enables us
to exactly reconstruct

$W_{A_{i}}=\frac{1}{2^{|A_{i}|}}\sum_{P\in\\{I,X,Y,Z\\}^{|A_{i}|}}U^{\dagger}PU\otimes
P=U^{\dagger}S_{A_{i}}U.$ (231)

Because $U$ is a quantum circuit of depth $d=\mathcal{O}(1)$ on a constant-
dimensional lattice over a finite gate set of a constant size, we can perform
a constant-time brute-force search to find a $(2d+1)$-depth circuit
implementation for $W_{A_{i}}$ instead of searching through the
$\varepsilon$-net as in Step 2: Compiling. The computational time of the
compiling step is improved from
$\left(n/\varepsilon\right)^{\mathcal{O}(8kd)^{k+1})}$ to $\mathcal{O}(n)$.
Following the rest of the proof for the case of $\mathrm{SU}(4)$ gates, we can
learn $U$ exactly with a learned circuit of depth $(k+1)(2d+1)+1$. The sample
complexity is given in Eq. (230), and the computational time is dominated by
reading the classical dataset, which is of
$\mathcal{O}(nN)=\mathcal{O}(n\log(n/\delta))$. This concludes the proof of
Theorem 7.

##  6 Learning shallow quantum circuits from quantum queries

We consider quantum learning algorithms that can access an unknown $n$-qubit
unitary $U$ through coherent quantum queries, which interleave the unitary $U$
with quantum computation.

######  Definition 19 (Coherent quantum queries).

The learning algorithm is a quantum algorithm with general coherent query
access to the unknown unitary $U$. The quantum learning algorithm can
interleave multiple accesses to the unknown unitary $U$ with polynomial-size
quantum circuits.

We show the following result for learning geometrically-local shallow quantum
circuits over finite gate sets with asymptotically optimal query complexity
and time complexity. We only need to consider proving the matching upper
bounds. The matching lower bounds to the query and time complexity are
trivial: learning anything about $U$ requires $\Omega(1)$ queries to $U$;
writing down $U$ requires $\Omega(n)$ time.

######  Theorem 8 (Learning geometrically-local shallow quantum circuits over
a finite gate set).

Given an unknown geometrically-local constant-depth $n$-qubit circuit $U$ over
a finite gate set. From

$N=\Theta(1)$ (232)

queries to $U$, we can learn an $n$-qubit quantum channel $\hat{\mathcal{E}}$
that can be implemented by a geometrically-local constant-depth $2n$-qubit
circuit, such that

$\hat{\mathcal{E}}=\mathcal{U},$ (233)

with probability $1$. The computational time to learn $\hat{\mathcal{E}}$ is
$\Theta(n)$.

###  6.1 Learning local inversion using coherent quantum queries

When there is only a finite choice of possible unitaries, we can find the
local inversion perfectly with $\mathcal{O}(1)$ queries, even if there is
incoherent noise coming from the environment. This lemma is useful for showing
the $\mathcal{O}(1)$ query complexity for learning $n$-qubit shallow quantum
circuits with a finite gate set and a fixed geometric structure. The idea is
to store multiple output quantum states in a quantum memory and utilize
entangled quantum data processing. The formal statement is given below. We use
the subscript on identity $I$ or $\mathcal{I}$ to denote the number of qubits
the identity acts on.

######  Lemma 20 (Perfect local inversion among finite choices).

Consider $k,l,m=\mathcal{O}(1)$, unitaries $U_{1},\ldots,U_{m}$ over $k$
qubits, and unitaries $W_{1},\ldots W_{m}$ over $(k-1)+l$ qubits. Let CPTP
maps $\mathcal{E}_{x}$ from $k$ to $k+l$ qubits be

$\mathcal{E}_{x}(\rho):=(\mathcal{I}_{1}\otimes\mathcal{W}_{x})(\mathcal{U}_{x}\otimes\mathcal{I}_{l})(\rho\otimes
I/2^{l}),\quad\forall x=1,\ldots,m.$ (234)

Given an unknown $\mathcal{E}_{x}$. Using $\mathcal{O}(1)$ queries to
$\mathcal{E}_{x}$, we can find a perfect local inversion $V_{x}$ of $U_{x}$ on
the first qubit. Furthermore, $V_{x}=U_{i}^{\dagger}$ for some $i$.

In order to prove the above lemma, we use a perfect local identity check for
two choices given in Lemma 21. The proof of Lemma 20 is given after the proof
of Lemma 21.

######  Lemma 21 (Perfect local identity check among two choices).

Consider $k,l\geq 1$, two unitaries $U_{1},U_{2}$ over $k$ qubits, and two
unitaries $V_{1},V_{2}$ over $k+l-1$ qubits. Given CPTP maps from $k$ qubits
to $k+l$ qubits,

$\mathcal{E}_{x}(\rho):=(\mathcal{I}_{1}\otimes\mathcal{V}_{x})(\mathcal{U}_{x}\otimes\mathcal{I}_{l})(\rho\otimes
I/2^{l}),\quad\forall x=1,2.$ (235)

Assume that $k,l$ are constants, $U_{1}$ acts as identity on the first qubit
$U_{1}=I_{1}\otimes\tilde{U}_{1}$, and $U_{2}$ is constant far from CPTP maps
that act as an identity on the first qubit,

$c:=\min_{\mathcal{E}}\norm{\mathcal{U}_{2}-\mathcal{I}_{1}\otimes\mathcal{E}}_{\diamond}=\Omega(1).$
(236)

Given an unknown $\mathcal{E}_{x}$. Using $\mathcal{O}(1)$ queries to
$\mathcal{E}_{x}$, we can perfectly distinguish between $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$.

###### Proof.

Let $\ket{\Omega_{k}}$ be the maximally entangled state over two copies of a
$k$-qubit system. We define the following density matrices over $(k+l)+k$
qubits,

$\rho_{x}:=(\mathcal{I}_{k}\otimes\mathcal{E}_{x})(\outerproduct{\Omega_{k}}{\Omega_{k}}),\quad\forall
x=1,2.$ (237)

The support of a density matrix $\rho$ is defined as

$\mathrm{supp}(\rho):=\big{\\{}\ket{\psi}\big{|}\bra{\psi}\rho\ket{\psi}>0\big{\\}}.$
(238)

From the definition of $\rho_{x}$, we have

$\mathrm{supp}(\rho_{x})=\left\\{(I_{k+1}\otimes V_{x})(I_{k}\otimes
U_{x}\otimes
I_{l})(\ket{\Omega_{k}}\otimes\ket{\psi}),\,\,\forall\ket{\psi}\right\\}.$
(239)

The maximal fidelity between two density matrices is defined as

$\tilde{F}(\rho_{1},\rho_{2}):=\max\left(|\braket{\phi_{1}}{\phi_{2}}|\,\,\big{|}\,\,\ket{\phi_{x}}\in\mathrm{supp}(\rho_{x}),\,\,x=1,2\right).$
(240)

The maximal fidelity behaves similarly to fidelity and is multiplicative under
tensor product

$\tilde{F}(\rho_{1}\otimes\sigma_{1},\rho_{2}\otimes\
\sigma_{2})=\tilde{F}(\rho_{1},\rho_{2})\tilde{F}(\sigma_{2},\sigma_{2}).$
(241)

From the above definition, we see that there exists
$\ket{\psi_{1}},\ket{\psi_{2}}$ such that

$\tilde{F}(\rho_{1},\rho_{2})^{2}=\left|(\bra{\Omega_{k}}\otimes\bra{\psi_{1}})(I_{k}\otimes
U_{2}^{\dagger}\otimes
I_{l})(I_{k+1}\otimes(V_{2}^{\dagger}V_{1}(\tilde{U}_{1}\otimes
I_{l})))(\ket{\Omega_{k}}\otimes\ket{\psi_{2}})\right|^{2}.$ (242)

We now consider two states associated with the above,

$\displaystyle\sigma_{1}$
$\displaystyle:=(I_{k+1}\otimes(V_{2}^{\dagger}V_{1}(\tilde{U}_{1}\otimes
I_{l})))(\outerproduct{\Omega_{k}}{\Omega_{k}}\otimes\outerproduct{\psi_{2}}{\psi_{2}})(I_{k+1}\otimes((\tilde{U}_{1}^{\dagger}\otimes
I_{l})V_{1}^{\dagger}V_{2}))$ (243) $\displaystyle\sigma_{2}$
$\displaystyle:=(I_{k}\otimes U_{2}\otimes
I_{l})(\outerproduct{\Omega_{k}}{\Omega_{k}}\otimes\outerproduct{\psi_{1}}{\psi_{1}})(I_{k}\otimes
U_{2}^{\dagger}\otimes I_{l})$ (244)

The Fuchs–van de Graaf inequalities show that
$\tilde{F}(\rho_{1},\rho_{2})^{2}=\Tr(\sigma_{1}\sigma_{2})\leq
1-\tfrac{1}{4}\norm{\sigma_{1}-\sigma_{2}}_{1}^{2}$. We now consider a lower
bound of the trace norm $\norm{\sigma_{1}-\sigma_{2}}_{1}$ by tracing out the
last $l$ qubits,

$\norm{\sigma_{1}-\sigma_{2}}_{1}\geq\norm{(\mathcal{I}_{k}\otimes\mathcal{I}_{1}\otimes\mathcal{E})(\outerproduct{\Omega_{k}}{\Omega_{k}})-(\mathcal{I}_{k}\otimes\mathcal{U}_{2})(\outerproduct{\Omega_{k}}{\Omega_{k}})}_{1},$
(245)

where $\mathcal{E}$ is a CPTP map that acts on the last $k-1$ qubits. Recall
that the $1$-norm distance in the Choi states upper bounds the diamond
distance in the CPTP maps up to the dimension factor $1/2^{k}$. From the
definition of $c$ in Eq. (236), we have the following inequality,

$\norm{\sigma_{1}-\sigma_{2}}_{1}\geq\frac{1}{2^{k}}\norm{\mathcal{I}_{1}\otimes\mathcal{E}-\mathcal{U}_{2}}_{\diamond}\geq\frac{c}{2^{k}}.$
(246)

Therefore, we have

$\tilde{F}(\rho_{1},\rho_{2})\leq\sqrt{1-(c/2^{k+2})^{2}}<1,$ (247)

which is a key result that will be used later.

We need to consider another pair of states. Consider the Pauli decomposition
of $U_{2}$ on the first qubit,

$U_{2}=\sum_{P\in\\{I,X,Y,Z\\}}P\otimes\tilde{U}_{2,P},$ (248)

where $\tilde{U}_{2,P}$ is a complex matrix of dimension $2^{k-1}$. Because
$U_{2}$ does not act as identity on the first qubit, we have
$c^{\prime}:=\sum_{P\neq I}\Tr(\tilde{U}_{2,P}^{\dagger}\tilde{U}_{2,P})>0$ is
a positive constant. Consider the following matrix,

$M:=\sum_{P\in\\{X,Y,Z\\}}P\otimes\tilde{U}_{2,P},$ (249)

and define two $2k$-qubit pure states,

$\displaystyle\ket{\psi_{1}}$ $\displaystyle:=\ket{\Omega_{k}},$ (250)
$\displaystyle\ket{\psi_{2}}$
$\displaystyle:=I_{k}\otimes\left(U_{2}^{\dagger}\frac{M}{\sqrt{\Tr(M^{\dagger}M)/2^{k}}}\right)\ket{\Omega_{k}}.$
(251)

By the definition of $c^{\prime}$ and $M$, we have
$\Tr(M^{\dagger}M)=2c^{\prime}>0$ and

$\tilde{F}(\outerproduct{\psi_{1}}{\psi_{1}},\outerproduct{\psi_{2}}{\psi_{2}})=|\braket{\psi_{1}}{\psi_{2}}|^{2}=2c^{\prime}/2^{k}>0.$
(252)

Furthermore, the overlap between
$\mathcal{E}_{x}(\outerproduct{\psi_{x}}{\psi_{x}})$ satisfies

$\displaystyle\Tr\left(\mathcal{E}_{1}(\outerproduct{\psi_{1}}{\psi_{1}})\mathcal{E}_{2}(\outerproduct{\psi_{2}}{\psi_{2}})\right)=\frac{1}{2c^{\prime}/2^{k}}\cdot\frac{1}{2^{k}}\cdot\frac{1}{2^{k}}\cdot$
(253) $\displaystyle\sum_{P,Q\in\\{X,Y,Z\\}}\Tr(\Tr_{\leq
k}(P\otimes((\tilde{U}_{2,P}^{\dagger}\otimes
I_{l})V_{2}^{\dagger}V_{1}(\tilde{U}_{1}\otimes I_{l})))\Tr_{\leq
k}(Q\otimes((\tilde{U}_{1}^{\dagger}\otimes
I_{l})V_{1}^{\dagger}V_{2}(\tilde{U}_{2,Q}\otimes I_{l}))))=0,$ (254)

which implies that there exists a two-outcome projective measurement
$\mathcal{M}$ that could perfectly distinguish between the two states
$\mathcal{E}_{1}(\outerproduct{\psi_{1}}{\psi_{1}})$ and
$\mathcal{E}_{2}(\outerproduct{\psi_{2}}{\psi_{2}})$.

Consider $N$ queries to $\mathcal{E}_{x}$ to obtain $\rho_{x}^{\otimes N}$,
where the number of queries is

$N:=\max\left(1,\left\lceil\frac{\log\left((2c^{\prime}/2^{k})\right)}{\log\left(\sqrt{1-(c/2^{k+2})^{2}}\right)}\right\rceil\right)=\mathcal{O}(1).$
(255)

Using Eq. (241), (247), and (252), we have

$\tilde{F}(\rho_{1}^{\otimes N},\rho_{2}^{\otimes
N})=\tilde{F}(\rho_{1},\rho_{2})^{N}\leq\sqrt{1-(c/2^{k+2})^{2}}^{N}\leq(2c^{\prime}/2^{k})=\tilde{F}(\outerproduct{\psi_{1}}{\psi_{1}},\outerproduct{\psi_{2}}{\psi_{2}}).$
(256)

From Lemma 1 of [98], there exists a CPTP map $\mathcal{T}$ that takes
$\rho_{x}$ to $\outerproduct{\psi_{x}}{\psi_{x}}$ for $x=1,2$. We apply
$\mathcal{T}$ to $\rho_{x}$. And we evoke one additional query to
$\mathcal{E}_{x}$ to obtain
$\mathcal{E}_{x}(\outerproduct{\psi_{x}}{\psi_{x}})$. Finally, we perform the
two-outcome projective measurement $\mathcal{M}$ to perfectly distinguish
between $\mathcal{E}_{1}(\outerproduct{\psi_{1}}{\psi_{1}})$ and
$\mathcal{E}_{2}(\outerproduct{\psi_{2}}{\psi_{2}})$. Together, with
$N+1=\mathcal{O}(1)$ queries to $\mathcal{E}_{x}$, we can perfectly
distinguish between $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. ∎

We are now ready to prove Lemma 20. The central idea is a bipartite tournament
with a potential local inversion on one side and all possible non-local
inversion on the other side.

###### Proof of Lemma 20.

Each query to $\mathcal{E}_{x}$ allows us to create $1$ query to any one of
the following CPTP maps,

$\mathcal{E}_{x,i}=(\mathcal{E}_{x}\circ\mathcal{U}^{\dagger}_{i}),\,\,\forall
i=1,\ldots,m.$ (257)

The algorithm proceeds by going through all of $i$ one by one. For each $i$,
the algorithm creates two sets,

$\displaystyle S_{i}$
$\displaystyle:=\left\\{y\in\\{1,\ldots,m\\}\,\,|\,\,U_{y}U_{i}^{\dagger}\,\,\mbox{acts
as identity on the first qubit}\right\\},$ (258) $\displaystyle T_{i}$
$\displaystyle:=\\{1,\ldots,m\\}\setminus S_{i}.$ (259)

Note that by definition, $i\in S_{i}$ and $i\not\in T_{i}$. For each $y\in
T_{i}$, the algorithm uses the algorithm given in the proof of Lemma 21 to
test whether $\mathcal{E}_{x,i}$ is equal to $\mathcal{E}_{y,i}$ or
$\mathcal{E}_{i,i}$. If $\mathcal{E}_{x,i}$ is indeed equal to one of them,
then the algorithm in Lemma 21 is guaranteed to output the one that is equal
to $\mathcal{E}_{x,i}$. If not, then the algorithm in Lemma 21 will output
$\mathcal{E}_{y,i}$ or $\mathcal{E}_{i,i}$ arbitrarily. After going through
all $y\in T_{i}$, if between $\mathcal{E}_{y,i}$ and $\mathcal{E}_{i,i}$,
$\mathcal{E}_{i,i}$ is always chosen for all $y\in T_{i}$, then the algorithm
sets $i^{*}:=i$ and terminates the for-loop over $i$. The algorithm outputs
$U_{i^{*}}^{\dagger}$ as the claimed perfect local inversion of $U_{x}$ on the
first qubit.

By construction, the total number of queries to $\mathcal{E}_{x}$ in the above
algorithm is a constant. We now prove that (a) $i^{*}$ can always be found by
the above algorithm and (b) $U_{i^{*}}^{\dagger}$ is a perfect local inversion
of $U_{x}$ on the first qubit. The proof is separated into the following two
paragraphs addressing each claim.

#####  $i^{*}$ can always be found.

When $i=x$, for each $y\in T_{i}$, we are testing whether $\mathcal{E}_{x,x}$
is equal to $\mathcal{E}_{y,x}$ or $\mathcal{E}_{x,x}$. Because
$U_{y}U_{x}^{\dagger}$ does not act as identity on the first qubit by
definition of $T_{x}$, Lemma 21 shows that the algorithm will always return
$\mathcal{E}_{x,x}$ when deciding between $\mathcal{E}_{y,x}$ and
$\mathcal{E}_{x,x}$. Hence when $i=x$, the algorithm will set $i^{*}:=i$ and
terminate the for-loop over $i$. The algorithm could also terminate earlier
for some $i<x$ but will always terminate when $i=x$. Therefore, $i^{*}$, as
defined by the algorithm previously, can always be found.

#####  $U_{i^{*}}^{\dagger}$ is a perfect local inversion of $U_{x}$ on the
first qubit.

We first show by contradiction that $x\not\in T_{i^{*}}$. Suppose that $x\in
T_{i^{*}}$. For $y=x\in T_{i^{*}}$, we would be testing whether
$\mathcal{E}_{x,i^{*}}$ is equal to $\mathcal{E}_{x,i^{*}}$ or
$\mathcal{E}_{i^{*},i^{*}}$. Recall that $i^{*}\not\in T_{i^{*}}$, thus $x\neq
i^{*}$. Lemma 21 thus implies that the algorithm will always return
$\mathcal{E}_{x,i^{*}}$ when deciding between $\mathcal{E}_{x,i^{*}}$ and
$\mathcal{E}_{i^{*},i^{*}}$. As a result, the condition defining $i^{*}$ is
not satisfied, which is a contradiction. Because $S_{i^{*}}\cup
T_{i^{*}}=\\{1,\ldots,m\\}$, we have $x\in S_{i^{*}}$. which means have
$U_{x}U_{i^{*}}^{\dagger}$ acts as identity on the first qubit. As a result,
$U_{i^{*}}^{\dagger}$ is a perfect local inversion of $U_{x}$ on the first
qubit. ∎

###  6.2 Learning geometrically-local shallow circuits over a finite gate set
(Proof of Theorem 8)

We present the algorithm for learning an unknown geometrically-local shallow
quantum circuit $U$ over a finite gate set. Let the geometry over $n$ qubits
be represented by a graph $G=(V,E)$ with degree $\kappa=\mathcal{O}(1)$, the
depth of $U$ be $d=\mathcal{O}(1)$, and the finite gate set be $\mathcal{G}$
with $|\mathcal{G}|=\mathcal{O}(1)$. This algorithm requires coherent quantum
queries to the unknown unitary $U$. The key ideas are constructing $n$ CPTP
maps $\mathcal{E}^{U}_{i},\forall i\in\\{1,\ldots,n\\}$ from $\mathcal{O}(1)$
queries to $U$, utilizing Lemma 20 to find perfect local inversion among
finite choices, and using Definition 13 and Lemma 7 to sew the local inversion
unitaries together.

We consider the lightcone $L_{d}(i)$ of the geometry for qubit $i$ under the
unknown depth-$d$ geometrically-local circuit $U$ in Definition 10 and the
properties of the lightcones given in Lemma 16.

For each qubit $i$ in the $n$-qubit system, we can always decompose the
depth-$d$ geometrically-local quantum circuit $U$ as the following,

$U=\left(I_{i}\otimes W^{(i)}\otimes I_{\notin
L_{2d}(i)}\right)\left(U^{(i)}\otimes\tilde{W}^{(i)}\right),$ (260)

where $U^{(i)}$ acts on qubits in the set $L_{d}(i)$, $\tilde{W}^{(i)}$ acts
on qubits not in the set $L_{d}(i)$, $W^{(i)}$ acts on qubits in the set
$L_{2d}(i)\setminus\\{i\\}$, and $I_{i},I_{\notin L_{3d}(i)}$ are identity
matrices acting on qubit $i$ and qubits not in $L_{3d}(i)$, respectively.
Furthermore, $U^{(i)},W^{(i)},\tilde{W}^{(i)}$ are all subcircuits (circuits
containing a subset of gates) of the unknown depth-$d$ geometrically-local
circuits $U$. We define the CPTP map $\mathcal{E}^{U}_{i}$,

$\displaystyle\mathcal{E}^{U}_{i}(\rho)$ $\displaystyle:=\Tr_{\notin
L_{2d}(i)}\left(U\left(\rho\otimes\frac{I_{\notin
L_{d}(i)}}{2^{n-|L_{d}(i)|}}\right)U^{\dagger}\right)$ (261)
$\displaystyle=\left(\mathcal{I}_{i}\otimes\mathcal{W}^{(i)}\right)\left(\mathcal{U}^{(i)}\otimes\mathcal{I}_{L_{2d}(i)\setminus
L_{d}(i)}\right)\left(\rho\otimes\frac{I_{L_{2d}(i)\setminus
L_{d}(i)}}{2^{|L_{2d}(i)|-|L_{d}(i)|}}\right),$ (262)

where $\rho$ is a density matrix for qubits in $L_{d}(i)$, $I_{\notin
L_{d}(i)}$ is the identity matrix over qubits not in $L_{d}(i)$, $I_{\notin
L_{d}(i)}/2^{n-|L_{d}(i)|}$ is the maximally mixed state for qubits not in
$L_{d}(i)$, and $\Tr_{\notin L_{2d}(i)}$ traces out all qubits not in
$L_{2d}(i)$. Because $\mathcal{E}^{U}_{i}(\rho)$ uses a single query to $U$,
naively, one would expect that to obtain a query to $\mathcal{E}^{U}_{i}$ for
every qubit $i$ requires $n$ queries to $U$. The following lemma shows that we
can do much more efficiently than what one would naively expect.

######  Lemma 22 (Queries to every $\mathcal{E}^{U}_{i}$ from only
$\mathcal{O}(1)$ queries to $U$).

We can construct a query to every $\mathcal{E}^{U}_{i},1\leq i\leq n$ from
only $\mathcal{O}(1)$ queries to the unknown constant-depth geometrically-
local circuit $U$.

###### Proof.

Let $d=\mathcal{O}(1)$ be the depth of the circuit $U$. We consider a graph
$G^{(3d)}$ over $n$ qubits, where each pair of qubits is connected by an edge
if their distance in $G$ is at most $3d$. The degree of $G^{(3d)}$ is at most
$(\kappa+1)^{3d}=\mathcal{O}(1)$. The graph only has $\mathcal{O}(n)$ edges
and can be constructed as an adjacency list in time $\mathcal{O}(n)$. Let us
define a coloring of the graph $G^{(3d)}$. By the standard greedy coloring
algorithm, we can find a color $c^{(3d)}(i)$ for each qubit $i$ in graph
$G^{(3d)}$, where no adjacent vertices can have the same color, and there are
only $\chi^{(3d)}$ distinct colors with

$\chi^{(3d)}\leq(\kappa+1)^{3d}+1=\mathcal{O}(1).$ (263)

The greedy coloring algorithm runs in time linear in the number of edges in
$G^{(3d)}$, which is linear in the number $n$ of qubits.

For each color $c=1,\ldots,\chi^{(3d)}$, we consider the set of qubits with
color $c$. We can construct one query to every $\mathcal{E}^{U}_{i}$ for
qubits $i$ with color $c^{(3d)}(i)=c$ from only one query to $U$. By the
construction of the graph coloring, for two distinct qubits $i\neq j$ with the
same color $c$, $L_{3d}(i)\cap L_{3d}(j)=\varnothing$. We now define the
following sets of qubits for the color $c$,

$A(c):=\left\\{i\in\\{1,\ldots,n\\}\,\,\big{|}\,\,c^{(3d)}(i)=c\right\\},\quad
B_{q}(c):=\bigcup_{i:c^{(3d)}(i)=c}L_{q}(i),$ (264)

for any integer $q\geq 1$. Given the definition of $U^{(i)},W^{(i)}$ in Eq.
(260) for each qubit $i$. We can further decompose the shallow circuit $U$ as

$U=\left[\left(I_{A(c)}\otimes\bigotimes_{i:c^{(3d)}(i)=c}W^{(i)}\right)\otimes
I_{\notin
B_{2d}(c)}\right]\left[\left(\bigotimes_{i:c^{(3d)}(i)=c}U^{(i)}\right)\otimes\tilde{W}^{(c)}\right],$
(265)

where $\tilde{W}^{(c)}$ acts on qubits not in $B_{d}(c)$. Consider
initializing the qubits not in $B_{d}(c)$ as the maximally mixed state,
evolving under $U$, and tracing out any qubits not in $B_{2d}(c)$. The
resulting CPTP map $\mathcal{E}_{c}^{U}$ from qubits in $B_{d}(c)$ to qubits
in $B_{2d}(c)$ can be written as

$\mathcal{E}_{c}^{U}(\rho)=\left(\mathcal{I}_{A(c)}\otimes\bigotimes_{i:c^{(3d)}(i)=c}\mathcal{W}^{(i)}\right)\left(\bigotimes_{i:c^{(3d)}(i)=c}\mathcal{U}^{(i)}\otimes\mathcal{I}_{B_{2d}(i)\setminus
B_{d}(i)}\right)\left(\rho\otimes\frac{I_{B_{2d}(c)\setminus
B_{d}(c)}}{2^{|B_{2d}(c)|-|B_{d}(c)|}}\right),$ (266)

where $\rho$ is a density matrix over qubits in $B_{d}(c)$. It is not hard to
see that

$\mathcal{E}_{c}^{U}=\bigotimes_{i:c^{(3d)}(i)=c}\mathcal{E}_{i}^{U}.$ (267)

Because $\mathcal{E}_{c}^{U}$ only requires one query to $U$, we can create
$\mathcal{E}_{i}^{U}$ for all qubit $i$ with color $c$ from one query to $U$.
Since there is only $\chi^{(3d)}=\mathcal{O}(1)$ colors, we can create a query
to every $\mathcal{E}^{U}_{i},1\leq i\leq n$ from only $\mathcal{O}(1)$
queries to the unknown circuit $U$. ∎

Because $U$ is over a finite gate set with size $\mathcal{O}(1)$, we have
$U^{(i)}$ and $W^{(i)}$ only have a constant number of choices. Furthermore,
both $U^{(i)}$ and $W^{(i)}$ act on a constant number of qubits because
$|L_{d}(i)|=\mathcal{O}(1),|L_{2d}(i)|=\mathcal{O}(1)$ for a constant depth
$d$. From Lemma 20, for each qubit $i$, through $\mathcal{O}(1)$ queries to
$\mathcal{E}^{U}_{i}$, we can learn a perfect local inversion $V_{i}$ of
$U^{(i)}$ on qubit $i$ with no failure probability. The local inversion
unitary $V_{i}$ is the inverse of one of the possible choices for $U^{(i)}$.
Hence, $V_{i}$ is a geometrically-local depth-$d$ circuit that only acts on
qubits in $L_{d}(i)$. Combining with Lemma 22, from only $\mathcal{O}(1)$
queries to $U$, we can learn $V^{(i)},\forall i=1,\ldots,n$, such that

$\mathcal{U}^{(i)}\mathcal{V}_{i}=\mathcal{I}^{(i)}\otimes\mathcal{E}^{\mathcal{U}^{(i)}\mathcal{V}_{i}}_{\neq
i},$ (268)

where $\mathcal{I}^{(i)}$ is the identity map on qubit $i$ and
$\mathcal{E}^{\mathcal{U}^{(i)}\mathcal{V}_{i}}_{\neq i}$ is the reduced
channel of $\mathcal{U}^{(i)}\mathcal{V}_{i}$ with qubit $i$ removed. The
quantum computational time is given by $\mathcal{O}(n)$. We now show that
$V_{i}$ is also the perfect local inversion unitary for $U$ on qubit $i$. To
see this, recall the decomposition in Eq. (260), we have

$\displaystyle\mathcal{U}\mathcal{V}_{i}$
$\displaystyle=\left(\mathcal{I}_{i}\otimes\mathcal{W}^{(i)}\otimes\mathcal{I}_{\notin
L_{2d}(i)}\right)\left(\mathcal{U}^{(i)}\mathcal{V}_{i}\otimes\tilde{\mathcal{W}}^{(i)}\right)$
(269)
$\displaystyle=\mathcal{I}^{(i)}\otimes\left(\left(\mathcal{W}^{(i)}\otimes\mathcal{I}_{\notin
L_{2d}(i)}\right)\left(\mathcal{E}^{\mathcal{U}^{(i)}\mathcal{V}_{i}}_{\neq
i}\otimes\tilde{\mathcal{W}}^{(i)}\right)\right)$ (270)
$\displaystyle=\mathcal{I}^{(i)}\otimes\mathcal{E}^{\mathcal{U}\mathcal{V}_{i}}_{\neq
i}.$ (271)

We can now use Definition 13 and Lemma 7 to sew the perfect local inversion
unitaries together. This gives the following $2n$-qubit unitary,

$U_{\mathrm{sew}}(V_{1},\ldots,V_{n})=S\left[\prod_{i=1}^{n}\left(V_{i}^{(1)}\right)S_{i}\left(V_{i}^{(1)}\right)^{\dagger}\right]=U\otimes
U^{\dagger},$ (272)

where $V_{i}^{(1)}$ is the unitary $V_{i}$ acting on the first set of $n$
qubits.

We now show that there exists a sewing ordering such that
$U_{\mathrm{sew}}(V_{1},\ldots,V_{n})$ is a constant-depth geometrically-local
circuit. Given the geometry over $n$ qubits represented by a graph $G=(V,E)$.
Consider a graph $G^{(2d)}$ over $n$ qubits, where each pair $(i,j)$ of qubits
are connected by an edge if $i,j$ is of distance at most $2d$ in the geometric
graph $G$. Hence, equivalently, for all $(i,j)$ not connected by an edge in
$G^{(2d)}$, we have

$L_{d}(i)\cap L_{d}(j)=\varnothing.$ (273)

The degree of $G^{(2d)}$ is bounded above by $(\kappa+1)^{2d}$. And $G^{(2d)}$
can be constructed as an adjacency list in time $\mathcal{O}(n)$. Because the
graph has a constant degree, we can use a $\mathcal{O}(n)$-time greedy graph
coloring algorithm to color the $n$-qubit graph $G^{(2d)}$ using only a
constant number of colors. For each node/qubit $i$, we consider $c(i)$ to be
the color. The sewing order for the $n$ local inversion unitaries $V_{i}$ is
given by the greedy graph coloring, where we order from the smallest color to
the largest color. By the definition of graph coloring, for any pair $i,j$ of
qubits with the same color, we have $L_{d}(i)\cap L_{d}(j)=\varnothing.$
Furthermore, $V_{i}$ is a constant-depth geometrically-local circuit that only
acts on a constant number of qubits. Therefore, for any color $c^{\prime}$, we
can find an implementation of the $2n$-qubit unitary

$\prod_{i:c(i)=c^{\prime}}\left(V_{i}^{(1)}\right)S_{i}\left(V_{i}^{(1)}\right)^{\dagger}$
(274)

with a constant-depth geometrically-local quantum circuit in time
$\mathcal{O}(n)$. Since there is only a constant number of colors, the
$2n$-qubit unitary $U_{\mathrm{sew}}(V_{1},\ldots,V_{n})$ in Eq. (272) with
the color-based ordering can be implemented with a constant-depth
geometrically-local quantum circuit in time $\mathcal{O}(n)$. Finally, define
an $n$-qubit channel $\hat{\mathcal{E}}$ as follows,

$\hat{\mathcal{E}}(\rho):=\Tr_{>n}\left(\mathcal{U}_{\mathrm{sew}}(V_{1},\ldots,V_{n})(\rho\otimes\outerproduct{0^{n}}{0^{n}})\right),$
(275)

which can be implemented as a geometrically-local constant-depth quantum
circuit over $2n$ qubits. Because
$U_{\mathrm{sew}}(V_{1},\ldots,V_{n})=U\otimes U^{\dagger}$ from Eq. (272), we
have

$\mathcal{E}=\mathcal{U}$ (276)

with probability one. This concludes the proof of Theorem 8.

##  7 Hardness for learning log-depth quantum circuits

We have seen from the previous appendices that learning general constant-depth
quantum circuits can be done efficiently. A natural follow-up question is
whether one could efficiently learn log-depth quantum circuits. In the
following, we show that learning log-depth quantum circuits to a constant
diamond distance is exponentially hard, even when we allow coherent quantum
queries to $U$. Hence, the problem of learning quantum circuits transitions
from being polynomially easy to exponentially hard when we go from
$\mathcal{O}(1)$-depth to $\mathcal{O}(\log n)$-depth.

######  Proposition 3 (Hardness for learning log-depth circuits).

Consider an unknown $n$-qubit unitary $U$ generated by a $\mathcal{O}(\log
n)$-depth circuit over arbitrary two-qubit gates with $n$ ancilla qubits. We
have

  * •

Learning $U$ to $1/3$ diamond distance with high probability requires
$\exp(\Omega(n))$ queries.

  * •

Distinguishing whether $U$ equals to the identity $I$ or is $1/3$-far from the
identity $I$ in diamond distance with high probability requires
$\exp(\Omega(n))$ queries.

###### Proof.

Without loss of generality, we consider $n$ to be $2^{k}$ for an integer $k$.
Consider the unknown unitary $U$ to be $I$ or one of $U_{x},\forall
x\in\\{0,1\\}^{n}$. The unitary $U_{x}$ is defined to be

$U_{x}\ket{y}=\begin{cases}1,&x=y,\\\ -1,&x\neq y,\end{cases}$ (277)

for any $y\in\\{0,1\\}^{n}$. The $n$-qubit unitary $U_{x}$ can be constructed
as follows,

$U_{x}=\left(\prod_{\begin{subarray}{c}1\leq i\leq n\\\
x_{i}=0\end{subarray}}X_{i}\right)C^{n}Z\left(\prod_{\begin{subarray}{c}1\leq
i\leq n\\\ x_{i}=0\end{subarray}}X_{i}\right),$ (278)

where $X_{i}$ is the $X$ gate on the $i$-th qubit, and $C^{n}Z$ is a
controlled-Z gate controlled on all qubits. The circuit
$\prod_{\begin{subarray}{c}i:\,x_{i}=0\end{subarray}}X_{i}$ can be implemented
in one layer. We can implement $C^{n}Z$ using $n$ ancilla qubits in depth
$\mathcal{O}(\log n)$. To see this, we first construct a
$(2^{k}+2^{k}-1)$-qubit unitary $V$ recursively as follows:

  1. 1.

Set the $n=2^{k}$ qubits to be the first set of control qubits. Set
$j\leftarrow k$.

  2. 2.

Consider the $2^{j}$ control qubits as $2^{j-1}$ pairs of two control qubits.
Include $2^{j-1}$ new ancilla qubits initialized at $\ket{0}^{n}$.

  3. 3.

For each pair of control qubits, implement a $\mathrm{CCX}$ gate on each newly
added ancilla qubit controlled on the two control qubits.

  4. 4.

Set the new $2^{j-1}$ ancilla qubits as the set of control qubits. Set
$j\leftarrow j-1$.

  5. 5.

If $j>0$, repeat Step 2.

We can compile the $\mathrm{CCX}$ gate acting on three qubits to be a sequence
with a constant number of two-qubit gates. The depth of $V$ is
$\mathcal{O}(\log n)$. The unitary $V$ computes whether all $n$ qubits are one
and stores the result in the $2n-1$ qubit. We can implement the $n$-qubit
unitary $C^{n}Z$ using a $2n$-qubit $\mathcal{O}(\log n)$-depth circuit with
$n$ ancilla qubits,

$C^{n}Z\otimes\ket{0^{n}}=(V\otimes
I)^{\dagger}\,X_{2n}\,\mathrm{CZ}_{2n-1,2n}\,X_{2n}\,(V\otimes
I)\,(I_{n}\otimes\ket{0^{n}}),$ (279)

where $X_{2n}$ is the NOT gate on the one ancilla qubit not acted by $V$, $I$
is a single-qubit identity, $I_{n}$ is an $n$-qubit identity, and
$\mathrm{CZ}_{2n-1,2n}$ is controlled on the last ancilla qubit added in the
recursive construction of $V$ and acts on the one ancilla qubit not acted by
$V$.

If one could learn $U$ up to $1/3$ error in the diamond distance with high
probability or if one could distinguish whether $U$ equals to the identity $I$
or is $1/3$-far from the identity $I$ in the diamond distance with high
probability, then one could successfully distinguish between the identity map
$I$ and the unitary $U_{x}$. Distinguishing $I$ or one of $U_{x},\forall
x\in\\{0,1\\}^{n}$ is the well-known Grover search problem. Hence, from the
well-known Grover lower bound [106], we have the number of queries must be at
least $\Omega(2^{n/2})=\exp(\Omega(n))$. This concludes the proof. ∎

##  8 Learning quantum states generated by shallow circuits in 2D

Given copies of an unknown quantum state $\ket{\psi}=U\ket{0^{n}}$, with the
promise that $U$ is a depth-$d$ circuit acting on a 2-dimensional lattice. In
this section, we present an algorithm to learn a description of a shallow
circuit that prepares $\ket{\psi}$ up to a desired precision. The algorithm
can be viewed as first collecting a sufficiently large randomized measurement
dataset [84, 88] from the unknown state and then classically reconstructing
the circuit based on the dataset.

######  Definition 20 (Randomized measurement dataset for an unknown state).

The learning algorithm accesses the unknown state via a randomized measurement
dataset of the following form,

$\mathcal{T}_{\ket{\psi}}(N)=\left\\{\ket{\phi_{\ell}}=\bigotimes_{i=1}^{n}\ket{\phi_{\ell,i}}\right\\}_{\ell=1}^{N}.$
(280)

A randomized measurement dataset of size $N$ is constructed by obtaining $N$
samples from the unknown state $\ket{\psi}$. One sample is obtained from one
experiment given as follows: measure every qubit of $\ket{\psi}$ under a
random Pauli basis. The measurement collapses the state $\ket{\psi}$ to a
state $\ket{\phi_{\ell}}=\bigotimes_{i=1}^{n}\ket{\phi_{\ell,i}}$, where
$\ket{\phi_{\ell,i}}$ is a single-qubit stabilizer state in
$\mathrm{stab}_{1}$.

Together, $N$ copies of $\ket{\psi}$ construct a dataset
$\mathcal{T}_{\ket{\psi}}(N)$ with $N$ samples. The dataset can be represented
efficiently on a classical computer with $\mathcal{O}(Nn)$ bits.

######  Theorem 9 (Learning quantum states generated by shallow circuits in
2D).

Given copies of an unknown state $\ket{\psi}$, with the promise that
$\ket{\psi}=U\ket{0^{n}}$ for an unknown $n$-qubit circuit $U$ with circuit
depth $d$ acting on a 2-dimensional lattice, then the following holds.

  1. 1.

Suppose each two-qubit gate in $U$ is chosen from $\mathrm{SU}(4)$. With a
randomized measurement dataset $\mathcal{T}_{\ket{\psi}}(N)$ of size

$N=\frac{2^{\mathcal{O}(d^{2})}n^{50}}{\varepsilon^{64}}\log\frac{n}{\delta},$
(281)

we can learn a quantum circuit $V$ with depth $3d$ acting on $n+m$ qubits on
an extended 2-dimensional lattice, such that

$\frac{1}{2}\norm{\Tr_{B}\left(V\outerproduct{0^{n}}{0^{n}}_{A}\otimes\outerproduct{0^{m}}{0^{m}}_{B}V^{\dagger}\right)-\outerproduct{\psi}{\psi}}_{1}\leq\varepsilon,$
(282)

with probability at least $1-\delta$. The computational time to learn $V$ is
$\left(\frac{nd^{3}}{\varepsilon}\right)^{\mathcal{O}(d^{3})}$. The number of
ancilla qubits can be chosen as $m=tn$ for an arbitrarily small constant
$t>0$.

  2. 2.

In addition, if each two-qubit gate in $U$ is chosen from a finite gateset of
constant size and $d=\mathcal{O}(1)$, then there is an algorithm that learns
an exact preparation circuit $V$ with depth $3d$ acting on $n+m$ qubits, such
that
$V\ket{0^{n}}_{A}\ket{0^{m}}_{B}=\ket{\psi}_{A}\otimes\ket{\mathrm{junk}}_{B}$
with probability $1-\delta$, with sample complexity
$N=\mathcal{O}(\log(n/\delta))$ and time complexity
$\mathcal{O}(n\log(n/\delta))$. The number of ancilla qubits can be chosen as
$m=tn$ for an arbitrarily small constant $t>0$.

  3. 3.

In addition, if each two-qubit gate in $U$ is chosen from a finite gateset of
constant size and $d=\mathcal{O}(1)$, then there is an algorithm that learns a
circuit $V$ with depth $2^{c\cdot d^{2}}$ (for some universal constant $c$)
acting on $n$ qubits (without using any ancilla), such that
$\left|\bra{0^{n}}V^{\dagger}\ket{\psi}\right|^{2}\geq 1-\varepsilon$ with
probability $1-\delta$, with query complexity $N=\mathcal{O}(\log(n/\delta))$
and time complexity $(n/\varepsilon)^{\mathcal{O}(1)}$.

######  Remark 8.

The first claim in Theorem 9 holds for any gateset and any circuit depth $d$
(which may not be a constant), while the second and third claims are
specialized to the simpler setting of finite gateset and constant depth.

In particular, the first claim implies that when $d=\mathrm{polylog}(n)$, the
state $\ket{\psi}$ can be learned within $\varepsilon$ trace distance with
sample complexity
$N=\frac{2^{\mathrm{polylog}(n)}}{\varepsilon^{\mathcal{O}(1)}}\log\frac{n}{\delta}$,
in time $(n/\varepsilon)^{\mathrm{polylog}(n)}$.

We prove Theorem 9 in the remainder of this section. Next we give a detailed
presentation of the argument outlined in Section 2.2.1 and 2.2.2. We start by
assuming a finite gate set, and address general $\mathrm{SU}(4)$ gates in
Section 8.4.

###  8.1 Learning 1D states by solving a constraint satisfaction problem

We start by assuming $U$ is a depth-$d$ circuit acting on a 1D lattice, for
some constant $d=\mathcal{O}(1)$. The learning problem is equivalent to
finding a low-depth circuit $V$ such that $V\ket{\psi}=\ket{0^{n}}$. Consider
Fig. 3 where $A$, $B$, $C$ are contiguous regions of size $3d$. Suppose we
want to locally invert the qubits in region $A$ back to $\ket{0}_{A}$. We can
do so by undoing the gates within the lightcone of $A$, i.e. apply a depth-$d$
circuit of the blue shape (that acts on $4d$ qubits) on top of $\ket{\psi}$.
As we do not know what is the correct circuit to apply, we enumerate over all
possible circuits of the blue shape (we can do it because its size is small).
There are $2^{\mathcal{O}(d^{2})}$ such circuits in total, and for each
circuit we apply it to $\ket{\psi}$ and test if the state on $A$ actually
equals to $\ket{0}_{A}$ (we can do it by measuring many copies, and seeing the
outcome all-0 with high probability). For now we assume that all local
inversion circuits can be found exactly; this is addressed in more detail
later.

At the end of this procedure, we end up with a list of candidate circuits
$\mathcal{C}_{A}$ of the blue shape, such that each of them is a valid local
inversion of $A$, i.e., for all $V_{A}\in\mathcal{C}_{A}$ we have
$V_{A}\ket{\psi}=\ket{0}_{A}\otimes\ket{\psi^{\prime}}$. The inverse of the
lightcone of $A$ in the unknown circuit $U$ is among them, but we don’t know
which one. We repeat the same procedure for each region $A$, $B$, $C$, … and
get a list of candidate local inversions $\mathcal{C}_{A}$, $\mathcal{C}_{B}$,
$\mathcal{C}_{C}$, … for each region.

Note that in this construction shown in Fig. 3, only the local inversions
acting on neighboring regions could overlap. For example, the blue and green
circuit does not overlap because $A$ and $C$ are separated by distance $3d$,
and each circuit could “spread” into region $B$ for distance at most $d$.

The next observation is that there are certain blue circuits in
$\mathcal{C}_{A}$ that share the same overlapping region with certain red
circuits in $\mathcal{C}_{B}$, i.e. they share the same gates in the
overlapping triangle of blue and red. For example, the inverse of the
lightcone of $A$ in $U$ and the inverse of the lightcone of $B$ in $U$ share
the same overlap. We call such circuits “consistent” with each other. Note
that if two circuits are consistent, they can be merged into a bigger one. For
example, take a blue circuit and a red circuit that are consistent, then they
can be merged by considering the union of the gates, and applying the merged
circuit to $\ket{\psi}$ will simultaneously invert both regions $A$ and $B$.
If we can find a local inversion for each region such that all nearest
neighbors are consistent, then they can be merged into a depth-$d$ circuit $V$
that satisfies $V\ket{\psi}=\ket{0^{n}}$.

$d$$d$$3d$$A$$B$$C$ Figure 3: Efficient learning of quantum states generated
by a shallow circuit in 1D. For each local region $A,B,C,\dots$ we find a list
of local inversion circuits, and merge them together by solving a constraint
satisfaction problem.

Now the task can be viewed as a constraint satisfaction problem: for each
region, find a local inversion circuit among all candidate local inversions
(there are at most $2^{\mathcal{O}(d^{2})}$ choices), such that each pair of
nearest neighbor circuits are consistent. This can be solved efficiently by a
simple dynamic programming algorithm in time $n\cdot 2^{\mathcal{O}(d^{2})}$.

To be more specific, suppose the system is divided into $L=\frac{n}{3d}$
regions of size $3d$ as in Fig. 3, and suppose we have found at most
$M=2^{\mathcal{O}(d^{2})}$ local inversions for each region. These circuits
are stored in an array $C$, where $C[i][j]$ denotes the $j$th local inversion
circuit for the $i$th region. Define an arrays $cost$, where $cost[i][j]=0$ if
there exists a consistent assignment at locations $1,2,\dots,i$ where
$C[i][j]$ is used at location $i$; and $cost[i][j]\geq 1$ otherwise (let
$cost[0][j]=0$ for all $j$). Also define an array $prev$, where $prev[i][j]$
is an index $k$, such that there exists a consistent assignment at locations
$1,2,\dots,i$ where $C[i][j]$ is used at location $i$ and $C[i-1][k]$ is used
at location $i-1$. $prev[i][j]$ is not defined when $cost[i][j]\geq 1$.

Once these arrays are constructed, we can take any circuit $j$ such that
$cost[L][j]=0$, and construct a consistent assignment by tracing back through
the $prev$ array. Let $temp$ be an array of size $M$. The following pseudocode
shows how to construct these arrays in time $\mathcal{O}(LM^{2})$.

1for $i=1,2,\dots,L$ do

2 for $j=1,2,\dots,M$ do

3 for $k=1,2,\dots,M$ do

4 $temp[k]=cost[i-1][k]+1\left[C[i][j]\text{ is not consistent with
}C[i-1][k]\right]$

5 $cost[i][j]=\min_{k}temp[k]$

6 if $cost[i][j]=0$ then

7 $prev[i][j]=\operatorname*{arg\,min}_{k}temp[k]$

Finally, note that the above procedure can be implemented by a two-step
process:

  1. 1.

Learn reduced density matrices of $\ket{\psi}$ supported on the lightcone of
each small region $A,B,C,\dots$.

  2. 2.

Find local inversions classically using the learned classical descriptions of
the reduced density matrices, and then solve the constraint satisfaction
problem.

This is because to find local inversions, say for the $B$ region, we only need
access to the reduced density matrix of $\ket{\psi}$ on the lightcone of $B$,
which has $5d$ qubits, since the local inversion only acts on the reduced
density matrix.

We need to learn $\frac{n}{3d}$ reduced density matrices of size at most $5d$.
The following general lemma shows the complexity for learning reduced density
matrices which we use throughout this section.

######  Lemma 23 (Learning reduced density matrices).

Let $\rho$ be an unknown $n$-qubit mixed state. Suppose we would like to learn
its reduced density matrices $\rho_{A_{1}},\dots,\rho_{A_{m}}$ where $A_{i}$
are subsystems of size at most $k$. Given a randomized measurement dataset
$\mathcal{T}_{\rho}(N)$ of size
$N=\frac{2^{\mathcal{O}(k)}}{\varepsilon^{2}}\log\frac{m}{\delta}$, we can
learn a list of Hermitian matrices (not necessarily density matrices)
$\\{\sigma_{A_{i}}\\}$ such that with probability at least $1-\delta$, we have
$\|\rho_{A_{i}}-\sigma_{A_{i}}\|_{1}\leq\varepsilon$ for all $i$.

###### Proof.

Fix some $i$, we can write
$\rho_{A_{i}}=\sum_{P\in\\{I,X,Y,Z\\}^{|A_{i}|}}\alpha_{P}P$. It suffices to
learn the Pauli coefficients
$\alpha_{P}=\frac{1}{2^{|A_{i}|}}\Tr(\rho_{A_{i}}P)=\frac{1}{2^{|A_{i}|}}\Tr(\rho
P)$. Suppose we have learned these coefficients (denote as $\\{\beta_{P}\\}$)
to within $\varepsilon_{1}$ precision. Let
$\sigma_{A_{i}}:=\sum_{P\in\\{I,X,Y,Z\\}^{|A_{i}|}}\beta_{P}P$, then

$\left\|\rho_{A_{i}}-\sigma_{A_{i}}\right\|_{1}^{2}\leq
2^{|A_{i}|}\Tr(\rho-\sigma)^{2}=2^{2|A_{i}|}\sum_{P}(\alpha_{P}-\beta_{P})^{2}\leq
2^{4k}\varepsilon_{1}^{2},$ (283)

which gives $\left\|\rho_{A_{i}}-\sigma_{A_{i}}\right\|_{1}\leq
2^{2k}\varepsilon_{1}$. Thus to achieve
$\left\|\rho_{A_{i}}-\sigma_{A_{i}}\right\|_{1}\leq\varepsilon$ it suffices to
learn $\\{\Tr(\rho P)\\}$ within accuracy $\varepsilon/2^{k}$; there are at
most $m\cdot 4^{k}$ $k$-local Pauli operators that we need to learn.

By the main result of [84], given a randomized measurement dataset of size

$N=\frac{2^{\mathcal{O}(k)}}{\varepsilon^{2}}\log\frac{m}{\delta},$ (284)

with probability at least $1-\delta$, we can learn all observables $\Tr(\rho
P)$ for the $m\cdot 4^{k}$ $k$-local Pauli operators within accuracy
$\varepsilon/2^{k}$; this is sufficient to obtain Hermitian matrices
$\\{\sigma_{A_{i}}\\}$ that satisfy
$\|\rho_{A_{i}}-\sigma_{A_{i}}\|_{1}\leq\varepsilon$ for all $i$. ∎

Note that when the gates in the unknown circuit are assumed to come from a
constant-size gate set, the reduced density matrices only have
$2^{\mathcal{O}(d^{2})}=\mathcal{O}(1)$ choices. Therefore, choosing
$\varepsilon$ to be some small constant in Lemma 23 suffices to learn all the
reduced density matrices _exactly_. This allows us to find the exact local
inversions by classically processing the reduced density matrices.

In summary, we have shown an algorithm that learns a depth-$d$ circuit $V$
that satisfies $\ket{\psi}=V^{\dagger}\ket{0^{n}}$ with success probability
$1-\delta$, using a randomized measurement dataset of size
$N=\mathcal{O}(\log(n/\delta))$, in time $\mathcal{O}(n)$.

###  8.2 Disentangling a 2D state

$A$$B$$C$$5d$$7d$$L$$M$$R$

(a)

$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{5}$$B_{6}$$B_{7}$$A_{1}$$A_{2}$$A_{3}$$A_{4}$$A_{5}$$A_{6}$$A_{7}$$A_{8}$

(b)

Figure 4: Learning to disentangle a quantum state generated by a shallow
circuit in 2D. (a) The middle region $M$ can be inverted by solving a similar
1D constraint satisfaction problem as in Fig. 3. (b) After inverting all the
gray $B_{i}$ regions, the remaining white $A_{i}$ regions are disentangled
into a tensor product of pure states.

Next we use the 1D techniques developed above to disentangle a state
$\ket{\psi}=U\ket{0^{n}}$, where $U$ is a depth-$d$ circuit acting on a 2D
lattice, for some constant $d=\mathcal{O}(1)$.

For this purpose we need to introduce a general property for quantum states
generated by low depth circuits, that is they have finite correlation length.

######  Lemma 24 (Finite correlation length).

Let $\ket{\psi}$ be a state generated by a depth-$d$ geometrically-local
circuit (Definition 9). Let $A$, $B$ be two regions that are separated by
distance at least $2d$ in the connectivity graph. Then $I(A:B)_{\psi}=0$. In
other words, let $\rho_{AB}$, $\rho_{A}$, $\rho_{B}$ be the reduced density
matrices of $\ket{\psi}$ on $AB$, $A$ and $B$, then
$\rho_{AB}=\rho_{A}\otimes\rho_{B}$.

###### Proof.

As $A$ and $B$ are separated by distance $2d$, their lightcones $L(A)$ and
$L(B)$ are disjoint. $\rho_{AB}=\rho_{A}\otimes\rho_{B}$ follows from the fact
that $\rho_{AB}$ is generated by the gates in $L(AB)$, which is a tensor
product between $L(A)$ and $L(B)$. ∎

Fig. 4 (a) shows a quantum state $\ket{\psi}$ (let
$\rho=\outerproduct{\psi}{\psi}$) prepared by a depth-$d$ circuit on a 2D
lattice, divided into three regions $L,M,R$. Since $L$ and $R$ are separated
by distance $5d$, Lemma 24 implies that $\rho_{LR}=\rho_{L}\otimes\rho_{R}$.
Although subsystems $L$ and $R$ are not entangled with each other, they both
could be entangled with $M$. Therefore we develop an argument to invert the
qubits in $M$, so that the state on $L$ and $R$ could become a tensor product
of pure states.

Note that $M$ is a 1D-like region. Our goal is to find a depth-$d$ circuit $V$
acting on a slightly wider strip (of width $7d$) around $M$, such that
$V\ket{\psi}=\ket{0}_{M}\otimes\ket{\psi^{\prime}}$. Such a circuit exists
since we can undo the lightcone of $M$, and we can find such a circuit using
the same argument as in the previous section. In Fig. 4 (a), the blue, red and
green regions play the same role as in Fig. 3. For example, we can find a set
of local inversions $\mathcal{C}_{A}$ for the shaded blue region $A$, by first
learning the reduced density matrix on the dotted blue region, and then
enumerating over all depth-$d$ circuits acting on the dotted blue region.
After learning a set of local inversions for each local region, we can find a
desired depth-$d$ circuit that inverts $M$ by solving a 1D constraint
satisfaction problem.

Now, we have effectively reduced the problem of learning $\ket{\psi}$ to the
following problem: given copies of a state $\ket{\psi_{1}}$ with the promise
that

  1. 1.

it is prepared by a depth-$2d$ circuit (defined on a 2D lattice) acting on
$\ket{0^{n}}$;

  2. 2.

its reduced density matrix on $M$ equals $\outerproduct{0}{0}_{M}$.

The goal is to learn the state $\ket{\psi_{1}}$. Note that in this new state
$\sigma=\outerproduct{\psi_{1}}{\psi_{1}}$, even though its circuit depth has
increased from $d$ to $2d$, the reduced state on $L$ and $R$ is still in
tensor product, i.e. $\sigma_{LR}=\sigma_{L}\otimes\sigma_{R}$, due to the
fact that $M$ (with width $5d$) is sufficiently wide. The main purpose of
inverting the $M$ region is that now $\sigma_{L}$ and $\sigma_{R}$ are
guaranteed to be pure states, as shown by the following.

######  Lemma 25.

Let $\rho_{ABC}$ be a pure state such that the following two properties hold:

  1. 1.

$\rho_{B}=\outerproduct{0}{0}_{B}$,

  2. 2.

$\rho_{AC}=\rho_{A}\otimes\rho_{C}$.

Then $\rho_{A}$ and $\rho_{C}$ are both pure states.

###### Proof.

This is a special case of Lemma 29. ∎

Next, we apply the above argument across the entire system. In Fig. 4 (b), the
system is divided into many vertical strips of width $5d$. By repeating the
above argument, we can learn a inverting circuit $V_{i}$ for each shaded
$B_{i}$ region. Note that each $V_{i}$ acts on a width-$7d$ strip around
$B_{i}$ and therefore different $V_{i}$s do not overlap. By combining these
different inverting circuits, overall we have learned a depth-$d$ circuit $V$
such that $V\ket{\psi}=\ket{0}_{B}\otimes\ket{\psi^{\prime}}$ where $B$
denotes the union of $B_{i}$.

Finally, by repeatedly applying Lemma 25, we know that the reduced density
matrix of $V\ket{\psi}$ on each region $A_{i}$ is a pure state. This means
that overall the state can be written as
$V\ket{\psi}=\ket{0}_{B}\otimes(\otimes_{i}\ket{\phi}_{A_{i}})$ for some pure
states $\ket{\phi}_{A_{i}}$.

Now, we have disentangled the state $\ket{\psi}$ into a tensor product of many
1D-like pure states, and the problem of learning $\ket{\psi}$ is reduced to
the following problem:

Problem 1. We are given copies of a state $\ket{\psi_{2}}$ with the promise
that

  1. 1.

it is prepared by a depth-$2d$ circuit (defined on a 2D lattice) acting on
$\ket{0^{n}}$;

  2. 2.

its reduced density matrix on each of the $B_{i}$ regions in Fig. 4 (b) equals
$\outerproduct{0}{0}_{B_{i}}$; in particular, this implies that
$\ket{\psi_{2}}=\ket{0}_{B}\otimes(\otimes_{i}\ket{\phi}_{A_{i}})$ for some
pure states $\ket{\phi}_{A_{i}}$.

The goal is to learn the state $\ket{\psi_{2}}$, and it suffices to learn each
of the individual states $\ket{\phi}_{A_{i}}$.

###  8.3 Learning finite correlated states in 1D

Next we show how to learn a state $\ket{\phi}$ (abbreviating the subscript
$A_{i}$) on a specific region $A_{i}$ that came from Problem 1. Besides the
fact that $\ket{\phi}$ is a pure state, the learning algorithm heavily relies
on the property that $\ket{\phi}$ is part of a larger state that is prepared
by a depth-$2d$ circuit. Note that this does not imply that $\ket{\phi}$
itself can be prepared by a depth-$2d$ circuit acting on $A_{i}$. Instead, we
will use this property to derive useful facts about $\ket{\phi}$, presented as
two different viewpoints. Each of them leads to a learning algorithm that is
similar to the approach in Section 8.1.

Viewpoint 1. By Lemma 24, the state $\ket{\phi}$ is a finite correlated state
with correlation length $\ell=4d$. That is, let
$\sigma=\outerproduct{\phi}{\phi}$ and let $R_{1},R_{2}\subseteq A_{i}$ be two
regions that are separated by distance at least $4d$, then
$\sigma_{R_{1}R_{2}}=\sigma_{R_{1}}\otimes\sigma_{R_{2}}$.

$A_{i}^{L}$$A_{i}$$A_{i}^{R}$ Figure 5: Each of the states on the white
$A_{i}$ regions in Fig. 4 (b) can be viewed as being prepared by a depth-$2d$
circuit acting on $A_{i}$ (white) as well as ancilla qubits $A_{i}^{L}$ and
$A_{i}^{R}$ (blue).

Viewpoint 2. $\ket{\phi}$ can be prepared by a depth-$2d$ circuit acting on
$A_{i}$ as well as some ancilla qubits $A_{i}^{L}$ and $A_{i}^{R}$, shown in
Fig. 5. To see this, recall that $\ket{\phi}$ is part of a state that is
prepared by a depth-$2d$ circuit. Now, imagine that we _undo_ all the gates in
that circuit, except for those in the _backward lightcone_ of $A_{i}$. This
procedure does not affect the state on $A_{i}$, and the resulting circuit
(denote as $W_{i}$) has exactly the same shape as in Fig. 5, where
$A_{i}^{L}$, $A_{i}^{R}$ both has width $2d$. Moreover, since $\ket{\phi}$ is
a pure state, it is disentangled with the ancilla qubits, which means

$W_{i}\ket{0}_{A_{i}^{L}}\ket{0}_{A_{i}}\ket{0}_{A_{i}^{R}}=\ket{\mathrm{junk}}_{A_{i}^{L}}\otimes\ket{\phi}\otimes\ket{\mathrm{junk}^{\prime}}_{A_{i}^{R}}.$
(285)

Clearly, Viewpoint 2 is a much stronger characterization of $\ket{\phi}$ and
derives Viewpoint 1 as a corollary; however, it involves additional ancilla
qubits. In the following, we show that each of these Viewpoints itself is
sufficient to derive a learning algorithm; in particular,

  * •

Using Viewpoint 1, we show that the state $\ket{\phi}$ can be prepared by a
depth-$2^{\mathcal{O}(d^{2})}$ circuit acting on $A_{i}$ (without ancilla),
therefore it can be learned using the techniques in Section 8.1.

  * •

Using Viewpoint 2, we show how to learn a depth-$2d$ circuit $W_{i}$ that
prepares the state $\ket{\phi}$ using ancilla qubits, according to Eq. (285).

Central to both of these results is a technique that allows us to disentangle
a finite correlated state in 1D. For simplicity, below we present this
technique for a 1D system on a line with no width.

$\displaystyle\ket{\phi}$ $\displaystyle=\enspace\leavevmode\hbox
to200.37pt{\vbox to28.85pt{\pgfpicture\makeatletter\hbox{\hskip
0.59999pt\lower-14.42638pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{199.16931pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{85.35828pt}{14.22638pt}\pgfsys@lineto{85.35828pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{113.81104pt}{14.22638pt}\pgfsys@lineto{113.81104pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{38.92914pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{37.99406pt}{5.47743pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\rho_{A}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{152.55893pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$C$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{151.70361pt}{5.47743pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\rho_{C}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{95.54126pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\enspace=\enspace\leavevmode\hbox
to200.37pt{\vbox to49.85pt{\pgfpicture\makeatletter\hbox{\hskip
0.59999pt\lower-15.50377pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{96.7392pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{102.4301pt}{0.0pt}\pgfsys@lineto{199.16931pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{85.35828pt}{11.38092pt}\pgfsys@lineto{85.35828pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{113.81104pt}{11.38092pt}\pgfsys@lineto{113.81104pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{38.92914pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{37.99406pt}{5.47743pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\rho_{A}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{152.55893pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$C$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{151.70361pt}{5.47743pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\rho_{C}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{85.60533pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{102.67715pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{85.35828pt}{34.14322pt}\pgfsys@moveto{85.35828pt}{34.14322pt}\pgfsys@lineto{85.35828pt}{14.22638pt}\pgfsys@lineto{113.81104pt}{14.22638pt}\pgfsys@lineto{113.81104pt}{34.14322pt}\pgfsys@closepath\pgfsys@moveto{113.81104pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{95.62564pt}{20.76814pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$U$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{91.04874pt}{0.0pt}\pgfsys@lineto{91.04874pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{108.12056pt}{0.0pt}\pgfsys@lineto{108.12056pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle=\enspace\leavevmode\hbox to200.37pt{\vbox
to66.92pt{\pgfpicture\makeatletter\hbox{\hskip 0.59999pt\lower-32.57559pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{39.83368pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{45.52458pt}{0.0pt}\pgfsys@lineto{96.7392pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{102.4301pt}{0.0pt}\pgfsys@lineto{153.64471pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}\pgfsys@moveto{159.33562pt}{0.0pt}\pgfsys@lineto{199.16931pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{9.07637pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{65.98189pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{122.8874pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A_{3}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{179.79292pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A_{4}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{37.23573pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{94.14125pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{151.04677pt}{-10.36632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B_{3}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par {}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{28.45276pt}{34.14322pt}\pgfsys@moveto{28.45276pt}{34.14322pt}\pgfsys@lineto{28.45276pt}{14.22638pt}\pgfsys@lineto{56.90552pt}{14.22638pt}\pgfsys@lineto{56.90552pt}{34.14322pt}\pgfsys@closepath\pgfsys@moveto{56.90552pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{37.32013pt}{21.67036pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$U_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@lineto{34.14322pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{51.21504pt}{0.0pt}\pgfsys@lineto{51.21504pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{11.38092pt}\pgfsys@lineto{28.45276pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{56.90552pt}{11.38092pt}\pgfsys@lineto{56.90552pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{85.35828pt}{34.14322pt}\pgfsys@moveto{85.35828pt}{34.14322pt}\pgfsys@lineto{85.35828pt}{14.22638pt}\pgfsys@lineto{113.81104pt}{14.22638pt}\pgfsys@lineto{113.81104pt}{34.14322pt}\pgfsys@closepath\pgfsys@moveto{113.81104pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{94.22565pt}{21.67036pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$U_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{91.04874pt}{0.0pt}\pgfsys@lineto{91.04874pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{108.12056pt}{0.0pt}\pgfsys@lineto{108.12056pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{85.35828pt}{11.38092pt}\pgfsys@lineto{85.35828pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{113.81104pt}{11.38092pt}\pgfsys@lineto{113.81104pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{142.2638pt}{34.14322pt}\pgfsys@moveto{142.2638pt}{34.14322pt}\pgfsys@lineto{142.2638pt}{14.22638pt}\pgfsys@lineto{170.71655pt}{14.22638pt}\pgfsys@lineto{170.71655pt}{34.14322pt}\pgfsys@closepath\pgfsys@moveto{170.71655pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{151.13116pt}{21.67036pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$U_{3}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{147.95425pt}{0.0pt}\pgfsys@lineto{147.95425pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{165.02608pt}{0.0pt}\pgfsys@lineto{165.02608pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{142.2638pt}{11.38092pt}\pgfsys@lineto{142.2638pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setdash{3.0pt,2.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{170.71655pt}{11.38092pt}\pgfsys@lineto{170.71655pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {}{{}}{} {}{}{}{}{{{}{}}}
{}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {} {}{}{} { {{}} {}
{}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}} }}{{}}}
{}\pgfsys@moveto{39.83368pt}{-17.07182pt}\pgfsys@moveto{39.83368pt}{-17.07182pt}\pgfsys@curveto{39.4587pt}{-17.82182pt}{38.58368pt}{-18.32182pt}{37.33368pt}{-18.32182pt}\pgfsys@lineto{22.41684pt}{-18.32182pt}\pgfsys@curveto{21.16684pt}{-18.32182pt}{20.29182pt}{-18.82181pt}{19.91684pt}{-19.57182pt}\pgfsys@curveto{19.54185pt}{-18.82181pt}{18.66684pt}{-18.32182pt}{17.41684pt}{-18.32182pt}\pgfsys@lineto{2.5pt}{-18.32182pt}\pgfsys@curveto{1.25pt}{-18.32182pt}{0.37498pt}{-17.82182pt}{0.0pt}{-17.07182pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{14.68176pt}{-27.43814pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$R_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {}{{}}{}
{}{}{}{}{{{}{}}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {}
{}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}}
}}{{}}}
{}\pgfsys@moveto{96.7392pt}{-17.07182pt}\pgfsys@moveto{96.7392pt}{-17.07182pt}\pgfsys@curveto{96.36421pt}{-17.82182pt}{95.4892pt}{-18.32182pt}{94.2392pt}{-18.32182pt}\pgfsys@lineto{73.6319pt}{-18.32182pt}\pgfsys@curveto{72.3819pt}{-18.32182pt}{71.50688pt}{-18.82181pt}{71.1319pt}{-19.57182pt}\pgfsys@curveto{70.75691pt}{-18.82181pt}{69.8819pt}{-18.32182pt}{68.6319pt}{-18.32182pt}\pgfsys@lineto{48.02458pt}{-18.32182pt}\pgfsys@curveto{46.77458pt}{-18.32182pt}{45.89957pt}{-17.82182pt}{45.52458pt}{-17.07182pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{65.89682pt}{-27.43814pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$R_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {}{{}}{}
{}{}{}{}{{{}{}}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {}
{}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}}
}}{{}}}
{}\pgfsys@moveto{153.64471pt}{-17.07182pt}\pgfsys@moveto{153.64471pt}{-17.07182pt}\pgfsys@curveto{153.26973pt}{-17.82182pt}{152.39471pt}{-18.32182pt}{151.14471pt}{-18.32182pt}\pgfsys@lineto{130.53741pt}{-18.32182pt}\pgfsys@curveto{129.28741pt}{-18.32182pt}{128.4124pt}{-18.82181pt}{128.03741pt}{-19.57182pt}\pgfsys@curveto{127.66243pt}{-18.82181pt}{126.78741pt}{-18.32182pt}{125.53741pt}{-18.32182pt}\pgfsys@lineto{104.9301pt}{-18.32182pt}\pgfsys@curveto{103.6801pt}{-18.32182pt}{102.80508pt}{-17.82182pt}{102.4301pt}{-17.07182pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{122.80234pt}{-27.43814pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$R_{3}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {}{{}}{}
{}{}{}{}{{{}{}}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {}
{}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}}
}}{{}}}
{}\pgfsys@moveto{199.16931pt}{-17.07182pt}\pgfsys@moveto{199.16931pt}{-17.07182pt}\pgfsys@curveto{198.79433pt}{-17.82182pt}{197.91931pt}{-18.32182pt}{196.66931pt}{-18.32182pt}\pgfsys@lineto{181.75247pt}{-18.32182pt}\pgfsys@curveto{180.50247pt}{-18.32182pt}{179.62746pt}{-18.82181pt}{179.25247pt}{-19.57182pt}\pgfsys@curveto{178.87749pt}{-18.82181pt}{178.00247pt}{-18.32182pt}{176.75247pt}{-18.32182pt}\pgfsys@lineto{161.83562pt}{-18.32182pt}\pgfsys@curveto{160.58562pt}{-18.32182pt}{159.7106pt}{-17.82182pt}{159.33562pt}{-17.07182pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{174.0174pt}{-27.43814pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$R_{4}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ Figure 6:
Disentangling a finite correlated state in 1D.

######  Lemma 26 (Disentangling finite correlated states in 1D).

Let $\ket{\phi}$ be a state defined on a line with correlation length $\ell$,
that is, every two regions $R_{1}$, $R_{2}$ that are separated by distance at
least $\ell$ have zero mutual information, i.e.
$\rho_{R_{1}R_{2}}=\rho_{R_{1}}\otimes\rho_{R_{2}}$, where
$\rho=\outerproduct{\phi}{\phi}$. Divide the 1D line into contiguous regions
of size $\ell$, denote as $A_{1},B_{1},A_{2},B_{2},\dots,B_{L-1},A_{L}$ (Fig.
6). Then for each $i$ there exists a unitary $U_{i}$ acting on the $B_{i}$
region, such that $\prod_{i=1}^{L-1}U_{i}\ket{\phi}$ is a tensor product of
$L$ pure states.

###### Proof.

We start with three subsystems $A,B,C$ (first line of Fig. 6), where $B$ has
size $\ell$. Then we have

$\rank(\rho_{B})=\rank(\rho_{AC})=\rank(\rho_{A}\otimes\rho_{C})=\rank(\rho_{A})\cdot\rank(\rho_{C})\leq\dim(B).$
(286)

Purifying the state $\rho_{A}$ ($\rho_{C}$) requires an ancilla system with
dimension $\rank(\rho_{A})$ ($\rank(\rho_{C})$). Therefore we can partition
$B$ into two systems $B_{1}$, $B_{2}$, such that there exists pure states
$\ket{\phi_{1}}_{AB_{1}}$ and $\ket{\phi_{2}}_{B_{2}C}$, such that
$\ket{\phi_{1}}_{AB_{1}}$ is a purification of $\rho_{A}$, and
$\ket{\phi_{2}}_{B_{2}C}$ is a purification of $\rho_{C}$. This implies that
$\ket{\phi_{1}}_{AB_{1}}\otimes\ket{\phi_{2}}_{B_{2}C}$ is a purification of
$\rho_{AC}$. Since $\ket{\phi}_{ABC}$ is also a purification of $\rho_{AC}$,
by Uhlmann’s theorem there exists a unitary $U_{B}$ such that
$\ket{\phi}_{ABC}=U_{B}\ket{\phi_{1}}_{AB_{1}}\otimes\ket{\phi_{2}}_{B_{2}C}$.

Applying this argument independently at different $B_{i}$ regions (bottom line
of Fig. 6), we have that for each $i=1,2,\dots,L-1$, there exists a partition
of the system $B_{i}$ as two systems $B_{i}^{L}$ and $B_{i}^{R}$, as well as a
unitary $U_{i}$ acting on $B_{i}=B_{i}^{L}\cup B_{i}^{R}$, such that

$\ket{\phi}=U_{i}\ket{\phi_{1}}_{A_{1}\dots
B_{i}^{L}}\otimes\ket{\phi_{2}}_{B_{i}^{R}A_{i+1}\cdots A_{L}},$ (287)

or equivalently, $U_{i}^{\dagger}\ket{\phi}=\ket{\phi_{1}}_{A_{1}\dots
B_{i}^{L}}\otimes\ket{\phi_{2}}_{B_{i}^{R}A_{i+1}\cdots A_{L}}$, for some pure
states $\ket{\phi_{1}}$ and $\ket{\phi_{2}}$. Next, we relabel the systems
according to

$R_{i}:=B_{i-1}^{R}\cup A_{i}\cup B_{i}^{L}.$ (288)

Intuitively, after applying all $U_{i}^{\dagger}$s, the system must be
disentangled across all the $R_{i}$ regions. To prove this we use a simple
argument based on the strong subadditivity of quantum entropy (Lemma 27).

Let
$\sigma:=\left(\prod_{i=1}^{L-1}U_{i}^{\dagger}\right)\outerproduct{\phi}{\phi}\left(\prod_{i=1}^{L-1}U_{i}\right)$
be the final (pure) state. Fix some $i$, our goal is to prove that
$\sigma_{R_{i}}$ is pure, i.e., $S(\sigma_{R_{i}})=0$. The strong
subadditivity of quantum entropy gives

$S(\sigma_{R_{i}})\leq S(\sigma_{R_{1}\dots R_{i}})+S(\sigma_{R_{i}\dots
R_{L}})-S(\sigma)=S(\sigma_{R_{1}\dots R_{i}})+S(\sigma_{R_{i}\dots R_{L}}).$
(289)

Note that when calculating $S(\sigma_{R_{1}\dots R_{i}})$ we can _undo_ all
the unitaries $U_{j}^{\dagger}$ for $j<i$ due to the invariance of entropy
under unitary. Then $S(\sigma_{R_{1}\dots R_{i}})=0$ immediately follows from
Eq. (287), and a similar argument shows $S(\sigma_{R_{i}\dots R_{L}})=0$,
which concludes the proof. ∎

######  Lemma 27 (Strong subadditivity of quantum entropy [107]).

Let $\rho$ be a mixed state defined on three systems $A,B,C$. Let
$S(\rho):=-\Tr(\rho\log\rho)$ be the von Neumann entropy. Then we have

$S(\rho_{ABC})+S(\rho_{B})\leq S(\rho_{AB})+S(\rho_{BC}).$ (290)

Learning under Viewpoint 1. A corollary of Lemma 26 is that any finite
correlated state in 1D can be prepared by a low-depth circuit, because each of
the small pure state on the $R_{i}$ regions in the bottom line of Fig. 6 can
be prepared by a local unitary acting on $\mathcal{O}(\ell)$ qubits. Applying
this argument to the state $\ket{\phi}_{A_{i}}$ shown in Fig. 5, we conclude
that it can be prepared by two layers of unitaries acting on
$\mathcal{O}(d^{2})$ qubits, acting on the $A_{i}$ region only. This implies
that the state $\ket{\phi}_{A_{i}}$ can be prepared by a
depth-$2^{\mathcal{O}(d^{2})}$ circuit acting on $A_{i}$, and thus can be
learned by applying the argument in Section 8.1.

Learning under Viewpoint 2. The main drawback of the above argument is that
the learned circuit depth has an exponential blowup. To reduce this blowup we
use additional structure of the state $\ket{\phi}_{A_{i}}$, described in
Viewpoint 2 and Fig. 5. Note that there is a key difference between learning
the state $\ket{\phi}_{A_{i}}$ and learning 1D states discussed in Section
8.1. Here, while the state $\ket{\phi}_{A_{i}}$ has a low-depth property shown
in Fig. 5, this property relies on ancilla qubits (the $\ket{\mathrm{junk}}$
states in Eq. (285)) that _we do not have access to_. Therefore we cannot
directly apply the techniques in Section 8.1, which requires access to all
qubits prepared by the low-depth circuit.

The main idea is to learn a mixed state $\rho$ that is _locally consistent_
with the state $\outerproduct{\phi}{\phi}$, i.e., they have the same local
reduced density matrices, and then show that this forces the two states to be
globally the same.

$A_{i}^{L}$$A_{i}$$A_{i}^{R}$$4d$$12d$ Figure 7: Learning a quantum state
generated by a depth-$2d$ circuit with ancilla.

The argument is illustrated in Fig. 7, where we learn to locally _prepare_ the
state instead of _invert_ the state. Consider the state $\ket{\phi}$ on the
$A_{i}$ region shown in Fig. 7, and suppose we have learned its reduced
density matrix $\rho_{\mathrm{blue}}$ on the solid blue region. Due to the
fact that $\ket{\phi}$ is prepared by a depth-$2d$ circuit acting on
$A_{i}^{L},A_{i},A_{i}^{R}$, we know that there exists a depth-$2d$ circuit
acting on the dotted blue region that prepares $\rho_{\mathrm{blue}}$ (the
circuit looks like a small piece of Fig. 5), by undoing all the gates except
for those in the backward lightcone of the solid blue region. We can perform a
brute force search over all depth-$2d$ circuits acting on the dotted blue
region, and for each of them we can test whether it prepares
$\rho_{\mathrm{blue}}$. In this way we obtain a list of depth-$2d$ circuits
acting on the dotted blue region that prepares $\rho_{\mathrm{blue}}$.

By repeating the above procedure we can obtain a list of local preparation
circuits for each of the solid colored regions. A key point here is that the
neighboring colored regions overlap by distance $4d$. Moreover, the local
preparation circuits for the blue and green regions do not overlap, since the
red region is sufficiently big. This enables us to solve a constraint
satisfaction problem of the same nature as in Section 8.1, where we can choose
a local preparation circuit for each region, such that neighboring circuits
are consistent and can be merged together. Overall we have learned a
depth-$2d$ circuit $W$ acting on $A_{i}^{L},A_{i},A_{i}^{R}$, that
simultaneously prepares all the local reduced density matrices.

Let
$\rho:=\Tr_{A_{i}^{L}A_{i}^{R}}(W\outerproduct{0}{0}_{A_{i}^{L}A_{i}A_{i}^{R}}W^{\dagger})$
be the learned density matrix on $A_{i}$. At this point we know that $\rho$
and $\outerproduct{\phi}{\phi}$ are locally the same on the solid blue, red,
and green regions (and so on), but this does not directly imply that
$\rho=\outerproduct{\phi}{\phi}$. For example, a Haar random pure state and
the maximally mixed state are locally very close but globally very far. Next,
we show that the finite correlation property forces $\rho$ and
$\outerproduct{\phi}{\phi}$ to be globally equal.

######  Lemma 28 (Local consistency implies global consistency).

Let $\ket{\psi}$ be a state defined on a 1D line with correlation length
$\ell$ and let $\sigma=\outerproduct{\psi}{\psi}$. Suppose the system is
partitioned into contiguous regions $A_{1},\dots,A_{L}$ where
$|A_{i}|\geq\ell$. Suppose $\rho$ is a mixed state that satisfies
$\rho_{A_{i}A_{i+1}}=\sigma_{A_{i}A_{i+1}}$ for all $i$, then $\rho=\sigma$.

###### Proof.

We show this for 3 subsystems; generalizing to more subsystems is
straightforward. Let $\rho$ be a mixed state satisfying
$\rho_{A_{1}A_{2}}=\sigma_{A_{1}A_{2}}$ and
$\rho_{A_{2}A_{3}}=\sigma_{A_{2}A_{3}}$. Following the proof of Lemma 26,
there exists a unitary $U$ acting on $A_{2}$ such that

$U_{A_{2}}\ket{\psi}_{A_{1}A_{2}A_{3}}=\ket{\phi_{1}}_{A_{1}A_{21}}\otimes\ket{\phi_{2}}_{A_{22}A_{3}},$
(291)

where $A_{21},A_{22}$ is a partition of $A_{2}$, and
$\ket{\phi_{1}}_{A_{1}A_{21}}$, $\ket{\phi_{2}}_{A_{22}A_{3}}$ are some pure
states. Equivalently, we have

$U_{A_{2}}\sigma
U_{A_{2}}^{\dagger}=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}\otimes\outerproduct{\phi_{2}}{\phi_{2}}_{A_{22}A_{3}}.$
(292)

Let $\tau:=U_{A_{2}}\rho U_{A_{2}}^{\dagger}$, we will show that
$\tau=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}\otimes\outerproduct{\phi_{2}}{\phi_{2}}_{A_{22}A_{3}}$,
which implies $\rho=\sigma$.

First, taking the partial trace over $A_{3}$ on both sides of Eq. (292), we
have

$U\sigma_{A_{1}A_{2}}U^{\dagger}=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}\otimes\Tr_{A_{3}}\outerproduct{\phi_{2}}{\phi_{2}}.$
(293)

Then, notice that

$\tau_{A_{1}A_{2}}=U\rho_{A_{1}A_{2}}U^{\dagger}=U\sigma_{A_{1}A_{2}}U^{\dagger}=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}\otimes\Tr_{A_{3}}\outerproduct{\phi_{2}}{\phi_{2}}.$
(294)

Tracing out $A_{22}$ on both sides, we have
$\tau_{A_{1}A_{21}}=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}$;
similarly,
$\tau_{A_{22}A_{3}}=\outerproduct{\phi_{2}}{\phi_{2}}_{A_{22}A_{3}}$. Since
$\tau_{A_{1}A_{21}}$ and $\tau_{A_{22}A_{3}}$ are both pure states, this
implies that the global state $\tau$ is a tensor product

$\tau=\tau_{A_{1}A_{21}}\otimes\tau_{A_{22}A_{3}}=\outerproduct{\phi_{1}}{\phi_{1}}_{A_{1}A_{21}}\otimes\outerproduct{\phi_{2}}{\phi_{2}}_{A_{22}A_{3}}.$
(295)

Thus we have $\tau=U\sigma U^{\dagger}$, which implies $\rho=\sigma$. ∎

Summary of our progress so far. So far we have developed all technical
ingredients for learning a quantum state $\ket{\psi}=U\ket{0^{n}}$, under the
simplified setting that $U$ is a depth $d=\mathcal{O}(1)$ circuit acting on a
2D lattice, and each gate in $U$ is from a constant size gate set.

Note that all the above arguments can be viewed as first learning the local
reduced density matrices of $\ket{\psi}$ followed by classically
reconstructing the circuit. As we have discussed before in Section 8.1, a
reduced density matrix of constant size can be learned _exactly_ as it only
has a constant number of choices. In the disentangling step shown in Fig. 4,
we can learn $\mathcal{O}(n)$ reduced density matrices on the dotted regions
of size $\mathcal{O}(d^{2})$, and then classically reconstruct a depth-$d$
circuit $V$ in time $\mathcal{O}(n)$, such that
$V\ket{\psi}=\ket{0}_{B}\otimes(\otimes_{i}\ket{\phi}_{A_{i}})$ where the pure
states $\ket{\phi}_{A_{i}}$ live on the white regions of Fig. 4 (b).

Proof of second claim of Theorem 9. Next, we start with Viewpoint 2. As shown
in Fig. 7, learning a state $\ket{\phi}_{A_{i}}$ requires learning its reduced
density matrices of size $5d\times 16d$. This can be achieved by
experimentally applying $V$ to $\ket{\psi}$ and then learning the reduced
density matrices. Equivalently, say we want to learn the reduced density
matrix of $\ket{\phi}_{A_{i}}$ on a region $M$ of size $5d\times 16d$, then it
suffices to learn a reduced density matrix of $\ket{\psi}$ of size $7d\times
18d$ on a region surrounding $M$, then _classically_ apply the gates of $V$
within the backward lightcone of $M$, and then classically trace out the
qubits outside $M$. In other words, the reduced density matrices of
$\ket{\phi}_{A_{i}}$ can be simulated by slightly larger reduced density
matrices of $\ket{\psi}$. Using these reduced density matrices, for each $i$
we can learn a depth-$2d$ circuit $W_{i}$ such that

$W_{i}\ket{0}_{A_{i}^{L}A_{i}A_{i}^{R}}=\ket{\phi}_{A_{i}}\otimes\ket{\mathrm{junk}}_{A_{i}^{L}A_{i}^{R}},$
(296)

which takes total time $\mathcal{O}(n)$. The entire process requires
$\mathcal{O}(n)$ reduced density matrices of $\ket{\psi}$ of size
$\mathcal{O}(d^{2})$, which can be learned exactly with probability at least
$1-\delta$, using a randomized measurement dataset of size
$N=\mathcal{O}(\log(n/\delta))$.

The state $\ket{\psi}$ can be prepared as follows:

  1. 1.

Initialize registers $A_{i},B_{i},A_{i}^{L},A_{i}^{R}$ in the state $\ket{0}$.
Let $A=\cup_{i}A_{i}$ and $B=\cup_{i}B_{i}$.

  2. 2.

For each $i$, apply the depth-$2d$ circuit $W_{i}$ to
$A_{i}^{L}A_{i}A_{i}^{R}$.

  3. 3.

Apply the depth-$d$ circuit $V^{\dagger}$ to $AB$, and the state $\ket{\psi}$
lives on $AB$.

Overall the learned circuit has depth $3d$ and can be implemented on an
extended 2D lattice, where the qubits in $A_{i}$ can interact with its ancilla
qubits $A_{i}^{L},A_{i}^{R}$ as well as neighboring $B_{i}$ regions.

In Fig. 7 we have chosen the width of $A_{i}$ to be $5d$. Note that the width
of $A_{i}^{L}$ and $A_{i}^{R}$ are both $2d$, regardless of the width of
$A_{i}$. In fact we could have chosen the width of $A_{i}$ to be $Cd$ for some
large constant $C$, and the number of ancilla qubits is at most $n/(Cd)\cdot
4d=\frac{4}{C}n$, which can be made arbitrarily small.

Proof of third claim of Theorem 9. Using Viewpoint 1, the state
$\ket{\phi}_{A_{i}}$ can be prepared by a depth-$2^{\mathcal{O}(d^{2})}$
circuit acting on $A_{i}$, and thus can be learned by applying the argument in
Section 8.1. Let $\ket{\phi}_{A_{i}}=W\ket{0}_{A_{i}}$ for some
depth-$2^{\mathcal{O}(d^{2})}$ circuit $W$ acting on $A_{i}$. A technical
issue here is that we no longer have the guarantee that $W$ consists of gates
from a finite gate set as in $U$, because the existence of $W$ comes from the
disentangling argument in Lemma 26, instead of coming from the original
circuit $U$ as in Viewpoint 2. Below we discuss how to find this circuit $W$.

Let $d^{\prime}=2^{\mathcal{O}(d^{2})}$ be the circuit depth of $W$. Following
Section 8.1, we can learn reduced density matrices of
$\sigma:=\outerproduct{\phi}{\phi}_{A_{i}}$ of size $5d\times 5d^{\prime}$
(which can be done exactly, as discussed above) and then classically find
local inversions for regions of size $5d\times 3d^{\prime}$. Following Fig. 3,
let $A$ be a region of size $5d\times 3d^{\prime}$, and let $AA_{1}$ be the
lightcone of $A$ with size $5d\times 4d^{\prime}$. Then there is a
depth-$d^{\prime}$ circuit $W_{AA_{1}}$ acting on $AA_{1}$ such that

$\Tr_{A_{1}}\left(W_{AA_{1}}\sigma_{AA_{1}}W_{AA_{1}}^{\dagger}\right)=\outerproduct{0}{0}_{A}.$
(297)

To find the local inversion $W_{AA_{1}}$ we use an $\varepsilon_{0}$-net over
depth-$d^{\prime}$ circuits acting on $AA_{1}$, denoted as
$\mathcal{N}_{\varepsilon_{0}}(AA_{1})$ (see Definition 18 and Lemma 19),
which has size at most

$S=\left(\frac{d^{\prime 3}}{\varepsilon_{0}}\right)^{\mathcal{O}(d^{\prime
3})}.$ (298)

By definition, there exists
$\hat{W}_{AA_{1}}\in\mathcal{N}_{\varepsilon_{0}}(AA_{1})$ such that
$\|\hat{W}_{AA_{1}}-W_{AA_{1}}\|_{\infty}\leq\varepsilon_{0}$, which gives

$\expectationvalue{\Tr_{A_{1}}\left(\hat{W}_{AA_{1}}\sigma_{AA_{1}}\hat{W}_{AA_{1}}^{\dagger}\right)}{0_{A}}\geq
1-2\varepsilon_{0}.$ (299)

By enumerating over every element in $\mathcal{N}_{\varepsilon_{0}}(AA_{1})$,
we can find a list of circuits which satisfy the above equation. Following the
argument in Section 8.1, we repeat the same procedure for each local region
and merge the local circuits into a global depth-$d^{\prime}$ circuit
$\hat{W}_{i}$, which approximately inverts each local region up to
$1-2\varepsilon_{0}$ fidelity. By union bound, we have

$\left|\bra{0_{A_{i}}}\hat{W}_{i}\ket{\phi}_{A_{i}}\right|^{2}\geq
1-2\sqrt{n}\varepsilon_{0}.$ (300)

After learning each region $A_{i}$, the state $\ket{\psi}$ can be
approximately prepared as follows:

  1. 1.

Initialize registers $A_{i},B_{i}$ in the state $\ket{0}$. Let
$A=\cup_{i}A_{i}$ and $B=\cup_{i}B_{i}$.

  2. 2.

For each $i$, apply the depth-$d^{\prime}$ circuit $\hat{W}_{i}^{\dagger}$ to
$A_{i}$.

  3. 3.

Apply the depth-$d$ circuit $V^{\dagger}$ to $AB$, and the state on $AB$,
which is
$\ket{\hat{\psi}}=V^{\dagger}(\otimes_{i}\hat{W}_{i}^{\dagger})\ket{0^{n}}$,
approximately equals to $\ket{\psi}$.

We bound the approximation error as follows.

$\left|\braket{\hat{\psi}}{\psi}\right|^{2}=\left|\bra{0^{n}}(\otimes_{i}\hat{W}_{i})V\ket{\psi}\right|^{2}=\prod_{i}\left|\bra{0_{A_{i}}}\hat{W}_{i}\ket{\phi}_{A_{i}}\right|^{2}\geq
1-2n\varepsilon_{0}.$ (301)

Therefore to achieve $1-\varepsilon$ fidelity it suffices to choose
$\varepsilon_{0}=\frac{\varepsilon}{2n}$, which gives total running time
$n\cdot S=(n/\varepsilon)^{\mathcal{O}(1)}$.

###  8.4 Robustness to imprecision

In the previous sections we have been focusing on a finite gateset, which
allows us to learn reduced density matrices exactly, and therefore the
disentangling procedure in Fig. 4 can be performed exactly. However, it’s not
clear that this argument still works for general $\mathrm{SU}(4)$ gates,
because in this case each step can only be performed _approximately_. In
particular, we can only approximately disentangle the state using the
procedure in Fig. 4, and learning the remaining 1D states poses new technical
challenges as they are no longer pure.

In this section we address this issue. In the following we first outline the
argument and develop key technical lemmas, before going into the full proof of
the first claim in Theorem 9.

We start with the disentangling step in Fig. 4. Here, instead of exhaustively
enumerating small circuits acting on local regions, we can only enumerate over
an $\varepsilon$-net of the circuit. Therefore, we are only able to find
circuits that approximately invert each $B_{i}$ region shown in Fig. 4 (b).
This means that after the disentangling step, the reduced density matrix on
$B$ will be _close_ to $\outerproduct{0}{0}_{B}$, instead of being _exactly
equal_ to $\outerproduct{0}{0}_{B}$.

Now the question is what happens to the remaining $A_{i}$ regions. Note that
the state is still in tensor product across different $A_{i}$ regions due to
the finite correlation length property, but the reduced density matrices on
each $A_{i}$ region will not be pure. The following lemma shows that these
states are _approximately pure_.

######  Lemma 29.

Let $\rho_{A_{1}A_{2}\dots A_{L}B}$ be a pure state such that the following
two properties hold:

  1. 1.

$\expectationvalue{\rho_{B}}{0_{B}}\geq 1-\varepsilon$,

  2. 2.

$\rho_{A_{1}A_{2}\dots A_{L}}=\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{L}}$.

Then for each $i=1,\dots,L$ there exists a pure state $\ket{\phi}_{A_{i}}$
such that $\expectationvalue{\rho_{A_{i}}}{\phi_{A_{i}}}\geq 1-\varepsilon$.

###### Proof.

Consider the operator norm
$\|\rho\|_{\infty}:=\lambda_{\max}(\rho)=\max_{\ket{\psi}}\expectationvalue{\rho}{\psi}$.
Condition 1 gives $\|\rho_{B}\|_{\infty}\geq 1-\varepsilon$. Using condition 2
we have

$\|\rho_{B}\|_{\infty}=\|\rho_{A_{1}\dots
A_{L}}\|_{\infty}=\|\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{L}}\|_{\infty}=\prod_{i=1}^{L}\|\rho_{A_{i}}\|_{\infty}\geq
1-\varepsilon,$ (302)

which implies that $\lambda_{\max}(\rho_{A_{i}})\geq 1-\varepsilon$ for any
$i$. ∎

Next, we discuss how to learn these states $\\{\rho_{A_{i}}\\}$ that are
approximately pure. Again, we still have the property that each $\rho_{A_{i}}$
is a 1D-like state with finite correlation length. However, our previous
techniques developed in Section 8.3 only work for _exactly_ pure states. We
develop new techniques by examining the robustness of the key technical lemma
developed in Section 8.3, Lemma 26.

There are two key ingredients in the proof of Lemma 26:

  1. 1.

The use of Uhlmann’s theorem to prove the existence of a local disentangling
unitary;

  2. 2.

The use to entropy inequalities (in particular, strong subadditivity) to prove
that the state is disentangled into many local pieces after applying Uhlmann’s
unitaries across the entire system.

Fortunately, both ingredients are robust. First, Uhlmann’s theorem says that
if two mixed states are close, then there exists a unitary (acting on the
purifying system) that approximately maps between their purifications. Second,
entropy inequalities are robust, thanks to the continuity of entropy given
below.

######  Lemma 30 (Fannes–Audenaert inequality).

Let $\rho$, $\sigma$ be two $n$-qubit density matrices, and let
$\varepsilon:=\frac{1}{2}\|\rho-\sigma\|_{1}$. Then

$\left|S(\rho)-S(\sigma)\right|\leq n\varepsilon+h(\varepsilon),$ (303)

where $h(\cdot)$ is the binary entropy function and can be upper bounded as
$h(\varepsilon)\leq 2\sqrt{\varepsilon}$.

We formalize the above intuitions as the following main technical lemma, which
is a robust version of Lemma 28.

######  Lemma 31.

Let $\rho$ be an $n$-qubit mixed state defined on systems $A_{1},\dots,A_{L}$,
with the following properties:

  1. 1.

there exists an $n$-qubit pure state $\ket{\psi}$, such that
$\expectationvalue{\rho}{\psi}\geq 1-\varepsilon$.

  2. 2.

for any $i=2,3,\dots,L-1$, it holds that $I(A_{1}\cdots A_{i-1}:A_{i+1}\cdots
A_{L})_{\rho}=0$.

For simplicity we assume that $L$ is odd. Let $\sigma$ be another $n$-qubit
mixed state that satisfies

$\frac{1}{2}\|\sigma_{A_{2i}A_{2i+1}A_{2i+2}}-\rho_{A_{2i}A_{2i+1}A_{2i+2}}\|_{1}\leq\delta,\quad\forall
i=0,1,\dots,(L-1)/2,$ (304)

Then

$\frac{1}{2}\left\|\sigma-\rho\right\|_{1}\leq
13n\varepsilon^{1/16}+4n\delta^{1/4}.$ (305)

###### Proof.

The above condition says that $\rho$ and $\sigma$ are close on local regions
$A_{1}A_{2},A_{2}A_{3}A_{4},A_{4}A_{5}A_{6},\dots,A_{L-1}A_{L}$. The goal is
to prove that they are globally close.

Let $\tau:=\outerproduct{\psi}{\psi}$ denote the density matrix of
$\ket{\psi}$. For any $j\in\\{1,2,\dots,(L-1)/2\\}$, define three regions
$L^{(j)}:=A_{\leq 2j-1}$, $M^{(j)}:=A_{2j}$, $R^{(j)}:=A_{\geq 2j+1}$ (the
superscript $(j)$ is abbreviated when there is no confusion).

Note that for any subsystem $W$, we have

$\frac{1}{2}\|\tau_{W}-\rho_{W}\|_{1}\leq\frac{1}{2}\|\tau-\rho\|_{1}\leq\sqrt{1-\expectationvalue{\rho}{\psi}}\leq\sqrt{\varepsilon}.$
(306)

Therefore,

$\displaystyle\|\tau_{LR}-\tau_{L}\otimes\tau_{R}\|_{1}$
$\displaystyle\leq\|\tau_{LR}-\rho_{LR}\|_{1}+\|\rho_{LR}-\rho_{L}\otimes\rho_{R}\|_{1}+\|\rho_{L}\otimes\rho_{R}-\tau_{L}\otimes\tau_{R}\|_{1}$
(307)
$\displaystyle\leq\|\tau_{LR}-\rho_{LR}\|_{1}+\|\rho_{L}-\tau_{L}\|_{1}+\|\rho_{R}-\tau_{R}\|_{1}$
$\displaystyle\leq\varepsilon_{1}$

where we let $\varepsilon_{1}:=6\sqrt{\varepsilon}$. Then, the relationship
between fidelity and trace distance implies that

$F(\tau_{LR},\tau_{L}\otimes\tau_{R})\geq
1-\|\tau_{LR}-\tau_{L}\otimes\tau_{R}\|_{1}\geq 1-\varepsilon_{1}.$ (308)

Let $\ket{\phi_{1}}_{LM_{1}^{(j)}}$ be a purification of $\tau_{L}$, and let
$\ket{\phi_{2}}_{M_{2}^{(j)}R}$ be a purification of $\tau_{R}$. Note that
$\dim(M_{1}^{(j)})\leq\dim(L)$ and $\dim(M_{2}^{(j)})\leq\dim(R)$. Let
$M^{\prime(j)}$ be an ancilla space with dimension
$\dim(M_{1}^{(j)})\dim(M_{2}^{(j)})/\dim(M^{(j)})$. Here $M^{\prime(j)}$ is
needed in case $M^{(j)}$ is smaller than $M_{1}^{(j)}M_{2}^{(j)}$. Now,
$\ket{\psi}_{LMR}\ket{0}_{M^{\prime(j)}}$ is a purification of the state
$\tau_{LR}$, while
$\ket{\phi_{1}}_{LM_{1}^{(j)}}\otimes\ket{\phi_{2}}_{M_{2}^{(j)}R}$ is a
purification of the state $\tau_{L}\otimes\tau_{R}$, and they have the same
dimension. Then by Uhlmann’s theorem, there exists a unitary
$U^{(j)}:M^{(j)}M^{\prime(j)}\to M_{1}^{(j)}M_{2}^{(j)}$, such that

$U^{(j)}_{M^{(j)}M^{\prime(j)}}\ket{\psi}_{LM^{(j)}R}\ket{0}_{M^{\prime(j)}}\approx_{\varepsilon_{1}}\ket{\phi_{1}}_{LM_{1}^{(j)}}\otimes\ket{\phi_{2}}_{M_{2}^{(j)}R}.$
(309)

Here, $\ket{u}\approx_{\varepsilon}\ket{v}$ means $|\braket{u}{v}|^{2}\geq
1-\varepsilon$.

The above argument shows the existence of a unitary $U^{(j)}$ acting on
$M^{(j)}=A_{2j}$ (as well as an ancilla system $M^{\prime(j)}$), that
approximately disentangles the state $\ket{\psi}$ into a tensor product
between $LM_{1}^{(j)}$ and $M_{2}^{(j)}R$, where $M_{1}^{(j)}$, $M_{2}^{(j)}$
are ancilla systems associated with $A_{2j}$. We apply all such unitaries
$U^{(j)}$ ($j\in\\{1,2,\dots,(L-1)/2\\}$) to $\ket{\psi}$, and obtain

$\eta:=\left(\prod_{j=1}^{(L-1)/2}U^{(j)}\right)\outerproduct{\psi}{\psi}\otimes\outerproduct{0}{0}_{M^{\prime}}\left(\prod_{j=1}^{(L-1)/2}U^{(j){\dagger}}\right),$
(310)

where $M^{\prime}$ represents the union of all $M^{\prime(j)}$. Note that
$\eta$ supports on $A_{1},A_{3},A_{5},\dots,A_{L}$ as well as
$M_{1}^{(j)},M_{2}^{(j)}$ for $j\in\\{1,2,\dots,(L-1)/2\\}$. Now, we relabel
the systems according to

$B_{j}:=M_{2}^{(j-1)}\cup A_{2j-1}\cup M_{1}^{(j)},\quad
j\in\\{1,2,\dots,(L+1)/2\\},$ (311)

and the state $\eta$ supports on $B_{j}$, $j\in\\{1,2,\dots,(L+1)/2\\}$, and
we want to prove that it is approximately a tensor product across all $B_{j}$
regions via upper bounding the relative entropy

$D(\eta||\otimes_{j}\eta_{B_{j}})=\sum_{j}S(\eta_{B_{j}})-S(\eta)=\sum_{j}S(\eta_{B_{j}}).$
(312)

By the strong subadditivity of quantum entropy,

$S(\eta_{B_{j}})\leq S(\eta_{B_{\leq j}})+S(\eta_{B_{\geq
j}})-S(\eta)=S(\eta_{B_{\leq j}})+S(\eta_{B_{\geq j}}).$ (313)

Focusing on the entropy of $S(\eta_{B_{\leq j}})$, we can ignore the unitaries
that are applied on regions other than $A_{2j}$. Note that Eq. (309) implies
that

$\frac{1}{2}\left\|\Tr_{M_{2}^{(j)}R}(U^{(j)}\outerproduct{\psi}{\psi}\otimes\outerproduct{0}{0}_{M^{\prime(j)}}U^{(j){\dagger}})-\outerproduct{\phi_{1}}{\phi_{1}}_{LM_{1}^{(j)}}\right\|_{1}\leq\sqrt{\varepsilon_{1}}.$
(314)

Therefore by the Fannes-Audenaert inequality,

$S(\eta_{B_{\leq
j}})=S(\Tr_{M_{2}^{(j)}R}(U^{(j)}\outerproduct{\psi}{\psi}\otimes\outerproduct{0}{0}_{M^{\prime(j)}}U^{(j){\dagger}}))\leq
2|L|\sqrt{\varepsilon_{1}}+2\varepsilon_{1}^{1/4}\leq
2n\sqrt{\varepsilon_{1}}+2\varepsilon_{1}^{1/4}.$ (315)

A similar argument holds for $S(\eta_{B_{\geq j}})$. Therefore we have

$S(\eta_{B_{j}})\leq
4n\sqrt{\varepsilon_{1}}+4\varepsilon_{1}^{1/4},\quad\forall
j\in\\{1,2,\dots,(L+1)/2\\}.$ (316)

Let

$\omega:=\left(\prod_{j=1}^{(L-1)/2}U^{(j)}\right)\sigma\otimes\outerproduct{0}{0}_{M^{\prime}}\left(\prod_{j=1}^{(L-1)/2}U^{(j){\dagger}}\right),$
(317)

then
$\left\|\sigma-\outerproduct{\psi}{\psi}\right\|_{1}=\left\|\omega-\eta\right\|_{1}$.
Note that for any $j$, $\eta_{B_{j}}$ only depends on the reduced density
matrix $\tau_{A_{2j-2}A_{2j-1}A_{2j}}$; similarly, $\omega_{B_{j}}$ only
depends on the reduced density matrix $\sigma_{A_{2j-2}A_{2j-1}A_{2j}}$.
Therefore,

$\displaystyle\left\|\omega_{B_{j}}-\eta_{B_{j}}\right\|_{1}$
$\displaystyle\leq\left\|\sigma_{A_{2j-2}A_{2j-1}A_{2j}}-\tau_{A_{2j-2}A_{2j-1}A_{2j}}\right\|_{1}$
(318)
$\displaystyle\leq\left\|\sigma_{A_{2j-2}A_{2j-1}A_{2j}}-\rho_{A_{2j-2}A_{2j-1}A_{2j}}\right\|_{1}+\left\|\rho_{A_{2j-2}A_{2j-1}A_{2j}}-\tau_{A_{2j-2}A_{2j-1}A_{2j}}\right\|_{1}$
$\displaystyle\leq 2\delta+2\sqrt{\varepsilon}.$

Note that $|B_{j}|\leq 3n$, by the Fannes-Audenaert inequality,

$S(\omega_{B_{j}})\leq
S(\eta_{B_{j}})+3n(\delta+\sqrt{\varepsilon})+2\sqrt{\delta+\sqrt{\varepsilon}}.$
(319)

This implies that

$\displaystyle D(\omega||\otimes_{j}\omega_{B_{j}})$
$\displaystyle=\sum_{j}S(\omega_{B_{j}})-S(\omega)$ (320)
$\displaystyle\leq\sum_{j}S(\omega_{B_{j}})$
$\displaystyle\leq\sum_{j}S(\eta_{B_{j}})+3n^{2}(\delta+\sqrt{\varepsilon})+2n\sqrt{\delta+\sqrt{\varepsilon}}.$

Then

$\displaystyle\left\|\sigma-\rho\right\|_{1}$
$\displaystyle\leq\left\|\sigma-\tau\right\|_{1}+\left\|\tau-\rho\right\|_{1}$
(321) $\displaystyle\leq\left\|\omega-\eta\right\|_{1}+2\sqrt{\varepsilon}$
$\displaystyle\leq\left\|\omega-\otimes_{j}\omega_{B_{j}}\right\|_{1}+\left\|\otimes_{j}\omega_{B_{j}}-\otimes_{j}\eta_{B_{j}}\right\|_{1}+\left\|\otimes_{j}\eta_{B_{j}}-\eta\right\|_{1}+2\sqrt{\varepsilon}$
$\displaystyle\leq\sqrt{2D(\omega||\otimes_{j}\omega_{B_{j}})}+2n\delta+2n\sqrt{\varepsilon}+\sqrt{2D(\eta||\otimes_{j}\eta_{B_{j}})}+2\sqrt{\varepsilon}$
$\displaystyle\leq\sqrt{8n(n\sqrt{\varepsilon_{1}}+\varepsilon_{1}^{1/4})+6n^{2}(\delta+\sqrt{\varepsilon})+4n\sqrt{\delta+\sqrt{\varepsilon}}}$
$\displaystyle+\sqrt{8n(n\sqrt{\varepsilon_{1}}+\varepsilon_{1}^{1/4})}+2n\delta+2(n+1)\sqrt{\varepsilon}.$

Here in the fourth line we use the quantum Pinsker inequality, which says that
$\|\rho-\sigma\|_{1}\leq\sqrt{2D(\rho\|\sigma)}$ for two density matrices
$\rho,\sigma$. Using the fact that $\varepsilon_{1}=6\sqrt{\varepsilon}$, we
have

$\displaystyle\frac{1}{2}\left\|\sigma-\rho\right\|_{1}$ $\displaystyle\leq
n\delta+2n\sqrt{\varepsilon}+\sqrt{8}n\varepsilon_{1}^{1/4}+\sqrt{8}\sqrt{n}\varepsilon_{1}^{1/8}+\frac{\sqrt{6}}{2}n\sqrt{\delta}+\frac{\sqrt{6}}{2}n\varepsilon^{1/4}+\sqrt{n}\delta^{1/4}+\sqrt{n}\varepsilon^{1/8}$
(322)
$\displaystyle\leq\sqrt{8}n\varepsilon_{1}^{1/4}+\sqrt{8}\sqrt{n}\varepsilon_{1}^{1/8}+5n\varepsilon^{1/8}+4n\delta^{1/4}$
$\displaystyle\leq 13n\varepsilon^{1/16}+4n\delta^{1/4}.$

∎

Finally, the next technical lemma bounds the distance between the learned
state and the unknown state $\ket{\psi}$.

######  Lemma 32.

Let $\ket{\psi}_{A_{1}\dots A_{L}B}$ be a pure state, and let
$\rho_{A_{1}\dots A_{L}B}=\outerproduct{\psi}{\psi}_{A_{1}\dots A_{L}B}$.
Suppose the following two properties hold:

  1. 1.

$\expectationvalue{\rho_{B}}{0_{B}}=1-\varepsilon$,

  2. 2.

$\rho_{A_{1}\dots A_{L}}=\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{L}}$.

Suppose $\\{\sigma_{A_{i}}\\}$ are density matrices that satisfies
$\frac{1}{2}\left\|\rho_{A_{i}}-\sigma_{A_{i}}\right\|_{1}\leq\delta$ for any
$i$. Then

$\frac{1}{2}\left\|(\otimes_{i=1}^{L}\sigma_{A_{i}})\otimes\outerproduct{0}{0}_{B}-\outerproduct{\psi}{\psi}\right\|_{1}\leq\sqrt{2\varepsilon+L\delta}.$
(323)

###### Proof.

The state $\ket{\psi}_{A_{1}\dots A_{L}B}$ can be written as

$\ket{\psi}_{A_{1}\dots
A_{L}B}=\sqrt{1-\varepsilon}\ket{0}_{B}\ket{\phi}_{A_{1}\dots
A_{L}}+\sqrt{\varepsilon}\ket{\mathrm{else}}_{A_{1}\dots A_{L}B},$ (324)

where $\bra{0}_{B}\ket{\mathrm{else}}_{A_{1}\dots A_{L}B}=0$. This implies
that

$\rho_{A_{1}\dots A_{L}}=\Tr_{B}\rho_{A_{1}\dots
A_{L}B}=(1-\varepsilon)\outerproduct{\phi}{\phi}_{A_{1}\dots
A_{L}}+\varepsilon\Tr_{B}\outerproduct{\mathrm{else}}{\mathrm{else}}.$ (325)

Note that

$\displaystyle\frac{1}{2}\left\|\rho_{A_{1}\dots
A_{L}}-\sigma_{A_{1}}\otimes\cdots\otimes\sigma_{A_{L}}\right\|_{1}$
$\displaystyle=\frac{1}{2}\left\|\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{L}}-\sigma_{A_{1}}\otimes\cdots\otimes\sigma_{A_{L}}\right\|_{1}$
(326)
$\displaystyle\leq\frac{1}{2}\sum_{i=1}^{L}\left\|\rho_{A_{i}}-\sigma_{A_{i}}\right\|_{1}$
$\displaystyle\leq L\delta.$

Therefore,

$\displaystyle\bra{\psi}_{A_{1}\dots
A_{L}B}\sigma_{A_{1}}\otimes\cdots\otimes\sigma_{A_{L}}\otimes\outerproduct{0}{0}_{B}\ket{\psi}_{A_{1}\dots
A_{L}B}$ $\displaystyle\geq\bra{\psi}\rho_{A_{1}\dots
A_{L}}\otimes\outerproduct{0}{0}_{B}\ket{\psi}-L\delta$ (327)
$\displaystyle\geq(1-\varepsilon)^{2}-L\delta$ $\displaystyle\geq
1-2\varepsilon-L\delta.$

This implies that

$\frac{1}{2}\left\|(\otimes_{i=1}^{L}\sigma_{A_{i}})\otimes\outerproduct{0}{0}_{B}-\outerproduct{\psi}{\psi}\right\|_{1}\leq\sqrt{2\varepsilon+L\delta}.$
(328)

∎

Proof of first claim of Theorem 9. Next we show how to use the above
techniques to learn an unknown quantum state $\ket{\psi}=U\ket{0^{n}}$, with
the promise that $U$ is a depth-$d$ circuit acting on a 2D lattice (here $d$
is treated as a generic parameter which is not necessarily a constant) with
arbitrary $\mathrm{SU}(4)$ gates.

We work with Viewpoint 2 described in Section 8.3. As discussed at the end of
Section 8.3, the learning process requires $\mathcal{O}(n)$ reduced density
matrices of $\ket{\psi}$ of size $\mathcal{O}(d^{2})$. Suppose all of these
reduced density matrices are learned to within $\varepsilon_{0}$ trace
distance with probability $1-\delta$, then by Lemma 23 it suffices to take a
randomized measurement dataset $\mathcal{T}_{\ket{\psi}}(N)$ of size

$N=\frac{2^{\mathcal{O}(d^{2})}}{\varepsilon_{0}^{2}}\log\frac{n}{\delta}.$
(329)

Next we proceed with the disentangling step shown in Fig. 4. We have learned
the reduced density matrices on the dotted regions shown in Fig. 4 (a) to
within $\varepsilon_{0}$ trace distance. Denote the dotted blue region as
$AA_{1}$ where $A$ is the colored blue region, and let $\rho_{AA_{1}}$ be the
reduced density matrix of $\ket{\psi}$ on $AA_{1}$. We know that there exists
a depth-$2d$ circuit $V_{AA_{1}}$ such that

$V_{AA_{1}}\rho_{AA_{1}}V_{AA_{1}}^{\dagger}=\outerproduct{0}{0}_{A}\otimes\sigma_{A_{1}}$
(330)

for some density matrix $\sigma_{A_{1}}$. We have learned a density matrix
$\hat{\rho}_{AA_{1}}$ such that
$\|\hat{\rho}_{AA_{1}}-\rho_{AA_{1}}\|_{1}\leq\varepsilon_{0}$. To find an
approximate local inversion for the region $A$, we perform a brute force
search over an $\varepsilon_{0}$-net for depth-$2d$ circuits acting on
$AA_{1}$, denoted as $\mathcal{N}_{\varepsilon_{0}}(AA_{1})$, which is
constructed by discretizing each $\mathrm{SU}(4)$ gate (see Definition 18 and
Lemma 19), which has size at most

$S=\left(\frac{d^{3}}{\varepsilon_{0}}\right)^{\mathcal{O}(d^{3})}.$ (331)

Note that Eq. (330) together with
$\|\hat{\rho}_{AA_{1}}-\rho_{AA_{1}}\|_{1}\leq\varepsilon_{0}$ implies that

$\Tr(\bra{0}_{A}V_{AA_{1}}\hat{\rho}_{AA_{1}}V^{\dagger}_{AA_{1}}\ket{0}_{A})\geq
1-\varepsilon_{0}.$ (332)

By definition of $\varepsilon_{0}$-net, there exists a unitary
$\hat{V}_{AA_{1}}\in\mathcal{N}_{\varepsilon_{0}}(AA_{1})$ that satisfies
$\|\hat{V}_{AA_{1}}-V_{AA_{1}}\|_{\infty}\leq\varepsilon_{0}$, which gives

$\Tr(\bra{0}_{A}\hat{V}_{AA_{1}}\hat{\rho}_{AA_{1}}\hat{V}_{AA_{1}}^{\dagger}\ket{0}_{A})\geq
1-2\varepsilon_{0}.$ (333)

The algorithm is to enumerate over all elements in
$\mathcal{N}_{\varepsilon_{0}}(AA_{1})$ and find the ones which satisfy the
above equation. Each of these circuits is an approximate local inversion in
the sense that

$\Tr(\bra{0}_{A}\hat{V}_{AA_{1}}\rho_{AA_{1}}\hat{V}_{AA_{1}}^{\dagger}\ket{0}_{A})\geq
1-3\varepsilon_{0}.$ (334)

Using the same argument as in Section 8.2, in Fig. 4 (a) we can find a
depth-$d$ circuit $\hat{V}$ acting on the width-$7d$ strip around $M$, such
that Eq. (334) is satisfied for all local colored regions. There are at most
$\sqrt{n}$ such regions. Let $\rho=\outerproduct{\psi}{\psi}$, by union bound,

$\Tr(\bra{0}_{M}\hat{V}\rho\hat{V}^{\dagger}\ket{0}_{M})\geq
1-3\sqrt{n}\varepsilon_{0}.$ (335)

Repeat the same procedure for all vertical $B_{i}$ strips shown in Fig. 4 (b).
There are at most $\sqrt{n}$ different vertical strips. Let $B=\cup_{i}B_{i}$,
and let $V$ denote the union of all learned inversion circuits across
different regions, we have

$\Tr(\bra{0}_{B}V\rho V^{\dagger}\ket{0}_{B})\geq 1-3n\varepsilon_{0}.$ (336)

Now, the problem reduces to learning the state $V\ket{\psi}$, which can be
formulated as follows.

Problem 2. We are given copies of a state $\sigma=\outerproduct{\phi}{\phi}$
with the promise that

  1. 1.

it is prepared by a depth-$2d$ circuit (defined on a 2D lattice) acting on
$\ket{0^{n}}$;

  2. 2.

its reduced density matrix on each of the $B_{i}$ regions in Fig. 4 (b) is
close $\outerproduct{0}{0}_{B_{i}}$, i.e.
$\expectationvalue{\sigma_{B}}{0_{B}}\geq 1-\varepsilon_{1}$.

The goal is to (approximately) learn the state $\ket{\phi}$.

Let $\ket{\phi}:=V\ket{\psi}$ and let $\varepsilon_{1}:=3n\varepsilon_{0}$.
Consider dividing the state $\sigma=\outerproduct{\phi}{\phi}$ into regions
$A_{1},A_{2},\dots,A_{L}$ and $B=\cup_{i}B_{i}$ as in Fig. 4 (b). As the
regions $\\{A_{i}\\}$ are sufficiently far from each other, the reduced
density matrix on $A=\cup_{i}A_{i}$ is a tensor product across each region,
i.e., $\sigma_{A_{1}\dots
A_{L}}=\sigma_{A_{1}}\otimes\cdots\otimes\sigma_{A_{L}}$. By Eq. (336), we
have $\expectationvalue{\sigma_{B}}{0_{B}}\geq 1-\varepsilon_{1}$. By Lemma
29, for each $i=1,\dots,L$ there exists a pure state $\ket{\phi}_{A_{i}}$ such
that $\expectationvalue{\sigma_{A_{i}}}{\phi_{A_{i}}}\geq 1-\varepsilon_{1}$.

Next we discuss how to learn the state $\sigma_{A_{i}}$ for a fixed $i$. This
is similar to the earlier situation in Viewpoint 2, but with the critical
difference that here $\sigma_{A_{i}}$ is no longer pure. So we list the
updated Viewpoint below.

Viewpoint 2’. $\sigma_{A_{i}}$ can be prepared by a depth-$2d$ circuit acting
on $A_{i}$ as well as some ancilla qubits $A_{i}^{L}$ and $A_{i}^{R}$, shown
in Fig. 5. To see this, recall that $\sigma_{A_{i}}$ is part of a state that
is prepared by a depth-$2d$ circuit. Now, imagine that we _undo_ all the gates
in that circuit, except for those in the _backward lightcone_ of $A_{i}$. This
procedure does not affect the state on $A_{i}$, and the resulting circuit
(denote as $W_{i}$) has exactly the same shape as in Fig. 5, where
$A_{i}^{L}$, $A_{i}^{R}$ both has width $2d$. Note that here $\sigma_{A_{i}}$
could be entangled with the ancilla qubits, and we have

$\Tr_{A_{i}^{L}A_{i}^{R}}\left(W_{i}\outerproduct{0}{0}_{A_{i}^{L}A_{i}A_{i}^{R}}W_{i}^{\dagger}\right)=\sigma_{A_{i}}.$
(337)

Using the same argument as the end of Section 8.3, the reduced density
matrices of $\sigma_{A_{i}}$ can be simulated by reduced density matrices of
$\outerproduct{\psi}{\psi}$ on slightly larger regions. Therefore we can
obtain reduced density matrices of $\sigma_{A_{i}}$ within trace distance
$\varepsilon_{0}$. Let $C$ be the solid blue region in Fig. 7, and let
$CC_{1}$ be the dotted blue region. We have learned a reduced density matrix
$\hat{\sigma}_{C}$ such that
$\|\hat{\sigma}_{C}-\sigma_{C}\|_{1}\leq\varepsilon_{0}$. From Viewpoint 2’,
we know that there is a depth-$2d$ circuit $W_{CC_{1}}$ acting on $CC_{1}$,
such that

$\Tr_{C_{1}}\left(W_{CC_{1}}\outerproduct{0}{0}_{CC_{1}}W_{CC_{1}}^{\dagger}\right)=\sigma_{C}.$
(338)

Consider an $\varepsilon_{0}$-net for depth-$2d$ circuits acting on $CC_{1}$,
denoted as $\mathcal{N}_{\varepsilon_{0}}(CC_{1})$. By definition, there
exists a unitary $\hat{W}_{CC_{1}}$ that satisfies
$\|\hat{W}_{CC_{1}}-W_{CC_{1}}\|_{\infty}\leq\varepsilon_{0}$, which means
that

$\displaystyle\left\|\Tr_{C_{1}}\left(\hat{W}_{CC_{1}}\outerproduct{0}{0}_{CC_{1}}\hat{W}_{CC_{1}}^{\dagger}\right)-\hat{\sigma}_{C}\right\|_{1}$
(339) $\displaystyle\leq$
$\displaystyle\left\|\Tr_{C_{1}}\left(\hat{W}_{CC_{1}}\outerproduct{0}{0}_{CC_{1}}\hat{W}_{CC_{1}}^{\dagger}\right)-\sigma_{C}\right\|_{1}+\left\|\sigma_{C}-\hat{\sigma}_{C}\right\|_{1}$
$\displaystyle\leq$ $\displaystyle 2\varepsilon_{0}.$

By enumerating over every element in $\mathcal{N}_{\varepsilon_{0}}(CC_{1})$,
we can find a list of circuits $\\{\hat{W}_{CC_{1}}^{\prime}\\}$ that satisfy
$\left\|\Tr_{C_{1}}\left(\hat{W}_{CC_{1}}^{\prime}\outerproduct{0}{0}_{CC_{1}}\hat{W}_{CC_{1}}^{\prime{\dagger}}\right)-\hat{\sigma}_{C}\right\|_{1}\leq
2\varepsilon_{0}$. Any such circuit $\hat{W}_{CC_{1}}^{\prime}$ will also
satisfy

$\left\|\Tr_{C_{1}}\left(\hat{W}_{CC_{1}}^{\prime}\outerproduct{0}{0}_{CC_{1}}\hat{W}_{CC_{1}}^{\prime{\dagger}}\right)-\sigma_{C}\right\|_{1}\leq
3\varepsilon_{0}.$ (340)

Using the same argument as in Section 8.3, we can merge these learned local
circuits into a global depth-$2d$ circuit $\hat{W}_{i}$. Let
$\hat{\sigma}_{A_{i}}:=\Tr_{A_{i}^{L}A_{i}^{R}}\left(\hat{W}_{i}\outerproduct{0}{0}_{A_{i}^{L}A_{i}A_{i}^{R}}\hat{W}_{i}^{\dagger}\right)$
be the learned reduced density matrix on $A_{i}$, then the local reduced
density matrices of $\hat{\sigma}_{A_{i}}$ and $\sigma_{A_{i}}$ are
$3\varepsilon_{0}$ close in trace distance on solid colored regions in Fig. 7.
This allows us to invoke the main technical lemma, Lemma 31, which gives

$\frac{1}{2}\left\|\hat{\sigma}_{A_{i}}-\sigma_{A_{i}}\right\|_{1}\leq
13n\varepsilon_{1}^{1/16}+8n\varepsilon_{0}^{1/4}\leq
22n^{17/16}\varepsilon_{0}^{1/16}.$ (341)

The state $\ket{\psi}$ can be approximately prepared as follows:

  1. 1.

Initialize registers $A_{i},B_{i},A_{i}^{L},A_{i}^{R}$ in the state $\ket{0}$.
Let $A=\cup_{i}A_{i}$ and $B=\cup_{i}B_{i}$.

  2. 2.

For each $i$, apply the depth-$2d$ circuit $\hat{W}_{i}$ to
$A_{i}^{L}A_{i}A_{i}^{R}$. The reduced density matrix on $AB$ equals
$(\otimes_{i}\hat{\sigma}_{A_{i}})\otimes\outerproduct{0}{0}_{B}$

  3. 3.

Apply the depth-$d$ circuit $V^{\dagger}$ to $AB$, and the reduced density
matrix on $AB$ is
$\hat{\rho}=V^{\dagger}(\otimes_{i}\hat{\sigma}_{A_{i}})\otimes\outerproduct{0}{0}_{B}V$,
which approximately equals to $\outerproduct{\psi}{\psi}$.

Similar to the proof of second claim of Theorem 9 at the end of Section 8.3,
we can choose the $A_{i}$ regions to be sufficiently wide, such that the
number of ancilla qubits equals to $tn$ for an arbitrarily small constant $t$.

The final task is to bound the error between the learned density matrix and
$\outerproduct{\psi}{\psi}$. Using Lemma 32, the trace distance can be bounded
as

$\displaystyle\frac{1}{2}\left\|V^{\dagger}(\otimes_{i}\hat{\sigma}_{A_{i}})\otimes\outerproduct{0}{0}_{B}V-\outerproduct{\psi}{\psi}\right\|_{1}$
$\displaystyle=\frac{1}{2}\left\|(\otimes_{i}\hat{\sigma}_{A_{i}})\otimes\outerproduct{0}{0}_{B}-V\outerproduct{\psi}{\psi}V^{\dagger}\right\|_{1}$
(342) $\displaystyle\leq\sqrt{2\cdot 3n\varepsilon_{0}+\sqrt{n}\cdot
22n^{17/16}\varepsilon_{0}^{1/16}}$ $\displaystyle\leq
6n^{25/32}\varepsilon_{0}^{1/32}.$

Therefore, to achieve trace distance $\varepsilon$, it suffices to choose
$\varepsilon_{0}=\mathcal{O}(\frac{\varepsilon^{32}}{n^{25}})$. The total
sample complexity is

$N=\frac{2^{\mathcal{O}(d^{2})}}{\varepsilon_{0}^{2}}\log\frac{n}{\delta}=\frac{2^{\mathcal{O}(d^{2})}n^{50}}{\varepsilon^{64}}\log\frac{n}{\delta}.$
(343)

The total running time is

$n\cdot S=\left(\frac{nd^{3}}{\varepsilon}\right)^{\mathcal{O}(d^{3})}.$ (344)

##  9 Verifying learned shallow circuits under average-case distance

From the previous appendices, we have seen that given an $n$-qubit CPTP map
$\mathcal{C}$ promised to be a unitary $U$ generated by a constant-depth
quantum circuit, we can learn a constant-depth $2n$-qubit circuit $\hat{V}$,
such that $\hat{V}$ is close to $U\otimes U^{\dagger}$, and the reduced
channel $\hat{\mathcal{E}}:=\mathcal{E}^{\hat{V}}_{\leq n}$ of $\hat{V}$ on
the first $n$ qubits is close to $\mathcal{C}=U(\cdot)U^{\dagger}=\mathcal{U}$
in the diamond distance. In this section, we answer the question: What happens
if there is no promise that $\mathcal{C}$ is a unitary generated by a shallow
quantum circuit, and, furthermore, $\mathcal{C}$ may not even be unitary?

Given an arbitrary CPTP map $\mathcal{C}$, the proposed algorithm can still
learn a constant-depth $2n$-qubit circuit $\hat{V}$ with an associated
$n$-qubit CPTP map $\hat{\mathcal{E}}:=\mathcal{E}^{\hat{V}}_{\leq n}$.
However, without the promise on $\mathcal{C}$, the learned map
$\hat{\mathcal{E}}$ could be arbitrary. This raises the question: can we
verify that $\hat{\mathcal{E}}$ is close to $\mathcal{C}$? From the previous
section on the hardness for learning log-depth circuits, we see that even if
$\mathcal{C}$ is an $n$-qubit unitary $U$ generated by a log-depth circuit,
one already needs $\exp(\Omega(n))$ queries to check if $U$ is close to $I$ in
the diamond distance or not. Hence, when the learning algorithm outputs