Proof. For \(\ell=1,\dots,D\), write \[V_\ell := \bigotimes_{(u,v)\in M_\ell} U_{uv}^{(\ell)},\] so that \(U=V_D\cdots V_1\). Define intermediate observables by \[A_0:=A, \qquad A_{t+1}:=V_{D-t}^* A_t V_{D-t}, \qquad t=0,\dots,D-1.\] Thus \(A_D=U^*AU\). We claim by induction that \(A_t\) is supported on \(L_t(S)\). This is true for \(t=0\), since \(A_0=A\) is supported on \(S=L_0(S)\).

Assume that \(A_t\) is supported on \(L_t(S)\). We pull \(A_t\) back through the layer \(V_{D-t}\), namely we form \(A_{t+1}=V_{D-t}^*A_tV_{D-t}\). Since \(M_{D-t}\) is a matching, each gate in this layer acts on a disjoint pair of qubits. A gate acting on a pair disjoint from \(L_t(S)\) commutes with \(A_t\) and therefore does not change its support. A gate acting on a pair \((u,v)\) with at least one endpoint in \(L_t(S)\) can only enlarge the support by adding the other endpoint of that pair. Hence \[\operatorname{supp}(A_{t+1}) \subseteq L_t(S)\cup M_{D-t}(L_t(S)) = L_{t+1}(S).\] This proves the induction, and therefore \(U^*AU=A_D\) is supported on \(L_D(S)\).

It remains to prove the size bound. Since \(M_\ell\) is a matching, every element of \(L_t(S)\) has at most one partner under \(M_{D-t}\). Therefore \(|M_{D-t}(L_t(S))|\le |L_t(S)|\). Consequently, \[|L_{t+1}(S)| = |L_t(S)\cup M_{D-t}(L_t(S))| \le |L_t(S)|+|M_{D-t}(L_t(S))| \le 2|L_t(S)|.\] Iterating gives \(|L_D(S)|\le 2^D |S|\). Since \(L_D(S)\subseteq[n+r]\), we also have \(|L_D(S)|\le n+r\). Combining the two bounds yields the result. ◻

Proof. This is the same growth estimate as Lemma 1, but applied in the forward direction. Starting from \(v\), define \[F_0(v):=\{v\}, \qquad F_{\ell+1}(v):=F_\ell(v)\cup M_{\ell+1}(F_\ell(v)), \qquad \ell=0,\dots,D-1.\] Since each \(M_\ell\) is a matching, each step can at most double the size of the set. Hence \(|F_D(v)|\le 2^D\).

Moreover, \(v\in L_D(j)\) if and only if \(j\in F_D(v)\). Therefore \[|\{j\in[n]:v\in L_D(j)\} | \le |F_D(v)| \le 2^D.\] ◻

Proof. Fix \(i\in[n]\). Every neighbor \(j\) of \(i\) in \(\mathsf G_D^{\mathrm{dep}}\) satisfies \(L_D(i)\cap L_D(j)\neq\emptyset\). Hence, by a union bound, \[\deg_{\mathsf G_D^{\mathrm{dep}}}(i) \le \sum_{v\in L_D(i)} |\{j\in[n]:v\in L_D(j)\} |.\] By Lemmas 1 and 2, the right-hand side is at most \[|L_D(i)|2^D\le 2^D\cdot 2^D=4^D.\] Taking the maximum over \(i\in[n]\) proves the claim. ◻

Proof. For each \(s=1,\dots,p\), define the pulled-back one-site observable \(O_s:=U^*(\sigma_{i_s}^{a_s}\otimes I_{\mathrm{anc}})U.\) By Lemma 1, \(O_s\) is supported on \(L_D(i_s)\). Since the sites in \(I\) form an independent set in \(\mathsf{G}_D^{\mathrm{dep}}\), we have \[L_D(i_s)\cap L_D(i_t)=\emptyset \qquad \text{for all }s\neq t .\] Since the observables \(O_1,\dots,O_p\) are supported on pairwise disjoint input tensor factors and \(|0^{n+r}\rangle\) is a product state, \[\begin{align} \langle\phi|P_I^a\otimes I_{\mathrm{anc}}|\phi\rangle &= \langle 0^{n+r}|U^*(P_I^a\otimes I_{\mathrm{anc}})U|0^{n+r}\rangle = \langle 0^{n+r}|O_1\cdots O_p|0^{n+r}\rangle \\ &= \prod_{s=1}^p \langle 0^{n+r}|O_s|0^{n+r}\rangle = \prod_{s=1}^p \langle\phi|\sigma_{i_s}^{a_s}\otimes I_{\mathrm{anc}}|\phi\rangle = \prod_{s=1}^p m_{i_s}^\phi(a_s). \end{align}\] Hence \(\chi_{I,a}(\theta)=0\). ◻

Proof. Fix \(\theta=(M_1,\dots,M_D,U)\in\mathsf{T}_{n,r}^{(D)}\), and write \(\phi=\phi_\theta=U|0^{n+r}\rangle\). Since the \(g_{I,a}\)’s are independent standard Gaussians, \[\operatorname{Var}(R(\theta)) = \binom np^{-1} \sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 .\] Thus it suffices to prove the deterministic bound \[\sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 \le C_p n^{p-1}2^D.\]

For each physical site \(i\in[n]\) and label \(b\in\{1,2,3\}\), define the pulled-back Pauli observable \(O_i^b := U^*(\sigma_i^b\otimes I_{\mathrm{anc}})U\). Also define its mean, centered version, and fluctuation vector respectively by \[m_i^b := \langle0^{n+r}|O_i^b|0^{n+r}\rangle, \qquad A_i^b := O_i^b-m_i^b \mathrm{Id}_{n+r}, \qquad v_i^b := A_i^b|0^{n+r}\rangle,\] where \(\mathrm{Id}_{n+r}\) denotes the identity operator on \(\mathcal{H}_{n,r}\). We refer to \(v_i^b\) as the fluctuation vector because it is the component of \(O_i^b|0^{n+r}\rangle\) left after subtracting its mean component \(m_i^b|0^{n+r}\rangle\).

By Lemma 1, \(O_i^b\), and hence \(A_i^b\), is supported on \(L_D(i)\subset[n+r]\). Therefore, we have \[v_i^b \in (\mathbb{C}^2)^{\otimes L_D(i)} \otimes |0\rangle^{\otimes([n+r]\setminus L_D(i))}.\] Equivalently, if \(e_T\) denotes the computational basis vector with ones on \(T\subset[n+r]\) and zeros elsewhere, then \(v_i^b\) is a linear combination only of basis vectors \(e_T\) with \(T\subseteq L_D(i)\).

Note also that, \[\langle 0^{n+r},v_i^b\rangle = \langle0^{n+r}|A_i^b|0^{n+r}\rangle = 0 .\] Moreover, since \(A_i^b\) is self-adjoint, \[\|v_i^b\|^2 = \langle0^{n+r}|(A_i^b)^2|0^{n+r}\rangle = \langle0^{n+r}|(O_i^b-m_i^b \mathrm{Id}_{n+r})^2|0^{n+r}\rangle .\] Using \(\phi=U |0^{n+r} \rangle\), this equals \[\langle \phi | ( \sigma_i^b\otimes I_{\mathrm{anc}} - \langle\phi|\sigma_i^b\otimes I_{\mathrm{anc}}|\phi\rangle \mathrm{Id}_{n+r} )^2 | \phi \rangle .\] Since \((\sigma_i^b\otimes I_{\mathrm{anc}})^2=\mathrm{Id}_{n+r}\), we obtain \[\|v_i^b\|^2 = 1- \langle\phi|\sigma_i^b\otimes I_{\mathrm{anc}}|\phi\rangle^2 \le 1.\]

By Lemma 2, the physical backward supports satisfy \[\sup_{v\in[n+r]} |\{i\in[n]:v\in L_D(i)\} | \le 2^D .\] We now apply Lemma 14 in Appendix 4.1 with \[\Omega=[n+r], \qquad J=[n], \qquad J_0=\{1,2,3\}, \qquad L_i=L_D(i), \qquad w_i^b=v_i^b, \qquad \gamma=2^D .\] It follows that for every \(x\in(\mathbb{C}^2)^{\otimes(n+r)}\), \[\begin{align} \label{eq:fluctuation-vectors-bound} \sum_{i=1}^n\sum_{b=1}^3 |\langle x,v_i^b\rangle|^2 \le 3\cdot 2^D\|x\|^2. \end{align}\tag{4}\]

Now fix \(I=(i_1,\dots,i_p)\in\mathcal{I}_p^n\) and \(a=(a_1,\dots,a_p)\in\{1,2,3\}^p\). Write \[O_s:=O_{i_s}^{a_s}, \qquad m_s:=m_{i_s}^{a_s}, \qquad A_s:=O_s-m_s \mathrm{Id}_{n+r}.\] By the definition of \(P_I^a\) and \(O_s\), we have \[P_I^a\otimes I_{\mathrm{anc}} = \prod_{s=1}^p(\sigma_{i_s}^{a_s}\otimes I_{\mathrm{anc}}),\] and hence \[U^*(P_I^a\otimes I_{\mathrm{anc}})U = \prod_{s=1}^p U^*(\sigma_{i_s}^{a_s}\otimes I_{\mathrm{anc}})U = O_1\cdots O_p .\] Therefore \[\chi_{I,a}(\theta) = \langle0^{n+r}|O_1\cdots O_p|0^{n+r}\rangle - \prod_{s=1}^p m_s .\]

We now bound \(\chi_{I,a}(\theta)\). Since \(A_s=O_s-m_s \mathrm{Id}_{n+r}\), we have the telescoping identity \[O_1\cdots O_p-\prod_{s=1}^p m_s \mathrm{Id}_{n+r} = \sum_{s=1}^p \big( \prod_{r<s}O_r \big) A_s \big( \prod_{r>s}m_r \big),\] and so \[\chi_{I,a}(\theta) = \sum_{s=1}^p \big( \prod_{r>s}m_r \big) \big\langle 0^{n+r} \big | \big (\prod_{r<s}O_r \big) A_s \big| 0^{n+r} \big\rangle .\] For each \(s\), define \[x_s := \big(\prod_{r<s}O_r\big)^*|0^{n+r}\rangle .\] Each \(O_r\) is unitary, so \(\|x_s\|=1\). Moreover, since \(v_{i_s}^{a_s}=A_s|0^{n+r}\rangle\), \[\big\langle 0^{n+r} \big| \big(\prod_{r<s}O_r\big) A_s \big| 0^{n+r} \big\rangle = \langle x_s,v_{i_s}^{a_s}\rangle .\] Also \(|m_r|\le1\). Hence \[|\chi_{I,a}(\theta)| \le \sum_{s=1}^p |\langle x_s,v_{i_s}^{a_s}\rangle|.\]

By Cauchy–Schwarz, \[|\chi_{I,a}(\theta)|^2 \le p \sum_{s=1}^p |\langle x_s,v_{i_s}^{a_s}\rangle|^2 .\]

We now sum this estimate over \(I\in\mathcal{I}_p^n\) and \(a\in\{1,2,3\}^p\). It is convenient to enlarge the sum from increasing \(p\)-tuples to ordered \(p\)-tuples of distinct physical sites, \[[n]^p_{\neq} := \{(i_1,\dots,i_p)\in[n]^p: i_1,\dots,i_p \text{ are distinct}\}.\] This changes the estimate only by a constant depending on \(p\). Hence \[\begin{align} \sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 &\le C_p \sum_{(i_1,\dots,i_p)\in[n]^p_{\neq}} \sum_{a\in\{1,2,3\}^p} \sum_{s=1}^p |\langle x_s,v_{i_s}^{a_s}\rangle|^2 \\ &= C_p \sum_{s=1}^p \sum_{(i_1,\dots,i_p)\in[n]^p_{\neq}} \sum_{a\in\{1,2,3\}^p} |\langle x_s,v_{i_s}^{a_s}\rangle|^2 . \end{align}\] We bound the inner sum for a fixed \(s\). Write \(i_{-s}:=(i_r)_{r\neq s}\) and \(a_{-s}:=(a_r)_{r\neq s}\). Then \[\sum_{(i_1,\dots,i_p)\in[n]^p_{\neq}} \sum_{a\in\{1,2,3\}^p} |\langle x_s,v_{i_s}^{a_s}\rangle|^2 = \sum_{i_{-s}\in[n]^{p-1}_{\neq}} \sum_{a_{-s}\in\{1,2,3\}^{p-1}} \sum_{i_s\in[n]\setminus\{i_r:r\neq s\}} \sum_{a_s=1}^3 |\langle x_s,v_{i_s}^{a_s}\rangle|^2 .\] For each fixed choice of \(i_{-s},a_{-s}\), the vector \(x_s\) is fixed and has norm one. Dropping the restriction \(i_s\notin\{i_r:r\neq s\}\) can only increase the inner sum, so \[\sum_{i_s\in[n]\setminus\{i_r:r\neq s\}} \sum_{a_s=1}^3 |\langle x_s,v_{i_s}^{a_s}\rangle|^2 \le \sum_{i_s=1}^n \sum_{a_s=1}^3 |\langle x_s,v_{i_s}^{a_s}\rangle|^2 .\] Applying 4 with \(x=x_s\), we get \[\sum_{i_s=1}^n \sum_{a_s=1}^3 |\langle x_s,v_{i_s}^{a_s}\rangle|^2 \le 3\cdot 2^D\|x_s\|^2 = 3\cdot 2^D .\] There are at most \(n^{p-1}\) choices for \(i_{-s}\) and \(3^{p-1}\) choices for \(a_{-s}\). Therefore, for each fixed \(s\in[p]\), \[\sum_{(i_1,\dots,i_p)\in[n]^p_{\neq}} \sum_{a\in\{1,2,3\}^p} |\langle x_s,v_{i_s}^{a_s}\rangle|^2 \le C_p n^{p-1}2^D .\] Substituting this bound and summing over \(s=1,\dots,p\), we obtain \[\sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 \le C_p n^{p-1}2^D .\] This is the desired deterministic bound. Taking the supremum over \(\theta\in\mathsf{T}_{n,r}^{(D)}\) completes the proof. ◻

Proof. We identify a parameter \(\theta\in\mathsf{T}_{n,r}^{(D)}\) with its corresponding circuit unitary \(U\) when no confusion can arise. Thus \(U=V_DV_{D-1}\cdots V_1\), where each layer has the form \[V_t = \bigotimes_{e\in M_t}U_e^{(t)}, \qquad U_e^{(t)}\in U(4),\] for a perfect matching \(M_t\) on \([n+r]\). Throughout, whenever we write a tensor product over a partial matching, the resulting operator is understood to act as the identity on all qubits not covered by that matching.

We prove the entropy bound by replacing each circuit, in the metric \(\mathsf{d}_{R}\), by an equivalent pruned and relabeled circuit acting on at most \(n2^D\) qubits.

We now construct the pruned circuit. It is enough to track how physical observables pull back through the circuit. Here and below, a physical observable means an observable supported on the first \(n\) qubits.

Write \(U=V_DV_{D-1}\cdots V_1\), where \(V_1\) acts first and \(V_D\) acts last. Given a physical observable \(X\), define the pulled-back observables \[X_D:=X, \qquad X_{t-1}:=V_t^*X_tV_t, \qquad t=D,D-1,\dots,1.\] Thus \(X_t\) is the observable obtained after pulling \(X\) backward through the later layers \(D,D-1,\dots,t+1\). In particular, \(X_0=U^*XU.\) Since \(X_D=X\) is physical, \(\operatorname{supp}(X_D)\subseteq[n]\). We will use a joint support bound that works for all physical observables at once, and therefore initialize \(S_D:=[n].\)

Now define the backward active sets recursively. For \(t=D,D-1,\dots,1\), set \[R_t:=\{e\in M_t:e\cap S_t\neq\emptyset\}, \qquad S_{t-1}:=S_t\cup\bigcup_{e\in R_t}e.\] Here \(S_t\) is a set which contains the support of \(X_t\), uniformly over all physical observables \(X\) considered in the residual process. The set \(R_t\) consists of precisely those gates in layer \(t\) that touch this current backward support. These are the only gates in layer \(t\) that can affect the pulled-back observable when passing from time \(t\) to time \(t-1\).

Since \(M_t\) is a matching, each qubit in \(S_t\) belongs to at most one edge of \(M_t\). Therefore each active qubit can introduce at most one new qubit when we pull backward through layer \(t\). Hence \(|S_{t-1}|\le 2|S_t|,\) and iterating gives \[|S_t|\le n2^{D-t}, \qquad t=0,1,\dots,D.\] In particular, \(|S_0|\le n2^D\). Moreover, since every edge of \(R_t\) touches \(S_t\), we have \(|R_t|\le |S_t|\), and hence \[\sum_{t=1}^D |R_t| \le \sum_{t=1}^D |S_t| \le n(2^D-1).\]

Define the pruned layer and pruned circuit by \[V_t^{\mathrm{pr}} := \bigotimes_{e\in R_t}U_e^{(t)}, \qquad U^{\mathrm{pr}} := V_D^{\mathrm{pr}}\cdots V_1^{\mathrm{pr}},\] where \(V_t^{\mathrm{pr}}\) acts as the identity on all qubits not covered by \(R_t\). We claim that, for every physical observable \(X\), \(U^*XU=(U^{\mathrm{pr}})^*XU^{\mathrm{pr}}\).

To prove the claim, use the pulled-back observables \(X_t\) defined above. We prove by induction that \(\operatorname{supp}(X_t)\subseteq S_t\) for every \(t=D,D-1,\dots,0\), and that \[X_{t-1}=(V_t^{\mathrm{pr}})^*X_tV_t^{\mathrm{pr}} \qquad\text{for }t=D,D-1,\dots,1.\] The base case holds because \(X_D=X\) is physical, so \(\operatorname{supp}(X_D)\subseteq[n]=S_D\).

Assume that \(\operatorname{supp}(X_t)\subseteq S_t\). Let \[V_t^{\mathrm{bad}} := \bigotimes_{e\in M_t\setminus R_t}U_e^{(t)}.\] Since \(M_t\) is a matching, the gates in \(R_t\) and \(M_t\setminus R_t\) act on disjoint pairs, and hence \(V_t=V_t^{\mathrm{bad}}V_t^{\mathrm{pr}}\). By definition of \(R_t\), every edge in \(M_t\setminus R_t\) is disjoint from \(S_t\). Hence \(V_t^{\mathrm{bad}}\) is supported outside \(\operatorname{supp}(X_t)\), and therefore \((V_t^{\mathrm{bad}})^*X_tV_t^{\mathrm{bad}}=X_t\). It follows that \[X_{t-1} = V_t^*X_tV_t = (V_t^{\mathrm{pr}})^* (V_t^{\mathrm{bad}})^* X_t V_t^{\mathrm{bad}} V_t^{\mathrm{pr}} = (V_t^{\mathrm{pr}})^*X_tV_t^{\mathrm{pr}} .\] Finally, conjugation by \(V_t^{\mathrm{pr}}\) can only spread the support along the edges in \(R_t\). Thus \[\operatorname{supp}(X_{t-1}) \subseteq S_t\cup\bigcup_{e\in R_t}e = S_{t-1}.\] This proves the induction. Since \(X_0=U^*XU\), the displayed identity for \(X_{t-1}\) also gives \(U^*XU=(U^{\mathrm{pr}})^*XU^{\mathrm{pr}}\), as claimed.

Let \(\theta^{\mathrm{pr}}\) denote the circuit parameter obtained from \(\theta\) by replacing \(U\) with \(U^{\mathrm{pr}}\), equivalently by setting all deleted gates to the identity. Applying this identity to the physical Pauli products \(P_I^a\otimes I_{\mathrm{anc}}\) and to the one-site physical observables \(\sigma_i^b\otimes I_{\mathrm{anc}}\), we obtain \(\chi_{I,a}(\theta)=\chi_{I,a}(\theta^{\mathrm{pr}})\) for every \(I\in\mathcal{I}_p^n\) and \(a\in\{1,2,3\}^p\). Consequently, \(\mathsf d_R(\theta,\theta^{\mathrm{pr}})=0\).

After pruning, each circuit parameter \(\theta\) is \(\mathsf d_R\)-equivalent to the pruned parameter \(\theta^{\mathrm{pr}}\), whose nonidentity gates involve only the qubits in the backward active set \(S_0\). In particular, at most \(n(2^D-1)\) ancillas can remain active. However, these active ancillas may have arbitrary labels among the \(r\) available ancillas. If we counted these labels directly, we would reintroduce an \(r\)-dependent combinatorial factor. Since all ancillas are initialized in the same state and the observables in the residual process act only on the physical qubits, we may permute ancilla labels, while keeping the physical labels fixed, without changing any physical expectation.

Concretely, let \(A(\theta^{\mathrm{pr}}):=S_0\setminus[n]\) be the set of ancilla labels appearing in the joint backward support of the physical outputs. Since \(|S_0|\le n2^D\), we have \(|A(\theta^{\mathrm{pr}})|\le n(2^D-1)\).

Set \[q_*:=\min\{r,n(2^D-1)\}, \qquad Q:=n+q_*.\] Then \(Q\le n2^D\). Let \[K:=\{1,\dots,n\}\cup\{n+1,\dots,n+q_*\}\] be the set consisting of the physical qubits and the first \(q_*\) ancillas.

Since \(|A(\theta^{\mathrm{pr}})|\le q_*\), there exists a permutation \(\pi\) of \([n+r]\) such that \(\pi(i)=i\) for every physical label \(i\in[n]\), and \[\pi(A(\theta^{\mathrm{pr}}))\subseteq\{n+1,\dots,n+q_*\}.\] Let \(P_\pi\) denote the corresponding qubit-permutation unitary, and define \(\widetilde{U}:=P_\pi U^{\mathrm{pr}}P_\pi^*\).

Let \(\widetilde{\theta}\) denote the corresponding relabeled circuit parameter. Then \(\widetilde{\theta}\) is a depth-\(D\) matching-circuit parameter whose nonidentity gates are all supported on \(K\).

We now check that this relabeling preserves all residual coefficients. Since \(\pi\) fixes the physical labels, for every physical observable \(X\), \(P_\pi^*XP_\pi=X\). Also \(P_\pi|0^{n+r}\rangle=|0^{n+r}\rangle\). Therefore \[\langle0^{n+r}|\widetilde{U}^*X\widetilde{U}|0^{n+r}\rangle = \langle0^{n+r}| U^{\mathrm{pr}*}XU^{\mathrm{pr}} |0^{n+r}\rangle.\] Applying this identity to all physical Pauli products and one-site physical Pauli observables gives \[\chi_{I,a}(\widetilde{\theta}) = \chi_{I,a}(\theta^{\mathrm{pr}}) = \chi_{I,a}(\theta)\] for every \(I\in\mathcal{I}_p^n\) and \(a\in\{1,2,3\}^p\). Thus \(\mathsf d_R(\theta,\widetilde{\theta})=0\).

Consequently, every circuit parameter in \(\mathsf{T}_{n,r}^{(D)}\) is \(\mathsf{d}_{R}\)-equivalent to a circuit parameter whose nonidentity gates act only on a canonical set of size \(Q\le n2^D\).

It remains to cover depth-\(D\) matching circuits on the set \(K\). Let \(N_Q\) be the number of partial matchings on a \(Q\)-element set. A partial matching with exactly \(m\) edges is obtained by choosing \(2m\) vertices and partitioning them into \(m\) unordered pairs. Hence \[N_Q = \sum_{m=0}^{\lfloor Q/2\rfloor} \binom{Q}{2m} \frac{(2m)!}{2^m m!} = \sum_{m=0}^{\lfloor Q/2\rfloor} \frac{Q!}{(Q-2m)!2^m m!}.\] For each \(m\), \[\frac{Q!}{(Q-2m)!2^m m!} \le Q^{2m}\le Q^Q.\] Thus \[N_Q \le (Q+1)Q^Q \le \exp (CQ\log(eQ)).\] A depth-\(D\) architecture is a sequence of \(D\) partial matchings on \(K\). Therefore the number of possible architectures is at most \(N_Q^D\). Hence \[\log(N_Q^D) = D\log N_Q \le C DQ\log(eQ).\] Since \(Q\le n2^D\), we have \[DQ\log(eQ) \le Dn2^D\log(en2^D) \le C Dn2^D(\log n+D).\] Thus the logarithm of the number of possible depth-\(D\) architectures is at most \(C Dn2^D(\log n+D)\).

We now cover the remaining unitary degrees of freedom on the active set \(K\). The counting is done in two stages. We first fix the pruned, relabeled architecture, namely the sequence of partial matchings \(\mathcal{M}=(M_1,\dots,M_D)\) on \(K\). Then we discretize the two-qubit unitaries assigned to the edges of these matchings. The nets obtained for the different architectures will later be combined by taking a union over the possible choices of \(\mathcal{M}\).

Fix a depth-\(D\) architecture \(\mathcal{M}=(M_1,\dots,M_D)\), where each \(M_t\) is a partial matching on the active set \(K.\) Let \(J(\mathcal{M}):=\sum_{t=1}^D |M_t|\) be the number of two-qubit gate locations. Since each \(M_t\) is a partial matching, \[J(\mathcal{M})\le \frac{DQ}{2}\le Dn2^D.\]

Set \(J_0:=Dn2^D.\) The unitary group \(U(4)\), equipped with the operator norm, has covering numbers \[N(U(4),\|\cdot\|_{\mathrm{op}},\delta) \le \left(\frac{C}{\delta}\right)^C, \qquad 0<\delta\le1.\] Taking the product over all gate locations in the fixed architecture gives a gate-net of cardinality at most \[\left(\frac{C}{\delta}\right)^{C J(\mathcal{M})} \le \left(\frac{C}{\delta}\right)^{C J_0}.\]

We now relate the gate accuracy \(\delta\) to the residual metric. Let \(\theta_U\) and \(\theta_V\) be two circuit parameters with the same architecture. Enumerate their corresponding gate locations in circuit order and write \[U=A_J A_{J-1}\cdots A_1, \qquad V=B_JB_{J-1}\cdots B_1,\] where \(J=J(\mathcal{M})\), and suppose that \(\|A_j-B_j\|_{\mathrm{op}}\le\delta\) for \(j=1,\dots,J\). The telescoping expansion gives \[U-V = \sum_{j=1}^J A_J\cdots A_{j+1} (A_j-B_j) B_{j-1}\cdots B_1,\] and therefore \(\|U-V\|_{\mathrm{op}} \le J\delta \le J_0\delta\). For any physical Pauli observable \(X=\sigma_i^b\otimes I_{\mathrm{anc}}\), we have \[\|U^*XU-V^*XV\|_{\mathrm{op}} \le 2\|U-V\|_{\mathrm{op}} \le 2J_0\delta.\] Since all pulled-back Pauli observables are unitary, for \(I=\{i_1,\dots,i_p\}\) and \(a=(a_1,\dots,a_p)\), \[\big\| \prod_{s=1}^p O_{i_s}^{a_s}(U) - \prod_{s=1}^p O_{i_s}^{a_s}(V) \big\|_{\mathrm{op}} \le \sum_{s=1}^p \|O_{i_s}^{a_s}(U)-O_{i_s}^{a_s}(V)\|_{\mathrm{op}} \le 2pJ_0\delta.\] Similarly, for every physical site \(i\in[n]\) and every \(b\in\{1,2,3\}\), \[\left| \langle 0^{n+r}|O_i^b(U)|0^{n+r}\rangle - \langle 0^{n+r}|O_i^b(V)|0^{n+r}\rangle \right| \le \|O_i^b(U)-O_i^b(V)\|_{\mathrm{op}} \le 2J_0\delta .\] Since these expectations have absolute value at most \(1\), it follows that \[\big| \prod_{s=1}^p \langle 0^{n+r}|O_{i_s}^{a_s}(U)|0^{n+r}\rangle - \prod_{s=1}^p \langle 0^{n+r}|O_{i_s}^{a_s}(V)|0^{n+r}\rangle \big| \le 2pJ_0\delta .\] Hence \[|\chi_{I,a}(\theta_U)-\chi_{I,a}(\theta_V)| \le C_pJ_0\delta,\] and so \[\mathsf d_R(\theta_U,\theta_V)^2 = \binom np^{-1} \sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta_U)-\chi_{I,a}(\theta_V)|^2 \le C_pJ_0^2\delta^2.\] Thus \(\mathsf{d}_{R}(\theta_U,\theta_V)\le C_pJ_0\delta\). If \(0<\eta\le C_p\), choose \(\delta=\frac{\eta}{C_pJ_0}.\) Then the product gate-net is an \(\eta\)-net in \(\mathsf{d}_{R}\) for a fixed architecture, and its logarithmic size is at most \(C_pJ_0\log (C_pJ_0/\eta)\).

If \(\eta>C_p\), then one representative per fixed architecture is enough after increasing \(C_p\), because \(|\chi_{I,a}|\le2\) implies that the \(\mathsf{d}_{R}\)-diameter is bounded by a constant depending only on \(p\). Thus, for all \(\eta>0\), the gate contribution for a fixed architecture is bounded by \[C_pJ_0\log_+\left(\frac{C_pJ_0}{\eta}\right) = C_pDn2^D \log_+\left(\frac{C_pDn2^D}{\eta}\right).\]

It remains to combine the architecture count with the fixed-architecture gate nets. By the pruning and relabeling construction above, every circuit parameter \(\theta\in\mathsf{T}_{n,r}^{(D)}\) is \(\mathsf{d}_{R}\)-equivalent to a pruned, relabeled circuit parameter whose nonidentity gates act only on the canonical active set \(K\), with \(|K|\le n2^D\). Thus it suffices to cover the collection of such pruned, relabeled circuits.

We showed that the number of possible pruned architectures on \(K\) has logarithm at most \(C Dn2^D(\log n+D)\). For each fixed pruned architecture, the preceding gate-discretization argument gives an \(\eta\)-net in \(\mathsf{d}_{R}\) of logarithmic size at most \(C_pDn2^D \log_+ (C_pDn2^D/\eta)\). Taking the union of these fixed-architecture nets over all pruned architectures gives a net for the full parameter space \(\mathsf{T}_{n,r}^{(D)}\). Equivalently, the covering number is bounded by the number of pruned architectures times the largest fixed-architecture covering number. Therefore, after absorbing constants into \(C_p\), \[\log N(\mathsf{T}_{n,r}^{(D)},\mathsf{d}_{R},\eta) \le C_pDn2^D(\log n+D) + C_pDn2^D \log_+\left(\frac{C_pDn2^D}{\eta}\right).\] The right-hand side is independent of \(r\), as claimed. ◻

Proof. By Proposition 5, we have \[\begin{align} \label{eq:varBoundExpectedSupResidual} \sigma_\infty^2 := \sup_{\theta \in \mathsf{T}_{n,r}^{(D)}} \operatorname{Var} ( R(\theta) ) \le C_p\frac{2^D}{n}. \end{align}\tag{5}\] By Dudley’s entropy integral, \[\mathbb{E}\sup_{\theta \in \mathsf{T}_{n,r}^{(D)}} |R (\theta)| \le C \int_0^{\operatorname{diam}(\mathsf{d}_R)} \sqrt{ \log N(\mathsf{T}_{n,r}^{(D)},\mathsf{d}_R,\eta) } d\eta \le C \int_0^{2\sigma_\infty} \sqrt{ \log N(\mathsf{T}_{n,r}^{(D)},\mathsf{d}_R,\eta) } d\eta ,\] since \(\operatorname{diam}(\mathsf{d}_R)\le 2\sigma_\infty\). The entropy estimate in Proposition 6 gives \[\mathbb{E}\sup_{\theta \in \mathsf{T}_{n,r}^{(D)}} |R (\theta)| \le C \int_0^{2\sigma_\infty} \sqrt{ C_pDn2^D(\log n+D) + C_pDn2^D \log_+\left(\frac{C_pDn2^D}{\eta}\right) } d\eta.\] Using the elementary bound \[\int_0^{2\sigma} \sqrt{ A+\log(2\sigma/\eta) } d\eta \le C\sigma\sqrt{A+1}, \qquad A\ge 0,\] together with 5 , we obtain \[\mathbb{E}\sup_{\theta \in \mathsf{T}_{n,r}^{(D)}} |R(\theta)| \le C_p \sigma_\infty \sqrt{Dn2^D(\log n+D)}.\] The claim follows by applying once more 5 : \[\sigma_\infty \sqrt{Dn2^D(\log n+D)} \le C_p \left(\frac{2^D}{n}\right)^{1/2} \sqrt{Dn2^D(\log n+D)} = C_p 2^D \sqrt{D(\log n+D)}.\] ◻

Proof. \(R\) is a centered Gaussian process indexed by \(\mathsf{T}_{n,r}^{(D)}\). Since the number of \(D\)-tuples of perfect matchings is finite, and since for fixed matchings the circuit class is a compact subset of a finite-dimensional parameter space, the process is separable. In what follows, the absolute value in the supremum is handled by the standard symmetrization of the index set, \(\mathsf{T}_{n,r}^{(D)}\mapsto \mathsf{T}_{n,r}^{(D)}\times\{-1,1\}\), which replaces \(R(\theta)\) by \(\pm R(\theta)\). This only changes covering numbers by a factor of \(2\), and is therefore absorbed into the constants below. We will henceforth abuse notation and continue to write \(\mathsf{T}_{n,r}^{(D)}\) for the resulting symmetrized index set. We now apply the Borell-TIS inequality, which states that if \(\{Z_t:t\in T\}\) is a centered separable Gaussian process with \(\sigma^2_T:=\sup_{t\in T}\operatorname{Var}(Z_t)<\infty\), then, for every \(u>0\), \[\mathbb{P}( \sup_{t\in T} Z_t \ge \mathbb{E}\sup_{t\in T}Z_t+u ) \le 2\exp\left( -\frac{u^2}{2\sigma_T^2} \right).\] Using Proposition 5, there exists \(A_p < \infty\) such that \(\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}\operatorname{Var}(R(\theta)) \le A_p2^D/n\). Therefore, for every \(u>0\), \[\mathbb{P}( \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} R(\theta) \ge \mathbb{E} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} R(\theta) +u ) \le 2\exp\left( -\frac{u^2}{ 2A_p2^D/n } \right).\]

Choosing \(u = B_p 2^{D} \sqrt{D(\log n+D)}\) with \(B_p > 0\), we have \[\frac{u^2}{2A_p2^D/n} = \frac{B_p^2}{2A_p} 2^D Dn(\log n+D).\] Setting \(c_p := B_p^2/(2A_p)\), we get that, with probability at least \(1-2\exp(-c_p 2^D Dn(\log n+D))\), \[\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} R(\theta) \le \mathbb{E} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} R(\theta) + B_p 2^{D} \sqrt{D(\log n+D)}.\] Combining this with Lemma 5 and increasing the constant \(C_p\) gives, with the same probability, \[\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} |R(\theta)| \le C_p 2^{D} \sqrt{D(\log n+D)}.\] ◻

Proof. The lower bound \(E_{n,r}^{(D_n)}(p)\ge E_{n,\mathrm{prod}}(p)\) follows because the depth-\(D_n\) class contains all physical product states. Indeed, let \(|\psi\rangle=\bigotimes_{i=1}^n|\psi^{(i)}\rangle\) be any product state on the physical qubits. Choose a first-layer matching on the \(n+r\) qubits. For each edge containing one or two physical qubits, choose the corresponding two-qubit unitary so that, starting from \(|00\rangle\), the physical output factor on each physical endpoint \(i\) is \(|\psi^{(i)}\rangle\). On edges containing no physical qubits, choose the identity. Choose all gates in layers \(\ell=2,\dots,D_n\) to be the identity. Then the reduced state on the first \(n\) physical qubits is \(\bigotimes_{i=1}^n|\psi^{(i)}\rangle\langle\psi^{(i)}|\). Hence every physical product-state energy is attainable inside \(\mathsf{S}_{n,r}^{(D_n)}\).

For the reverse bound, write \(\langle \phi_\theta|H_{n,p} \otimes I_{\mathrm{anc}}|\phi_\theta \rangle = X_0(\theta) + R(\theta)\). We first bound the supremum of the zeroth-order term. For \(x_1,\dots,x_n\in \mathbb{B}_2^3\), define the multilinear functional \[X_0(x_1,\dots,x_n) := \binom np^{-1/2} \sum_{I=\{i_1,\dots,i_p\}\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} g_{I,a} \prod_{s=1}^p x_{i_s}(a_s).\] For every depth-\(D_n\) state \(\phi\), its one-site Bloch vector \(m_i(\phi) :=(m_i^\phi(1),m_i^\phi(2),m_i^\phi(3))\) belongs to \(\mathbb{B}_2^3\), and by definition \(X_0(\phi) = X_0(m_1(\phi),\dots,m_n(\phi))\). Therefore \[\sup_{\theta \in \mathsf{T}_{n,r}^{(D_n)}} X_0(\theta) \le \sup_{x_1,\dots,x_n\in \mathbb{B}_2^3} X_0(x_1,\dots,x_n).\]

We claim that the last supremum is equal to the product-state optimum. Since \(X_0\) is multilinear and \((\mathbb{B}_2^3)^n\) is compact, the supremum is attained. Fixing all variables except \(x_i\), the map \(x_i\mapsto X_0(x_1,\dots,x_n)\) is linear on \(\mathbb{B}_2^3\). Hence, unless this linear functional is identically zero, its maximum over \(\mathbb{B}_2^3\) is attained on the sphere \(\mathcal{S}^2\). If it is identically zero, any choice of \(x_i\in \mathcal{S}^2\) is also optimal. Iterating this coordinate by coordinate, there is a maximizer with \(x_1,\dots,x_n\in \mathcal{S}^2.\) The points of \(\mathcal{S}^2\) are exactly the Bloch vectors of pure one-qubit states. Thus \[\frac{1}{\sqrt n} \sup_{x_1,\dots,x_n\in \mathbb{B}_2^3} X_0(x_1,\dots,x_n) = \frac{1}{\sqrt n} \sup_{\psi\in \mathsf{S}_{n,\mathrm{prod}}} \langle \psi|H_{n,p}|\psi\rangle = E_{n,\mathrm{prod}}(p).\] Consequently, \(\frac{1}{\sqrt{n}} \sup_{\theta \in \mathsf{T}_{n,r}^{(D_n)}} X_0(\theta) \le E_{n,\mathrm{prod}}(p)\).

It remains to control the residual. By Proposition 7, with probability tending to one, uniformly over \(r\) \[\frac{1}{\sqrt n} \sup_{\theta \in \mathsf{T}_{n,r}^{(D_n)}} | R(\theta) | \le C_p \sqrt{ \frac{4^{D_n}D_n(\log n+D_n)}{n} }.\] By assumption, \(4^{D_n}D_n(\log n+D_n)=o(n)\), and so the right-hand side is \(o_n(1)\) in probability. Hence \(E_{n,r}^{(D_n)}(p) \le E_{n,\mathrm{prod}}(p)+o_n(1)\) in probability, uniformly over \(r\). Combining this with the lower bound proves the first claim. ◻

Proof of Theorem 2, mean-field case. By Theorem 1, there exists a universal constant \(c>0\) such that, for every fixed \(p\ge3\), \(E_{n,\mathrm{gs}}(p) \ge c3^{p/2}/p\) with probability tending to one. On the other hand, by Theorem 1, for every \(\varepsilon>0\) and all sufficiently large \(p\), \(E_{n,\mathrm{prod}}(p) \le (1+\varepsilon)\sqrt{2\log p}\) with probability tending to one. Therefore, with probability tending to one, \[E_{n,\mathrm{gs}}(p)-E_{n,\mathrm{prod}}(p) \ge c\frac{3^{p/2}}{p} - (1+\varepsilon)\sqrt{2\log p}.\] Since \(3^{p/2}/p\gg\sqrt{\log p}\) as \(p\to\infty\), there exists \(p_0\ge3\) such that, for every fixed \(p\ge p_0\), the right-hand side is bounded below by \(2c_p\) for some \(c_p>0\). Thus, \(E_{n,\mathrm{gs}}(p)-E_{n,\mathrm{prod}}(p) \ge 2c_p\) with probability tending to one.

Choose \(\delta>0\) small enough that \(\delta<1/\log 4\). If \(D_n\le \delta\log n\), then \[4^{D_n}D_n(\log n+D_n) \le n^{\delta\log 4}\,\delta\log n\, (1+\delta)\log n = O_\delta\bigl(n^{\delta\log 4}(\log n)^2\bigr) = o(n).\] Therefore the hypothesis of Theorem 8 is satisfied. Hence \(E_{n,r}^{(D_n)}(p)-E_{n,\mathrm{prod}}(p)=o_n(1)\) in probability, uniformly over \(r\). Equivalently, for every \(\eta>0\), \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,r}^{(D_n)}(p)-E_{n,\mathrm{prod}}(p)>\eta \right) =0.\] Taking \(\eta= c_p,\) we have, with probability tending to one uniformly over \(r,\) \(E_{n,r}^{(D_n)}(p)-E_{n,\mathrm{prod}}(p) \le c_p .\)

Combining the two estimates gives \[\begin{align} E_{n,\mathrm{gs}}(p)-E_{n,r}^{(D_n)}(p) &= \left( E_{n,\mathrm{gs}}(p)-E_{n,\mathrm{prod}}(p) \right) - \left( E_{n,r}^{(D_n)}(p)-E_{n,\mathrm{prod}}(p) \right)\ge 2c_p - c_p = c_p, \end{align}\] with probability tending to one uniformly over \(r\). Equivalently, \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,\mathrm{gs}}(p)-E_{n,r}^{(D_n)}(p)<c_p \right) =0.\] ◻

Proof. Conditioned on the sparsification variables, the variance of the sparse residual process is \[\operatorname{Var}_g (R^{(\beta)}(\theta)\mid \xi) = \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n}\xi_I F_\theta(I), \qquad F_\theta(I):=\sum_{a\in\{1,2,3\}^p}|\chi_{I,a}(\theta)|^2.\] Thus we need to control the sparse average \(m_n^{-1} \sum_{I\in\mathcal{I}_p^n}\xi_I F_\theta(I)\) uniformly over \(\theta\in\mathsf{T}_{n,r}^{(D)}\).

We first record the mean and boundedness properties of \(F_\theta\). For the mean-field residual process, since the coefficients are independent Gaussians, we get \[\operatorname{Var}_g\bigl(R(\theta)\bigr) = \frac{1}{\binom np} \sum_{I\in\mathcal{I}_p^n} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 = \frac{1}{\binom np} \sum_{I\in\mathcal{I}_p^n} F_\theta(I).\] Therefore, by Proposition 5, \[\frac{1}{\binom np} \sum_{I\in\mathcal{I}_p^n} F_\theta(I) \le C_p\frac{2^D}{n}\] uniformly in \(\theta\in\mathsf{T}_{n,r}^{(D)}\). Also, \(0\le F_\theta(I)\le C_p\). To see this, note that for each \(a\), \[|\chi_{I,a}(\theta)| \le |\langle\phi_{\theta}|P_I^a\otimes I_{\mathrm{anc}}|\phi_{\theta}\rangle| + \big|\prod_{s=1}^p m_{i_s}^{\phi_\theta}(a_s)\big| \le 2,\] and there are \(3^p\) choices of \(a\).

The remaining issue is uniformity in \(\theta\). For each fixed \(\theta\), the quantity \(m_n^{-1}\sum_{I\in\mathcal{I}_p^n}\xi_I F_\theta(I)\) is a bounded Bernoulli average. We first apply Bernstein’s inequality, on a finite net of the circuit class. We then pass from the net to all \(\theta\in\mathsf{T}_{n,r}^{(D)}\) by proving a Lipschitz estimate for the coefficients \(F_\theta(I)\) with respect to the underlying circuit unitary.

Set \(\mathcal{J}_{n,D}:=C_pDn2^D(\log n+D)\), where \(C_p\) is chosen sufficiently large. The assumption is precisely \(\frac{2^D}{n}+\frac{\mathcal{J}_{n,D}}{m_n}=o(1),\) after changing the value of \(C_p\). Let \[\Lambda_{n,D} := \frac{2^D}{n} + \frac{\mathcal{J}_{n,D}}{m_n}.\] By assumption, \(\Lambda_{n,D}=o(1)\). We now construct a finite net using the same pruning and relabeling argument as in Proposition 6. Every circuit parameter \(\theta=(M_1,\dots,M_D,U)\in\mathsf{T}_{n,r}^{(D)}\) is equivalent, for all residual coefficients, to a pruned and relabeled circuit \(\widetilde{\theta} = (\widetilde{M}_1,\dots,\widetilde{M}_D,\widetilde{U})\) whose nonidentity gates act only on an active set of size at most \(n2^D\). In particular, \[\chi_{I,a}(\theta) = \chi_{I,a}(\widetilde{\theta}) \qquad \text{for all } I\in\mathcal{I}_p^n,\;a\in\{1,2,3\}^p .\] It is therefore enough to build a net for these pruned, relabeled circuits.

Let \(J_0:=Dn2^D\), which is an upper bound on the number of active two-qubit gate locations in a pruned depth-\(D\) circuit. For each fixed pruned architecture, take a \(\delta\)-net of \(U(4)\) in operator norm for each active gate location. By the usual telescoping bound for products of gates, if \(\delta=\frac{\Lambda_{n,D}}{C_pJ_0}\), then every pruned circuit \(\widetilde{U}\) has a representative \(U_0\) in the net such that \(\|\widetilde{U}-U_0\|_{\mathrm{op}}\le \Lambda_{n,D}\). The logarithm of the gate-net size for a fixed architecture is at most \(C_pJ_0\log(C_pJ_0/\Lambda_{n,D})\). The number of pruned architectures has logarithm at most \(C Dn2^D(\log n+D)\), again by the counting argument in Proposition 6. Since \(\Lambda_{n,D}\ge 2^D/n\), we have \[\log\left(\frac{C_pJ_0}{\Lambda_{n,D}}\right) \le \log(C_pD n^2) \le C(\log n+D),\] after increasing constants. Hence, after taking the union over pruned architectures, we obtain a finite net \(\mathcal{N}\) such that \(\log|\mathcal{N}| \le \mathcal{J}_{n,D}\), and every \(\theta\in\mathsf T_{n,r}^{(D)}\) has a pruned representative \(\widetilde{\theta}\) and a net point \(\theta_0\in\mathcal{N}\) satisfying \(\|\widetilde{U}-U_0\|_{\mathrm{op}}\le \Lambda_{n,D}\). The construction is independent of \(r\), because pruning removes all gates invisible to physical observables and the active ancillas are relabeled into a canonical block.

We now apply Bernstein’s inequality on the net. Fix \(\theta_0\in\mathcal{N}\). Since \(0\le F_{\theta_0}(I)\le C_p\) and \[\frac{1}{\binom np}\sum_{I\in\mathcal{I}_p^n}F_{\theta_0}(I) \le C_p\frac{2^D}{n},\] we have \[\mathbb{E}_\xi \bigg[ \frac{1}{m_n}\sum_{I\in\mathcal{I}_p^n}\xi_I F_{\theta_0}(I) \bigg] = \frac{1}{\binom np}\sum_{I\in\mathcal{I}_p^n}F_{\theta_0}(I) \le C_p\frac{2^D}{n}.\] Apply Bernstein’s inequality to the centered random variables \(Z_I := \xi_I F_{\theta_0}(I) - \mathbb{E}_\xi[\xi_I F_{\theta_0}(I)]\). Since \(0\le F_{\theta_0}(I)\le C_p\), we have \(|Z_I|\le C_p\). Moreover, \[\sum_{I\in\mathcal{I}_p^n}\mathbb{E}_\xi Z_I^2 \le \sum_{I\in\mathcal{I}_p^n} \mathbb{E}_\xi[\xi_I F_{\theta_0}(I)^2] \le C_p\kappa_n\sum_{I\in\mathcal{I}_p^n}F_{\theta_0}(I) \le C_p m_n\frac{2^D}{n}.\] Also, \[\mathbb{E}_\xi \sum_{I\in\mathcal{I}_p^n}\xi_I F_{\theta_0}(I) = \kappa_n\sum_{I\in\mathcal{I}_p^n}F_{\theta_0}(I) \le C_p m_n\frac{2^D}{n}.\] Therefore, applying Bernstein’s inequality with \(t=3\mathcal{J}_{n,D}\), we obtain \[\mathbb{P}_\xi \bigg( \frac{1}{m_n}\sum_{I\in\mathcal{I}_p^n}\xi_I F_{\theta_0}(I) > C_p\bigg[ \frac{2^D}{n} + \sqrt{ \frac{2^D}{n}\frac{\mathcal{J}_{n,D}}{m_n} } + \frac{\mathcal{J}_{n,D}}{m_n} \bigg] \bigg) \le \exp(-3\mathcal{J}_{n,D}).\] Since \[\sqrt{ \frac{2^D}{n}\frac{\mathcal{J}_{n,D}}{m_n} } \le \frac{1}{2}\frac{2^D}{n} + \frac{1}{2}\frac{\mathcal{J}_{n,D}}{m_n},\] we get \[\mathbb{P}_\xi\bigg( \frac{1}{m_n}\sum_{I\in\mathcal{I}_p^n}\xi_I F_{\theta_0}(I) > C_p\bigg[ \frac{2^D}{n} + \frac{\mathcal{J}_{n,D}}{m_n} \bigg] \bigg) \le \exp(-3\mathcal{J}_{n,D}).\] Taking a union bound over \(\mathcal{N}\), and using \(\log|\mathcal{N}|\le \mathcal{J}_{n,D}\), gives, with probability tending to one, \[\sup_{\theta_0\in\mathcal{N}} \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n}\xi_I F_{\theta_0}(I) \le C_p \left[ \frac{2^D}{n} + \frac{\mathcal{J}_{n,D}}{m_n} \right].\]

It remains to pass from the net to all of \(\mathsf{T}_{n,r}^{(D)}\). Since \(\mathcal{J}_{n,D}/m_n=o(1)\), we have \(m_n\to\infty\), and therefore \(|\mathcal{E}_p|\le 2m_n\) with probability tending to one. We work on the intersection of this event and the event on which the estimate in the previous display holds.

Let \(\theta\in\mathsf{T}_{n,r}^{(D)}\), let \(\widetilde{\theta}\) be its pruned and relabeled representative, and choose \(\theta_0\in\mathcal{N}\) in the same pruned architecture such that \(\|\widetilde{U}-U_0\|_{\mathrm{op}} \le \Lambda_{n,D}\). Since \(\chi_{I,a}(\theta)=\chi_{I,a}(\widetilde{\theta})\), it suffices to compare \(F_{\tilde{\theta}}(I)\) and \(F_{\theta_0}(I)\).

We claim that, for every \(I\in\mathcal{I}_p^n\), \(|F_{\tilde{\theta}}(I)-F_{\theta_0}(I)| \le C_p\Lambda_{n,D}\). To see this, note that for each label \(a\in\{1,2,3\}^p\), \[\big| \langle 0^{n+r}| \widetilde{U}^*(P_I^a\otimes I_{\mathrm{anc}})\widetilde{U} |0^{n+r}\rangle - \langle 0^{n+r}| U_0^*(P_I^a\otimes I_{\mathrm{anc}})U_0 |0^{n+r}\rangle \big| \le 2\|\widetilde{U}-U_0\|_{\mathrm{op}} \le 2\Lambda_{n,D},\] since \(\|P_I^a\otimes I_{\mathrm{anc}}\|_{\mathrm{op}}=1\). Similarly, for every physical one-site Pauli observable, \[|m_i^{\phi_{\tilde{\theta}}}(b)-m_i^{\phi_{\theta_0}}(b)| \le 2\|\widetilde{U}-U_0\|_{\mathrm{op}} \le 2\Lambda_{n,D}.\] Since all one-site means have absolute value at most \(1\), the product difference satisfies \[\big| \prod_{s=1}^p m_{i_s}^{\phi_{\tilde{\theta}}}(a_s) - \prod_{s=1}^p m_{i_s}^{\phi_{\theta_0}}(a_s) \big| \le C_p\Lambda_{n,D}.\] Therefore \(|\chi_{I,a}(\widetilde{\theta})-\chi_{I,a}(\theta_0)| \le C_p\Lambda_{n,D}\). Since \(|\chi_{I,a}(\widetilde{\theta})|\le2\) and \(|\chi_{I,a}(\theta_0)|\le2\), we also have \[\big| |\chi_{I,a}(\widetilde{\theta})|^2 - |\chi_{I,a}(\theta_0)|^2 \big | \le C_p\Lambda_{n,D}.\] Summing over the \(3^p\) labels \(a\) proves the claim.

Using \(\chi_{I,a}(\theta)=\chi_{I,a}(\widetilde{\theta})\), we get \[\frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n} \xi_I |F_{\theta}(I)-F_{\theta_0}(I)| = \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n} \xi_I |F_{\tilde{\theta}}(I)-F_{\theta_0}(I)| \le C_p\Lambda_{n,D}\frac{|\mathcal{E}_p|}{m_n} \le C_p\Lambda_{n,D}.\] Combining this with the net bound yields \[\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n}\xi_I F_\theta(I) \le C_p \left[ \frac{2^D}{n} + \frac{\mathcal{J}_{n,D}}{m_n} \right].\] Finally, since \[\operatorname{Var}_g ( R^{(\beta)}(\theta)\mid \xi ) = \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n} \xi_I F_\theta(I),\] the desired uniform variance bound follows. ◻

Proof. The proof is the same pruning and relabeling argument as in Proposition 6. We only record the changes caused by the sparsification.

Conditioned on the sparsification variables, the canonical metric is \[\mathsf{d}_\xi(\theta,\theta')^2 = \frac{1}{m_n} \sum_{I\in\mathcal{I}_p^n} \xi_I \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)-\chi_{I,a}(\theta')|^2 .\] By the coefficient Lipschitz estimate proved in Proposition 6, for every \(I\in\mathcal{I}_p^n\) and \(a\in\{1,2,3\}^p\), \[|\chi_{I,a}(\theta)-\chi_{I,a}(\theta')| \le C_p\|U-U'\|_{\mathrm{op}} .\] Therefore, on \(\mathsf E_{n,1}\), \[\mathsf{d}_\xi(\theta,\theta')^2 \le \frac{1}{m_n} \sum_{I\in\mathcal{E}_p} \sum_{a\in\{1,2,3\}^p} C_p\|U-U'\|_{\mathrm{op}}^2 \le C_p\|U-U'\|_{\mathrm{op}}^2.\] Hence \(\mathsf{d}_\xi(\theta,\theta') \le C_p\|U-U'\|_{\mathrm{op}}\).

The remainder of the proof follows exactly the covering argument from Proposition 6: after pruning to the joint backward support of the physical outputs and relabeling the active ancillas into a canonical block, the relevant circuits act on at most \(n2^D\) qubits. ◻

Proof. As in the proof of Proposition 7, the absolute value in the supremum is handled by symmetrizing the index set. This only changes covering numbers by a factor of \(2\), which is absorbed into the constants.

Fix \(r\in\mathbb{Z}_+\), and condition on a realization \(\xi\in\mathsf E_{n,r}\). Let \(\mathsf d_\xi\) denote the conditional canonical metric of the Gaussian process \(R^{(\beta)}\), conditioned on the sparsification variables \(\xi\). That is, for \(\theta,\theta'\in\mathsf{T}_{n,r}^{(D)}\), \[\mathsf{d}_\xi(\theta,\theta')^2 := \operatorname{Var}_g \left( R^{(\beta)}(\theta)-R^{(\beta)}(\theta') \mid \xi \right).\]

On \(\mathsf E_{n,1}\), Lemma 7 gives, for every \(\eta>0\), \[\log N(\mathsf{T}_{n,r}^{(D)},\mathsf{d}_\xi,\eta) \le C_pDn2^D(\log n+D) + C_pDn2^D \log_+\left( \frac{C_pDn2^D}{\eta} \right).\] Next, set \[\Lambda_{n,D} := \frac{2^D}{n} + \frac{Dn2^D(\log n+D)}{m_n}.\] On \(\mathsf E_{n,r}^{\mathrm{var}}\), \[\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} \operatorname{Var}_g \left( R^{(\beta)}(\theta)\mid \xi \right) \le C_p\Lambda_{n,D}.\] Therefore, \[\operatorname{diam}(\mathsf{T}_{n,r}^{(D)},\mathsf d_\xi) \le 2\left( \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} \operatorname{Var}_g(R^{(\beta)}(\theta)\mid\xi) \right)^{1/2} \le C_p\sqrt{\Lambda_{n,D}}.\]

Thus Dudley’s entropy integral gives \[\mathbb{E}_g \left[ \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}|R^{(\beta)}(\theta)| \,\big|\,\xi \right] \le C \int_0^{C_p\sqrt{\Lambda_{n,D}}} \sqrt{ C_pDn2^D(\log n+D) + C_pDn2^D \log_+\left( \frac{C_pDn2^D}{\eta} \right) } \,d\eta .\] Using the elementary entropy-integral bound from Lemma 5, together with \(\Lambda_{n,D}\ge 2^D/n\), we obtain \[\mathbb{E}_g \left[ \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}|R^{(\beta)}(\theta)| \,\big|\,\xi \right] \le C_p \sqrt{\Lambda_{n,D}}\, \sqrt{Dn2^D(\log n+D)}.\] Dividing by \(\sqrt n\) gives \[\mathbb{E}_g \bigg[ \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} |R^{(\beta)}(\theta)| \,\big | \, \xi \bigg] \le C_p \left\{ D2^D(\log n+D)\Lambda_{n,D} \right\}^{1/2}.\] Substituting the definition of \(\Lambda_{n,D}\) proves the claim. ◻

Proof. Let \(\mathsf E_{n,1}:=\{|\mathcal{E}_p|\le 2m_n\}\). For each \(r\in\mathbb{Z}_+\), let \(\mathsf E_{n,r}^{\mathrm{var}}\) and \(\mathsf E_{n,r}\) be the events defined in Lemma 8. That is, \(\mathsf E_{n,r} := \mathsf E_{n,1}\cap \mathsf E_{n,r}^{\mathrm{var}}\). We first claim that \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi(\mathsf E_{n,r}^c) =0.\] Indeed, \(|\mathcal{E}_p|=\sum_{I\in\mathcal{I}_p^n}\xi_I\), \(\mathbb{E}_\xi|\mathcal{E}_p|=m_n\), and \(m_n\to\infty\). Bernstein’s inequality gives \[\mathbb{P}_\xi(\mathsf E_{n,1}^c) = \mathbb{P}_\xi(|\mathcal{E}_p|>2m_n) \le \exp(-c m_n) = o(1).\] On the other hand, Lemma 6 gives \(\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi\left((\mathsf E_{n,r}^{\mathrm{var}})^c\right) =0\). Therefore \[\sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi(\mathsf E_{n,r}^c) \le \mathbb{P}_\xi(\mathsf E_{n,1}^c) + \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi\left((\mathsf E_{n,r}^{\mathrm{var}})^c\right) \to0.\]

On \(\mathsf E_{n,r}\), Lemma 8 gives \[\mathbb{E}_g \bigg[ \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D_n)}} |R^{(\beta)}(\theta)| \mid \xi \bigg] \le C_p \bigg\{ D_n2^{D_n}(\log n+D_n) \bigg[ \frac{2^{D_n}}{n} + \frac{D_n n 2^{D_n}(\log n+D_n)}{m_n} \bigg] \bigg\}^{1/2}.\] The right-hand side is \(o(1)\) by assumption.

Let \(\varepsilon>0\), and define \[A_{n,r} := \left\{ \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D_n)}} |R^{(\beta)}(\theta)| > \varepsilon \right\}.\] For every fixed \(r\), Markov’s inequality gives, on \(\mathsf E_{n,r}\), \[\mathbb{P}_g(A_{n,r}\mid \xi) \le \frac{C_p}{\varepsilon} \bigg( D_n2^{D_n}(\log n+D_n) \bigg[ \frac{2^{D_n}}{n} + \frac{D_n n 2^{D_n}(\log n+D_n)}{m_n} \bigg] \bigg)^{1/2}.\]

Consequently, for every \(r\in\mathbb{Z}_+\), \[\begin{align} \mathbb{P}_{\xi,g}(A_{n,r}) &\le \mathbb{P}_\xi(\mathsf E_{n,r}^c) + \mathbb{E}_\xi\left[ {\boldsymbol{1}}_{\mathsf E_{n,r}} \mathbb{P}_g(A_{n,r}\mid \xi) \right] \\ &\le \mathbb{P}_\xi(\mathsf E_{n,r}^c) + \frac{C_p}{\varepsilon} \left( D_n 2^{D_n}(\log n+D_n) \left[ \frac{2^{D_n}}{n} + \frac{D_n n2^{D_n}(\log n+D_n)}{m_n} \right] \right)^{1/2}. \end{align}\] Taking the supremum over \(r\in\mathbb{Z}_+\), we obtain \[\begin{align} \sup_{r\in\mathbb{Z}_+}\mathbb{P}_{\xi,g}(A_{n,r}) &\le \sup_{r\in\mathbb{Z}_+}\mathbb{P}_\xi(\mathsf E_{n,r}^c) + \frac{C_p}{\varepsilon} \left( D_n 2^{D_n}(\log n+D_n) \left[ \frac{2^{D_n}}{n} + \frac{D_n n2^{D_n}(\log n+D_n)}{m_n} \right] \right)^{1/2}. \end{align}\] The first term tends to zero by the preceding claim, and the second term tends to zero by the assumed depth condition. Hence \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_{\xi,g}\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D_n)}} |R^{(\beta)}(\theta)| > \varepsilon \right) =0,\] which proves the claim. ◻

Proof. The proof is identical to the mean-field depth-to-product comparison, Theorem 8, with the mean-field Hamiltonian \(H_{n,p}\) replaced by the sparse Hamiltonian \(H_{n,p}^{(\beta)}\). The zeroth-order term \(X_0^{(\beta)}\) is bounded by the sparse product-state optimum \(E_{n,\mathrm{prod}}^{(\beta)}(p)\) by the same multilinearity argument, while Lemma 9 gives \[\frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D_n)}} |R^{(\beta)}(\theta)| = o_n(1)\] in probability, uniformly over \(r\), under the stated depth condition. ◻

Proof of Theorem 2, growing-average-degree diluted case. By Corollary 1, the mean-field ground-state and product-state high-probability bounds transfer to the growing-average-degree diluted model. In particular, if \(c>0\) is the universal constant from Theorem 1, then for every \(\varepsilon>0\), \(E_{n,\mathrm{gs}}^{(\beta)}(p) \ge c3^{p/2}/p-\varepsilon\) with probability tending to one. Also, by the same corollary, for every \(\alpha>0\), for all sufficiently large fixed \(p\), and every \(\varepsilon>0\), \(E_{n,\mathrm{prod}}^{(\beta)}(p) \le (1+\alpha)\sqrt{2\log p}+\varepsilon\) with probability tending to one. Therefore, with probability tending to one, \[E_{n,\mathrm{gs}}^{(\beta)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) \ge c\frac{3^{p/2}}{p} - (1+\alpha)\sqrt{2\log p} - 2\varepsilon .\] Since \(3^{p/2}/p\gg\sqrt{\log p}\) as \(p\to\infty\), there exists \(p_0\ge3\) such that, for every fixed \(p\ge p_0\), we may choose \(\alpha>0\) and \(\varepsilon>0\) sufficiently small so that the right-hand side is bounded below by \(2c_p\) for some \(c_p>0\). Hence \(E_{n,\mathrm{gs}}^{(\beta)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) \ge 2c_p\) with probability tending to one.

Choose \(\delta_{p,\beta}>0\) small enough that \(\delta_{p,\beta} \log 4<\min\{1,p-\beta-1\}\). Since \(m_n = \Theta_p(n^{p-\beta})\), if \(D_n\le \delta_{p,\beta}\log n\), then \[\begin{align} & D_n2^{D_n}(\log n+D_n) \left[ \frac{2^{D_n}}{n} + \frac{D_n n2^{D_n}(\log n+D_n)}{m_n} \right] \\ &\qquad \le C_{p,\beta}(\log n)^2 n^{\delta_{p,\beta}\log 4-1} + C_{p,\beta}(\log n)^4 n^{\delta_{p,\beta}\log 4-(p-\beta-1)} = o(1). \end{align}\] Therefore the hypothesis of Theorem 9 is satisfied. Hence \(E_{n,r}^{(\beta, D_n)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) = o_n(1)\) in probability, uniformly over \(r\). Equivalently, for every \(\eta>0\), \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}( E_{n,r}^{(\beta, D_n)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) > \eta ) =0.\]

Combining the last two estimates yields \[\begin{align} E_{n,\mathrm{gs}}^{(\beta)}(p) - E_{n,r}^{(\beta, D_n)}(p) &= [ E_{n,\mathrm{gs}}^{(\beta)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) ] - [ E_{n,r}^{(\beta, D_n)}(p) - E_{n,\mathrm{prod}}^{(\beta)}(p) ] \\ &\ge 2c_p-o_n(1) \ge c_p \end{align}\] with probability tending to one, uniformly over \(r\). Therefore \[\lim_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}( E_{n,\mathrm{gs}}^{(\beta)}(p) - E_{n,r}^{(\beta, D_n)}(p) < c_p ) =0.\] This proves the theorem. ◻

Proof. First, \[|\mathcal{E}_p|=\sum_{I\in\mathcal{I}_p^n}\xi_I, \qquad \mathbb{E}_\xi|\mathcal{E}_p| = \zeta n^{-(p-1)}\binom np = \frac{\zeta}{p!}n(1+o_n(1)).\] Choosing \(C_p\) sufficiently large, Bernstein’s inequality gives constants \(c_p>0\) and \(n_0(p)<\infty\) such that, for all \(n\ge n_0(p)\), \[\mathbb{P}_\xi\left(|\mathcal{E}_p|>C_p\zeta n\right) \le \exp(-c_p\zeta n).\] Let \(\mathsf E_{n,0}\) denote the event on which \(|\mathcal{E}_p|\le C_p\zeta n\). On \(\mathsf E_{n,0}\), we have \[|E(Q)| \le \binom p2|\mathcal{E}_p| \le C_p\zeta n,\] after increasing \(C_p\).

Let \(K:=4^D\). Then, deterministically, \[|\{\mathsf G\subset Q:\Delta(\mathsf G)\le K\}| \le \prod_{v=1}^n \sum_{\ell=0}^K\binom{\deg_Q(v)}{\ell} \le \exp\left\{ K\sum_{v=1}^n\log(e+\deg_Q(v)) \right\}.\] By concavity of \(x\mapsto\log(e+x)\), \[\sum_{v=1}^n\log(e+\deg_Q(v)) \le n\log\left( e+\frac{2|E(Q)|}{n} \right).\] Hence, on \(\mathsf E_{n,0}\), \[|\{\mathsf G\subset Q:\Delta(\mathsf G)\le4^D\}| \le \exp\{C_{p,D}n\log(e+\zeta)\}.\]

It remains to prove the uniform bound on \(|\mathcal{B}(\mathsf G)|\). Fix a graph \(\mathsf G\) with \(\Delta(\mathsf G)\le4^D\). Then \(|E(\mathsf G)| \le 2^{2D-1}n\). Let \[\mathcal{I}_p(\mathsf G) := \{I\in\mathcal{I}_p^n: I\text{ contains at least one edge of }\mathsf G\}.\] By a union bound over edges of \(\mathsf G\), \[|\mathcal{I}_p(\mathsf G)| \le |E(\mathsf G)|\binom{n-2}{p-2} \le C_{p,D}n^{p-1}.\] It follows that \(|\mathcal{B}(\mathsf G)| = \sum_{I\in\mathcal{I}_p(\mathsf G)}\xi_I\) is stochastically dominated by a binomial random variable with parameters \(C_{p,D}n^{p-1}\) and \(\zeta n^{-(p-1)}\). In particular, \(\mathbb{E}|\mathcal{B}(\mathsf G)| \le C_{p,D}\zeta\).

We now make the constants in the union bound explicit. Let \[\mathfrak G_{n,D} := \left\{ ([n],E): E\subseteq \binom{[n]}{2}, \;\Delta([n],E)\le 4^D \right\}.\] Since every graph in \(\mathfrak G_{n,D}\) has at most \(2^{2D-1}n\) edges, there exists \(B_D<\infty\) such that \[|\mathfrak G_{n,D}| \le \sum_{q=0}^{\lfloor 2^{2D-1}n\rfloor} \binom{\binom n2}{q} \le \exp(B_Dn\log n)\] for all sufficiently large \(n\).

Set \(A_{p,D}:=2(B_D+2)\). For a fixed graph \(\mathsf G\), the standard binomial tail bound gives \[\begin{align} \mathbb{P}_\xi\left( |\mathcal{B}(\mathsf G)|>A_{p,D}n \right) &\le \left( \frac{eB_{p,D}\zeta}{A_{p,D}n} \right)^{A_{p,D}n}. \end{align}\] For each fixed \(\zeta\), there exists \(n_0(p,D,\zeta)<\infty\) such that, whenever \(n\ge n_0(p,D,\zeta)\), \[\frac{eB_{p,D}\zeta}{A_{p,D}n} \le n^{-1/2}.\] Consequently, \[\mathbb{P}_\xi\left( |\mathcal{B}(\mathsf G)|>A_{p,D}n \right) \le \exp\left( -\frac{A_{p,D}}{2}n\log n \right).\] Taking a union bound over all graphs of maximum degree at most \(4^D\) gives \[\mathbb{P}_\xi\left( \sup_{\mathsf G:\Delta(\mathsf G)\le4^D} |\mathcal{B}(\mathsf G)| > A_{p,D}n \right) \le \exp\left( B_Dn\log n - \frac{A_{p,D}}{2}n\log n \right) \le \exp(-2n\log n),\] where the last inequality follows from \(A_{p,D}/2=B_D+2\). In particular, the probability tends to zero, and is at most \(\exp(-2n)\) for all sufficiently large \(n\).

Finally, on the intersection of \(\mathsf E_{n,0}\) and the event \(\{ \sup_{\mathsf G:\Delta(\mathsf G)\le4^D} |\mathcal{B}(\mathsf G)| \le A_{p,D}n \}\), all three desired estimates hold simultaneously. Renaming \(A_{p,D}\) as \(C_{p,D}\), and increasing constants if necessary, completes the proof.

Indeed, for each fixed \(\zeta\), the probability that one of the three estimates fails is at most \[\exp(-c_p\zeta n)+\exp(-2n\log n) \le \exp(-c_{p,D,\zeta}n)\] for all sufficiently large \(n\), for some \(c_{p,D,\zeta}>0\). ◻

Proof. Conditioned on \(\xi=(\xi_I, I\in \mathcal{I}_p^n)\), \[\operatorname{Var}_g (R^{(\zeta)}(\theta)\mid\xi ) = \frac{1}{m_{n,\zeta}} \sum_{I\in\mathcal{I}_p^n} \xi_I \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 .\] For every \(I,a,\theta\), we have \[|\chi_{I,a}(\theta)| \le |\langle\phi_{\theta}|P_I^a \otimes I_{\mathrm{anc}}|\phi_{\theta} \rangle| + \big |\prod_{s=1}^p m^{\phi_\theta}_{i_s}(a_s)\big | \le 2.\] Therefore \[\sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)|^2 \le C_p .\] By Lemma 4, the coefficient \(\chi_{I,a}(\theta)\) can be nonzero only if \(I\in \mathcal{B}(\mathsf G_D^{\mathrm{dep}})\), that is, only if \(I\) contains at least one edge of \(\mathsf G_D^{\mathrm{dep}}\). Hence \[\operatorname{Var}_g (R^{(\zeta)}(\theta)\mid\xi ) \le C_p \frac{ |\mathcal{B}(\mathsf G_D^{\mathrm{dep}})| }{ m_{n,\zeta} }.\] By Lemma 3, \(\Delta(\mathsf G_D^{\mathrm{dep}}) \le 4^D\). Therefore Lemma 10 implies that, with probability tending to one, \[\sup_{\theta\in\mathsf{T}_{n,r}^{(D)}} \operatorname{Var}_g (R^{(\zeta)}(\theta)\mid\xi ) \le C_p \sup_{\mathsf G:\Delta(\mathsf G)\le4^D} \frac{|\mathcal{B}(\mathsf G)|}{m_{n,\zeta}} \le \frac{C_{p,D}}{\zeta} + o_n(1).\] This proves the claim. ◻

Proof. We work on a realization of the retained hypergraph for which the three estimates in Lemma 10 hold. This occurs with probability tending to one.

For an architecture \(M_1,\dots,M_D\), let \[\mathsf G_D^{\mathrm{dep}} = \mathsf G_D^{\mathrm{dep}}(M_1,\dots,M_D)\] be the associated dependency graph. We define the \(Q\)-restricted dependency graph associated with this architecture by \(\mathsf G_Q := \mathsf G_D^{\mathrm{dep}}\cap Q\), where the intersection is taken at the level of edge sets, so that \(E(\mathsf G_Q) = E(\mathsf G_D^{\mathrm{dep}})\cap E(Q)\). The set of retained hyperedges on which the residual coefficients may be nonzero depends only on this \(Q\)-restricted dependency graph. Indeed, if a retained hyperedge contains a pair \(\{i,j\}\in E(\mathsf G_D^{\mathrm{dep}})\), then, by the definition of \(Q\), the same pair also belongs to \(E(Q)\). Hence \[\mathcal{B}(\mathsf G_D^{\mathrm{dep}}) = \mathcal{B}(\mathsf G_D^{\mathrm{dep}}\cap Q) = \mathcal{B}(\mathsf G_Q).\] Moreover, by Lemma 3, \(\Delta(\mathsf G_D^{\mathrm{dep}})\le4^D\), and therefore \(\Delta(\mathsf G_Q)\le4^D\).

Thus the possible \(Q\)-restricted dependency graphs are contained in the class \(\{\mathsf G\subset Q:\Delta(\mathsf G)\le4^D\}\). By Lemma 10, the number of possible \(Q\)-restricted dependency graphs is at most \(\exp\{C_{p,D}n\log(e+\zeta)\}\).

Fix one graph \(\mathsf G\subset Q\) with \(\Delta(\mathsf G)\le4^D\). Again by Lemma 10, \(|\mathcal{B}(\mathsf G)|\le C_{p,D}n\). For each circuit parameter \(\theta\) whose \(Q\)-restricted dependency graph is \(\mathsf G\), define its active residual coefficient vector by \[r_{\mathsf G}(\theta) := \bigl(\chi_{I,a}(\theta)\bigr)_ {I\in\mathcal{B}(\mathsf G),a\in\{1,2,3\}^p}.\] By Lemma 4, all inactive coefficients vanish, that is, if \(I\notin\mathcal{B}(\mathsf G)\), then \(\chi_{I,a}(\theta)=0\) for every \(a\). Also \(|\chi_{I,a}(\theta)|\le2\), so \[r_{\mathsf G}(\theta)\in[-2,2]^{k_{\mathsf G}}, \qquad k_{\mathsf G}:=3^p|\mathcal{B}(\mathsf G)|\le C_{p,D}n .\]

We cover this cube in the scaled Euclidean metric \[d_{\mathsf G}(x,y)^2 := \frac{1}{m_{n,\zeta}} \sum_{I\in\mathcal{B}(\mathsf G)} \sum_{a\in\{1,2,3\}^p} |x_{I,a}-y_{I,a}|^2 .\] Since \(m_{n,\zeta} =\Theta( \zeta n)\), \(\zeta\ge1\), and \(k_{\mathsf G}\le C_{p,D}n\), the standard Euclidean cube covering bound gives a grid of cardinality at most \[\left(\frac{C_{p,D}}{\eta}\right)^{k_{\mathsf G}} \le \exp\left\{ C_{p,D}n \log_+\left(\frac{C_{p,D}}{\eta}\right) \right\}.\] Every active residual coefficient vector is within \(d_{\mathsf G}\)-distance \(\eta\) of some grid point. Keeping only the grid cells that intersect the set of realizable residual vectors, and choosing one circuit parameter from each such cell, gives a \(2\eta\)-net for the corresponding circuit parameters in the canonical metric.

Recall that the conditional canonical metric of the Gaussian process \(R^{(\zeta)}\), conditioned on \(\xi\), is \[\mathsf{d}_\xi(\theta,\theta')^2 := \operatorname{Var}_g \left( R^{(\zeta)}(\theta) - R^{(\zeta)}(\theta') \big| \xi \right).\] Since the Gaussian coefficients \(g_{I,a}\) are independent, this equals \[\mathsf{d}_\xi(\theta,\theta')^2 = \frac{1}{m_{n,\zeta}} \sum_{I\in\mathcal{I}_p^n} \xi_I \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)-\chi_{I,a}(\theta')|^2 .\] Now suppose that \(\theta\) and \(\theta'\) have the same \(Q\)-restricted dependency graph \(\mathsf G\). By Lemma 4, all residual coefficients outside \(\mathcal{B}(\mathsf G)\) vanish for both parameters. Therefore the preceding display reduces to \[\mathsf{d}_\xi(\theta,\theta')^2 = \frac{1}{m_{n,\zeta}} \sum_{I\in\mathcal{B}(\mathsf G)} \sum_{a\in\{1,2,3\}^p} |\chi_{I,a}(\theta)-\chi_{I,a}(\theta')|^2 .\] Thus, on a fixed \(Q\)-restricted dependency graph \(\mathsf G\), the conditional canonical metric is exactly the scaled Euclidean distance between the active residual coefficient vectors. Consequently the preceding cube net gives an \(O(\eta)\)-cover for all circuit parameters with fixed \(Q\)-restricted dependency graph \(\mathsf G\).

Finally, taking the union over all possible \(Q\)-restricted dependency graphs gives \[\log N(\mathsf{T}_{n,r}^{(D)},\mathsf{d}_\xi,\eta) \le C_{p,D} n \left[ \log(e+\zeta) + \log_+\left(\frac{C_{p,D}}{\eta}\right) \right],\] after adjusting constants. For \(\eta>1\), the same bound follows by monotonicity of covering numbers from the case \(\eta=1\), after increasing \(C_{p,D}\). ◻

Proof. Let \(A_{p,D}\) be the constant from Lemma 11. Applying that lemma with slack \(\zeta^{-1}\), we obtain \[\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi\left( \sup_{\theta\in\mathsf T_{n,r}^{(D)}} \operatorname{Var}_g\!\left(R^{(\zeta)}(\theta)\mid \xi\right) > \frac{A_{p,D}+1}{\zeta} \right) =0.\] Thus, after replacing \(A_{p,D}+1\) by \(C_{p,D}\), the event \[\mathsf E_{n,r}^{\mathrm{var}} := \left\{ \sup_{\theta\in\mathsf T_{n,r}^{(D)}} \operatorname{Var}_g\!\left(R^{(\zeta)}(\theta)\mid \xi\right) \le \frac{C_{p,D}}{\zeta} \right\}\] satisfies \(\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi\bigl((\mathsf E_{n,r}^{\mathrm{var}})^c\bigr)=0\).

Let \(\mathsf E_n^{\mathrm{ent}}\) be the event from Lemma 12. On this event, for every \(r\in\mathbb{Z}_+\) and every \(\eta>0\), \[\log N(\mathsf T_{n,r}^{(D)},\mathsf d_\xi,\eta) \le C_{p,D} n \left[ \log(e+\zeta) + \log_+\left(\frac{C_{p,D}}{\eta}\right) \right],\] and \(\mathbb{P}_\xi(\mathsf E_n^{\mathrm{ent}})\to1\). Set \(\mathsf E_{n,r}:=\mathsf E_n^{\mathrm{ent}} \cap \mathsf E_{n,r}^{\mathrm{var}}\). Then \(\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_\xi(\mathsf E_{n,r}^c)=0\).

Fix \(r\in\mathbb{Z}_+\), and condition on a realization \(\xi\in\mathsf E_{n,r}\). Let \(\mathsf d_\xi\) be the conditional canonical metric of \(R^{(\zeta)}\). On \(\mathsf E_{n,r}\), \[\operatorname{diam}(\mathsf T_{n,r}^{(D)},\mathsf d_\xi) \le 2 \left( \sup_{\theta\in\mathsf T_{n,r}^{(D)}} \operatorname{Var}_g(R^{(\zeta)}(\theta)\mid \xi) \right)^{1/2} \le C_{p,D}\zeta^{-1/2}.\]

We first bound the conditional mean. The absolute value in the supremum is handled by symmetrizing the index set, which only changes the entropy by an additive constant. Dudley’s entropy integral gives \[\mathbb{E}_g\big[ \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| \,\big|\,\xi \big] \le C \int_0^{C_{p,D}\zeta^{-1/2}} \sqrt{ C_{p,D} n \left[ \log(e+\zeta) + \log_+\left(\frac{C_{p,D}}{\eta}\right) \right] } \,d\eta .\] Using \[\int_0^\sigma \sqrt{A+\log_+(C/\eta)}\,d\eta \le C'\sigma\sqrt{A+\log(e+C/\sigma)+1},\] with \(\sigma=C_{p,D}\zeta^{-1/2}\) and \(A=\log(e+\zeta)\), we obtain \[\mathbb{E}_g\big[ \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| \,\big|\,\xi \big] \le C_{p,D} \sqrt{\frac{\log(e+\zeta)}{\zeta}}.\]

Now define \(Z_\theta:=\frac{1}{\sqrt n}R^{(\zeta)}(\theta)\). On \(\mathsf E_{n,r}\), \[\sup_{\theta\in\mathsf T_{n,r}^{(D)}} \operatorname{Var}_g(Z_\theta\mid \xi) \le \frac{C_{p,D}}{\zeta n}.\] By Borell–TIS, conditionally on \(\xi\in\mathsf E_{n,r}\), for every \(t>0\), \[\mathbb{P}_g\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| > C_{p,D} \sqrt{\frac{\log(e+\zeta)}{\zeta}} + t \,\big|\,\xi \right) \le 2\exp\left(-c_{p,D}\zeta n t^2\right).\] Taking \(t=\varepsilon\), we get \[\mathbb{P}_g\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| > C_{p,D} \sqrt{\frac{\log(e+\zeta)}{\zeta}} + \varepsilon \,\big|\,\xi \right) \le 2\exp\left(-c_{p,D}\zeta n\varepsilon^2\right).\]

Therefore, for every \(r\in\mathbb{Z}_+\), \[\mathbb{P}_{\xi,g}\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| > C_{p,D} \sqrt{\frac{\log(e+\zeta)}{\zeta}} + \varepsilon \right) \le \mathbb{P}_\xi(\mathsf E_{n,r}^c) + 2\exp\left(-c_{p,D}\zeta n\varepsilon^2\right).\] Taking the supremum over \(r\in\mathbb{Z}_+\) and then \(\limsup_{n\to\infty}\) gives \[\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}_{\xi,g}\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| > C_{p,D} \sqrt{\frac{\log(e+\zeta)}{\zeta}} + \varepsilon \right) =0.\] This proves the claim. ◻

Proof. The lower bound \(E_{n,r}^{(\zeta,D)}(p) \ge E_{n,\mathrm{prod}}^{(\zeta)}(p)\) holds because the depth-\(D\) circuit class contains all product states.

For the reverse bound, let \(\theta\in\mathsf{T}_{n,r}^{(D)}\), with \(\phi_\theta=U|0^{n+r}\rangle\). By the residual decomposition, \[\langle\phi_\theta|H_{n,p}^{(\zeta)} \otimes I_{\mathrm{anc}}|\phi_\theta\rangle = X_0^{(\zeta)}(\theta) + R^{(\zeta)}(\theta).\] Taking suprema over \(\theta\in\mathsf{T}_{n,r}^{(D)}\) gives \[E_{n,r}^{(\zeta,D)}(p) \le \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}X_0^{(\zeta)}(\theta) + \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}|R^{(\zeta)}(\theta)|.\] Arguing exactly as in the mean-field case proof in Theorem 8, the zeroth-order term is bounded by the product-state optimum, \[\frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}X_0^{(\zeta)}(\theta) \le E_{n,\mathrm{prod}}^{(\zeta)}(p).\] Consequently, \[0\le E_{n,r}^{(\zeta,D)}(p) - E_{n,\mathrm{prod}}^{(\zeta)}(p) \le \frac{1}{\sqrt n} \sup_{\theta\in\mathsf{T}_{n,r}^{(D)}}|R^{(\zeta)}(\theta)|.\] By Lemma 13, for every \(\gamma>0\), \[\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)| > C_{p,D}\sqrt{\frac{\log(e+\zeta)}{\zeta}} +\gamma \right) =0.\] Using \[0\le E_{n,r}^{(\zeta,D)}(p) - E_{n,\mathrm{prod}}^{(\zeta)}(p) \le \frac{1}{\sqrt n} \sup_{\theta\in\mathsf T_{n,r}^{(D)}} |R^{(\zeta)}(\theta)|,\] we obtain, for every \(\gamma>0\), \[\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,r}^{(\zeta,D)}(p) - E_{n,\mathrm{prod}}^{(\zeta)}(p) > C_{p,D}\sqrt{\frac{\log(e+\zeta)}{\zeta}} +\gamma \right) =0.\] Now fix \(\varepsilon>0\). Choose \(\zeta\) sufficiently large that \(C_{p,D}\sqrt{\frac{\log(e+\zeta)}{\zeta}} < \frac{\varepsilon}{2}\). Taking \(\gamma=\varepsilon/2\), we get \[\limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,r}^{(\zeta,D)}(p) - E_{n,\mathrm{prod}}^{(\zeta)}(p) > \varepsilon \right) =0\] for all sufficiently large \(\zeta\). Therefore \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,r}^{(\zeta,D)}(p) - E_{n,\mathrm{prod}}^{(\zeta)}(p) > \varepsilon \right) =0.\] ◻

Proof of Theorem 3. Let \(c>0\) be the universal constant from Theorem 1. By Corollary 1, for every \(\varepsilon>0\), \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \mathbb{P}\left( E_{n,\mathrm{gs}}^{(\zeta)}(p) < c\frac{3^{p/2}}{p}-\varepsilon \right) =0.\] Also, by the same corollary, for every \(\delta>0\), for all sufficiently large fixed \(p\), and every \(\varepsilon>0\), \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \mathbb{P}( E_{n,\mathrm{prod}}^{(\zeta)}(p) > (1+\delta)\sqrt{2\log p}+\varepsilon ) =0.\]

By Theorem 10, for every fixed \(D\ge1\) and every \(\varepsilon>0\), \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}( E_{n,r}^{(\zeta,D)}(p) > E_{n,\mathrm{prod}}^{(\zeta)}(p)+\varepsilon) =0.\] Combining the last two estimates by a union bound gives \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}( E_{n,r}^{(\zeta,D)}(p) > (1+\delta)\sqrt{2\log p}+2\varepsilon ) =0.\]

Therefore, another union bound gives \[\lim_{\zeta\to\infty} \limsup_{n\to\infty} \sup_{r\in\mathbb{Z}_+} \mathbb{P}\left( E_{n,\mathrm{gs}}^{(\zeta)}(p) - E_{n,r}^{(\zeta,D)}(p) < c\frac{3^{p/2}}{p} - (1+\delta)\sqrt{2\log p} - 3\varepsilon \right) =0.\] Since \(3^{p/2}/p\gg \sqrt{\log p}\) as \(p\to\infty\), there exists \(p_0\ge3\) such that, for every fixed \(p\ge p_0\), we may choose \(\delta>0\) and \(\varepsilon>0\) sufficiently small so that \[c\frac{3^{p/2}}{p} - (1+\delta)\sqrt{2\log p} - 3\varepsilon \ge 2c_p\] for some \(c_p>0\). Reducing \(c_p\) if necessary, we obtain the result. ◻