$\displaystyle\overset{a}{=}\text{Re}\Big{\\{}\sum_{x\in\mathcal{X}}\text{Q}_{\text{X}}(x)\langle\partial_{i}\phi_{x}(\boldsymbol{\theta})|\partial_{j}\phi_{x}(\boldsymbol{\theta})\rangle-\sum_{x_{1},x_{2}}\text{Q}_{\text{X}}(x_{1})\text{Q}_{\text{X}}(x_{2})\langle\partial_{i}\phi_{x_{1}}(\boldsymbol{\theta})|\phi_{x_{1}}(\boldsymbol{\theta})\rangle\langle\phi_{x_{2}}(\boldsymbol{\theta})|\partial_{j}\phi_{x_{2}}(\boldsymbol{\theta})\rangle\Big{\\}}$
$\displaystyle\overset{b}{=}\Re{\Tr(\frac{\partial
U^{\dagger}(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}_{i}}\frac{\partial
U(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}_{j}}\rho)-\Tr(\frac{\partial
U^{\dagger}(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}_{i}}U(\boldsymbol{\theta})\rho)\Tr(U^{\dagger}(\boldsymbol{\theta})\frac{\partial
U(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}_{j}}\rho)}$
$\displaystyle=\Re{\Tr(\Upsilon_{i}(\boldsymbol{\theta})\Upsilon_{j}(\boldsymbol{\theta})\rho)-\Tr(\Upsilon_{i}(\boldsymbol{\theta})\rho)\Tr(\Upsilon_{j}(\boldsymbol{\theta})\rho)},$
(37)

where in $(a)$, the real part appears from the fact that
$d\boldsymbol{\theta}_{i}d\boldsymbol{\theta}_{j}$ occurs twice in the
summation but with the conjugated terms and $(b)$ follows from the cyclicity
of trace. This completes the proof of Theorem 1.

###  -D Derivation of the $\mathcal{F}^{\mathcal{E}}$ expression for the QNN
Model discussed in Section II.

Consider the parameterized unitary of the $\mathsf{a}^{\text{th}}$ hidden
layer,
$U_{\mathsf{a}}(\boldsymbol{\theta}_{\mathsf{a}})=\bigotimes_{p=1}^{d}R_{\sigma^{\mathsf{a}}_{\mathsf{p}}}(\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p})})$.
Recalling the notation from Sec. II, the derivative of
$W_{\mathsf{a}}(\boldsymbol{\theta}_{\mathsf{a}})$ with respect to
$\mathsf{p}^{\text{th}}$ qubit parameter can be expressed as:

$\partial_{\mathsf{a_{p}}}W_{\mathsf{a}}(\boldsymbol{\theta}_{\mathsf{a}}):=\frac{\partial
W_{\mathsf{a}}(\boldsymbol{\theta}_{\mathsf{a}})}{\partial{\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p})}}}=-\frac{i}{2}W_{\mathsf{a}}(\boldsymbol{\theta}_{\mathsf{a}})(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]}).$

Further, the derivative of $U(\boldsymbol{\theta})$ can be written as:

$\displaystyle\partial_{\mathsf{a_{p}}}U(\boldsymbol{\theta}):=\frac{\partial
U(\boldsymbol{\theta})}{\partial{\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p})}}}$
$\displaystyle=-\frac{i}{2}W_{[L:\mathsf{a}]}(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})W_{(\mathsf{a}:1]},$
(38)

Using (38), we compute the elements of the E-QFIM corresponding to the
($\mathsf{a}^{\text{th}}$ layer, $\mathsf{p}^{\text{th}}$ qubit) parameter and
($\mathsf{b}^{\text{th}}$ layer, $\mathsf{q}^{\text{th}}$ qubit) parameter.
Consider the second term of $\mathcal{F}^{\mathcal{E}}$ (see (15)).

$\displaystyle\Tr\\{(\partial_{\mathsf{a_{p}}}U^{\dagger}(\boldsymbol{\theta}))U(\boldsymbol{\theta})\rho\\}\Tr\\{U^{\dagger}(\boldsymbol{\theta})(\partial_{\mathsf{b_{q}}}U(\boldsymbol{\theta}))\rho\\}$
$\displaystyle=0.25\\!\cdot\\!\Tr\\{W_{[1:\mathsf{a})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})W_{[\mathsf{a}:L]}^{\dagger}W_{[L:1]}\rho\\}\Tr\\{W_{[1:L]}^{\dagger}W_{[L:\mathsf{b}]}(\mathbb{I}^{\otimes[1:\mathsf{q})}\otimes\sigma^{\mathsf{b}}_{\mathsf{q}}\otimes\mathbb{I}^{\otimes(\mathsf{q}:d]})W_{(\mathsf{b}:1]}\rho\\}$
$\displaystyle=0.25\\!\cdot\\!\Tr\\{W_{[1:\mathsf{a})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})W_{(\mathsf{a}:1]}\rho\\}\Tr\\{W_{[1:\mathsf{b})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{q})}\otimes\sigma^{\mathsf{b}}_{\mathsf{q}}\otimes\mathbb{I}^{\otimes(\mathsf{q}:d]})W_{(\mathsf{b}:1]}\rho\\}$
$\displaystyle=\Tr\\{G_{\mathsf{a_{p}}}\rho\\}\Tr\\{G_{\mathsf{b_{q}}}\rho\\}.$
(39)

To compute the first term of (15), without loss of generality, assume
$\mathsf{a}\leq\mathsf{b}$. Thus, we get

$\displaystyle\Re{\Tr((\partial_{\mathsf{a_{p}}}U^{\dagger}(\boldsymbol{\theta}))(\partial_{\mathsf{b_{q}}}U(\boldsymbol{\theta}))\rho)}$
$\displaystyle=0.25\cdot\Re{\Tr(W_{[1:\mathsf{a})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})W_{[\mathsf{a}:\mathsf{b})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{q})}\otimes\sigma^{\mathsf{b}}_{\mathsf{q}}\otimes\mathbb{I}^{\otimes(\mathsf{q}:d]})W_{(\mathsf{b}:1]}\rho)}$
$\displaystyle=0.25\cdot\Re{\Tr(W_{[1:\mathsf{a})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})W_{(\mathsf{a}:1]}W_{[1:\mathsf{b})}^{\dagger}(\mathbb{I}^{\otimes[1:\mathsf{q})}\otimes\sigma^{\mathsf{b}}_{\mathsf{q}}\otimes\mathbb{I}^{\otimes(\mathsf{q}:d]})W_{(\mathsf{b}:1]}\rho)}$
$\displaystyle=\Re{\Tr(G_{\mathsf{a_{p}}}G_{\mathsf{b_{q}}}\rho)}=\frac{1}{2}\Tr(\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}\rho),$
(40)

where the last equality follows from the cyclicity of the trace. Combining
these expressions, the E-QFIM takes the form:
$\mathcal{F}_{(\mathsf{a_{p}},\mathsf{b_{q}})}(\boldsymbol{\theta})=\operatorname*{Cov}(G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}})_{\rho}.$

###  -E Proof of Lemma 2.

Using the cyclicity of trace, we rewrite the expectation of
$\\{\mathbf{A},\mathbf{B}\\}$ with respect to the state $|\phi\rangle$ as
follows:

$\displaystyle\vspace{-10pt}\expectationvalue{\\{\mathbf{A},\mathbf{B}\\}}{\phi}$
$\displaystyle=\Tr(\\{\mathbf{A},\mathbf{B}\\}\Phi)=\Tr(\mathbf{B}\Phi\mathbf{A}+\mathbf{B}\mathbf{A}\Phi)=\Tr(\\{\mathbf{A},\Phi\\}\mathbf{B}).$
(41)

Suppose $A$ is a random variable denoting the measurement outcome of
$\mathcal{M}=\\{\mathbf{A}_{+},\mathbf{A}_{-}\\}$ on the state $|\phi\rangle$.
The probability of obtaining outcome $1$, i.e.,
$\mathbb{P}\\{A=1\\}=\Tr(\mathbf{A}_{+}\Phi)$. Similarly,
$\mathbb{P}\\{A=-1\\}=\Tr(\mathbf{A}_{-}\Phi)$. Then, we decompose the anit-
commutator $\\{\mathbf{A},\Phi\\}$ in terms of $\mathbf{A}_{+}\text{ and
}\mathbf{A}_{-}$ as follows:

$\displaystyle\\{\mathbf{A},\Phi\\}=\mathbf{A}\Phi I+I\Phi\mathbf{A}$
$\displaystyle\overset{a}{=}(\mathbf{A}_{+}-\mathbf{A}_{-})\Phi(\mathbf{A}_{+}+\mathbf{A}_{-})+(\mathbf{A}_{+}+\mathbf{A}_{-})\Phi(\mathbf{A}_{+}-\mathbf{A}_{-})$
$\displaystyle=2[\mathbf{A}_{+}\Phi\mathbf{A}_{+}-\mathbf{A}_{-}\Phi\mathbf{A}_{-}]$
$\displaystyle=2[\mathbb{P}\\{A=1\\}\Phi(\mathbf{A}_{+})-\mathbb{P}\\{A=-1\\}\Phi(\mathbf{A}_{-})],$

where $(a)$ follows from the facts that the Hermitian matrix has orthonormal
eigenvectors for distinct eigenvalues and $\mathbf{A}^{2}=\mathbb{I}$. Here,
$\Phi(\mathbf{A}_{+})\text{ and }\Phi(\mathbf{A}_{-})$ denote the post-
measurement state when we measure outcomes $+1\text{ and }-1$, respectively.
Subsequently, let $B$ be the random variable denoting the measurement outcome
of the post-measurement state along the eigenvectors of $\mathbf{B}$. Then,

$\displaystyle\frac{1}{2}\Tr(\\{\mathbf{A},\Phi\\}\mathbf{B})$
$\displaystyle=\mathbb{P}\\{A=1\\}\Tr(\mathbf{B}\Phi(\mathbf{A}_{+}))-\mathbb{P}\\{A=-1\\}\Tr(\mathbf{B}\Phi(\mathbf{A}_{-}))$
$\displaystyle=\mathbb{P}\\{A=1\\}\mathbb{E}[AB|A=1]+\mathbb{P}\\{A=-1\\}\mathbb{E}[AB|A=-1]=\mathbb{E}[AB].$
(42)

Hence, from (41) and (42), we get
$\expectationvalue{\\{\mathbf{A},\mathbf{B}\\}}{\phi}=2\cdot\mathbb{E}[AB]$.
This completes the proof of Lemma 2.

###  -F Proof of Lemma 3.

Let $|\phi_{x}^{a}\rangle:=W_{(\mathsf{a}:1]}\ket{\phi_{x}}$ denote the input
state to the $\mathsf{a}^{\text{th}}$ layer of the PQC. We denote
$\Sigma^{\mathsf{a}}_{\mathsf{p}}:=(\mathbb{I}^{\otimes[1:\mathsf{p})}\otimes\sigma^{\mathsf{a}}_{\mathsf{p}}\otimes\mathbb{I}^{\otimes(\mathsf{p}:d]})$
and
$\Sigma^{\mathsf{b}}_{\mathsf{q}}:=(\mathbb{I}^{\otimes[1:\mathsf{q})}\otimes\sigma^{\mathsf{b}}_{\mathsf{q}}\otimes\mathbb{I}^{\otimes(\mathsf{q}:d]})$.
We first compute the expectation of diagonal entries. Observe that
$\mathbb{E}[v_{i}||\phi_{x_{i}}\rangle]=\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
\Phi^{\mathsf{b}}_{x_{i}})$ for $i={1,2}$. For $z_{22}$,

$\displaystyle\mathbb{E}[z_{22}]=\mathbb{E}[0.25\cdot(1-v_{1}v_{2})]$
$\displaystyle\overset{a}{=}0.25\cdot(1-\mathbb{E}_{X_{1}}[\mathbb{E}[v_{1}||\phi_{x_{1}}\rangle]]\mathbb{E}_{X_{2}}[\mathbb{E}[v_{2}||\phi_{x_{2}}\rangle]])$
$\displaystyle=0.25\cdot(1-\mathbb{E}_{X_{1}}[\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
\Phi^{\mathsf{b}}_{x_{1}})]\mathbb{E}_{X_{2}}[\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
\Phi^{\mathsf{b}}_{x_{2}})])$
$\displaystyle=0.25-0.25[\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:1]}\rho
W^{\dagger}_{[1:\mathsf{b})})]^{2}=0.25-[\Tr(G_{\mathsf{b_{q}}}\rho)]^{2},$

where $(a)$ follows because $|\phi_{x_{1}}\rangle\text{ and
}|\phi_{x_{2}}\rangle$ are i.i.d. samples. This gives the desired result for
$z_{22}$. Next, we note that the structure of the pair $(v_{1},v_{2})$ is
exactly the same as that of $(u_{1},u_{2})$ with the correspondence
$\mathsf{a_{p}}\leftrightarrow\mathsf{b_{q}}$. Hence, for
$z_{11}=0.25\cdot(1-u_{1}u_{2})$, we get
$\mathbb{E}[z_{11}]=0.25-\Tr(G_{\mathsf{a_{p}}}\rho)^{2}$.

Finally, we compute the expectation of off-diagonal entries. Recall the
definition of Hermitian operators $G_{\mathsf{a_{p}}}\text{ and
}G_{\mathsf{b_{q}}}$, then consider the following set of equalities:

$\displaystyle\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}$
$\displaystyle=G_{\mathsf{a_{p}}}G_{\mathsf{b_{q}}}+G_{\mathsf{b_{q}}}G_{\mathsf{a_{p}}}$
$\displaystyle=0.25\cdot(W_{[1:\mathsf{a})}^{\dagger}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{(\mathsf{a}:1]}W_{[1:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:1]}+W_{[1:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:1]}W_{[1:\mathsf{a})}^{\dagger}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{(\mathsf{a}:1]})$
$\displaystyle=0.25\cdot(W_{[1:\mathsf{a})}^{\dagger}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{[\mathsf{a}:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:1]}+W_{[1:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{(\mathsf{a}:1]}).$

Using the above expansion of $\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}$ and
cyclicity of trace, we get

$\displaystyle\expectationvalue{\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}}{\phi_{x}}$
$\displaystyle=\Tr(\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}\Phi_{x})$
$\displaystyle=0.25\cdot\Tr(\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{[\mathsf{a}:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:1]}\Phi_{x}\
W_{[1:\mathsf{a})}^{\dagger})+\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{(\mathsf{a}:1]}\Phi_{x}\ W_{[1:\mathsf{b})}^{\dagger})$
$\displaystyle\overset{a}{=}0.25\cdot\Tr(\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{[\mathsf{a}:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\Phi^{\mathsf{a}}_{x})+\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\ \Sigma^{\mathsf{a}}_{\mathsf{p}}\
\Phi^{\mathsf{a}}_{x}\ W_{[\mathsf{a}:\mathsf{b})}^{\dagger})$
$\displaystyle=0.25\cdot\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\Phi^{\mathsf{a}}_{x}\
\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{[\mathsf{a}:\mathsf{b})}^{\dagger})+\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\ \Sigma^{\mathsf{a}}_{\mathsf{p}}\
\Phi^{\mathsf{a}}_{x}\ W_{[\mathsf{a}:\mathsf{b})}^{\dagger})$
$\displaystyle=0.25\cdot\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\\{\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathsf{a}}_{x}\\}W_{[\mathsf{a}:\mathsf{b})}^{\dagger}),$
(43)

where $(a)$ follows from the definition $\Phi_{x}^{a}$. Using the following
facts: (i) $\Sigma^{\mathsf{a}}_{\mathsf{p}}$ is Hermitian, (ii)
$(\Sigma^{\mathsf{a}}_{\mathsf{p}})^{2}=\mathbb{I}$, (iii)
$\Tr(\\{\mathbf{A},\mathbf{B}\\}\Phi)=\Tr(\mathbf{B}\\{\mathbf{A},\Phi\\})$,
and Lemma 2, we can write

$\mathbb{E}[u_{i}w_{i}||\phi_{x_{i+2}}\rangle]=0.5\cdot\Tr(W_{[\mathsf{a}:\mathsf{b})}^{\dagger}\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\\{\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathbf{a}}_{x_{i+2}}\\}),$
(44)

for $i=1,2$, where we used the Heisenberg picture of quantum measurements:
$\Tr(\Lambda U\rho U^{\dagger})=\Tr(U^{\dagger}\Lambda U\rho)$, where
$\Lambda$ and $U$ represent a measurement and unitary operator, respectively
[SN20]. Now, we are equipped to compute the expectation of the off-diagonal
entries. For $z_{12}=z_{21}$,

$\displaystyle\mathbb{E}[z_{12}]$
$\displaystyle=0.125\cdot\mathbb{E}[u_{1}w_{1}+u_{2}w_{2}]-0.0625\cdot\mathbb{E}\left[(u_{1}+u_{2})(v_{1}+v_{2})\right]$
$\displaystyle\overset{a}{=}0.125\cdot\big{(}\mathbb{E}_{X_{3}}[\mathbb{E}[u_{1}w_{1}||\phi_{x_{3}}\rangle]]+\mathbb{E}_{X_{4}}[\mathbb{E}[u_{2}w_{2}||\phi_{x_{4}}\rangle]]\big{)}-\Tr(G_{\mathsf{a_{p}}}\rho)\Tr(G_{\mathsf{b_{q}}}\rho)$
$\displaystyle\overset{b}{=}0.0625\cdot\big{(}\mathbb{E}_{X_{3}}[\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\\{\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathsf{a}}_{x_{3}}\\}W_{[\mathsf{a}:\mathsf{b})}^{\dagger})]+\mathbb{E}_{X_{4}}[\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\\{\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathsf{a}}_{x_{4}}\\}W_{[\mathsf{a}:\mathsf{b})}^{\dagger})]\big{)}$
$\displaystyle\hskip
247.88556pt-\Tr(G_{\mathsf{a_{p}}}\rho)\Tr(G_{\mathsf{b_{q}}}\rho)$
$\displaystyle\overset{c}{=}0.125\cdot\Tr(\Sigma^{\mathsf{b}}_{\mathsf{q}}\
W_{(\mathsf{b}:\mathsf{a}]}\\{\Sigma^{\mathsf{a}}_{\mathsf{p}},\rho^{\mathsf{a}}\\}W_{[\mathsf{a}:\mathsf{b})}^{\dagger})-\Tr(G_{\mathsf{a_{p}}}\rho)\Tr(G_{\mathsf{b_{q}}}\rho)$
$\displaystyle\overset{d}{=}0.5\cdot\Tr(\\{G_{\mathsf{a_{p}}},G_{\mathsf{b_{q}}}\\}\rho)-\Tr(G_{\mathsf{a_{p}}}\rho)\Tr(G_{\mathsf{b_{q}}}\rho),$

where $(a)$ follows because
$|\phi_{x_{1}}\rangle|\phi_{x_{2}}\rangle,|\phi_{x_{3}}\rangle,\text{ and
}|\phi_{x_{4}}\rangle$ are i.i.d. samples and the analysis of $z_{11},z_{22}$,
$(b)$ follows from (44), $(c)$ follows by defining
$\rho^{\mathsf{a}}:=W_{(\mathsf{a}:1]}\rho W^{\dagger}_{[1:\mathsf{a})}$, and
$(d)$ follows from (43). This completes the proof of Lemma 3.

###  -G Proof of Theorem 2.

Without loss of generality, assume $\mathsf{a}\leq\mathsf{b}$. Consider the
following equalities:

$\displaystyle\mathbb{E}[\bar{\mathbf{Z}}{(\mathsf{a_{p}},\mathsf{b_{q}})}]=\frac{c(c-1)}{2}\mathbb{E}\left[\tilde{\mathbf{Z}}(\mathsf{a_{p}},\mathsf{b_{q}})-\frac{2\beta}{c}\mathbb{I}\right]\overset{a}{=}\frac{1}{2}\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\mathbb{E}\left[\tilde{\mathbf{Z}}{(\mathsf{a_{p}},\mathsf{b_{q}})}\right]-(c-1)\beta\mathbb{I}\quad\quad$
$\displaystyle\overset{b}{=}\frac{1}{2}\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\left[\begin{array}[]{cccccccccccc}0_{\ddots}&&&&&&&&\\\
&0&&&&&&&\\\
&&\frac{1}{(c-1)}\mathcal{F}^{\mathcal{E}}_{(\mathsf{a_{p}},\mathsf{a_{p}})}+\beta&0&\ldots&0&\mathcal{F}^{\mathcal{E}}_{(\mathsf{a_{p}},\mathsf{b_{q}})}&&\\\
&&0&0&\ldots&0&0&&\\\ &&\vdots&\vdots&\ddots&\vdots&\vdots&&\\\
&&0&0&\ldots&0&0&&\\\
&&\mathcal{F}^{\mathcal{E}}_{(\mathsf{b_{q}},\mathsf{a_{p}})}&0&\ldots&0&\frac{1}{(c-1)}\mathcal{F}^{\mathcal{E}}_{(\mathsf{b_{q}},\mathsf{b_{q}})}+\beta&&\\\
&&&&&&&0_{\ddots}&\\\ &&&&&&&&0\end{array}\right]-(c-1)\beta\mathbb{I}$ (54)
$\displaystyle\overset{c}{=}\frac{1}{2}(2\mathcal{F}^{\mathcal{E}}+2(c-1)\beta\mathbb{I})-(c-1)\beta\mathbb{I}=\mathcal{F}^{\mathcal{E}},$

where $(a)$ follows by taking the expectation over the random pair of
coordinates $(\mathsf{a_{p}},\mathsf{b_{q}})$, $(b)$ follows from Lemma 3, and
$(c)$ follows by expanding the summation and noting the following arguments.
The non-zero off-diagonal terms arise in the summation only twice, whereas the
non-zero diagonal terms appear in the summation $2(c\\!-\\!1)$ times. This
completes the proof of Theorem 2.

###  -H Derivation of the Gradient of Per-Sample Expected Loss.

Recall, from (38), the derivative of $U(\boldsymbol{\theta})$ with respect to
the ($\mathsf{a}^{\text{th}}$ layer, $\mathsf{p}^{\text{th}}$ qubit) parameter
$\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p})}$ is given as:

$\displaystyle\partial_{\mathsf{a_{p}}}U(\boldsymbol{\theta}):=\frac{\partial
U(\boldsymbol{\theta})}{\partial{\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p})}}}$
$\displaystyle=-\frac{i}{2}W_{[L:\mathsf{a}]}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W_{(\mathsf{a}:1]}.$

Using the above derivative, compute the following expression:

$\displaystyle(\partial_{\mathsf{a_{p}}}U(\boldsymbol{\theta}))\Phi_{x}U^{\dagger}(\boldsymbol{\theta})+U(\boldsymbol{\theta})\Phi_{x}(\partial_{\mathsf{a_{p}}}U^{\dagger}(\boldsymbol{\theta}))$
$\displaystyle=-\frac{i}{2}W_{[L:\mathsf{a}]}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
\Phi^{\mathsf{a}}_{x}W^{\dagger}_{[\mathsf{a}:L]}+\frac{i}{2}W_{[L:\mathsf{a}]}\Phi^{\mathsf{a}}_{x}\Sigma^{\mathsf{a}}_{\mathsf{p}}\
W^{\dagger}_{[\mathsf{a}:L]}$
$\displaystyle=-\frac{i}{2}W_{[L:\mathsf{a}]}[\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathsf{a}}_{x}]W^{\dagger}_{[\mathsf{a}:L]}.$
(55)

Thus, using (55), the gradient of per-sample expected loss can be written as:

$\displaystyle\frac{\partial\mathcal{L}(\boldsymbol{\theta},|\phi\rangle,y)}{\partial\boldsymbol{\theta}_{(\mathsf{a},\mathsf{p}))}}$
$\displaystyle=\sum_{\hat{y}\in\mathcal{Y}}\ell(y,\hat{y})\Tr\\{\Lambda_{\hat{y}}((\partial_{\mathsf{a_{p}}}U(\boldsymbol{\theta}))\Phi
U^{\dagger}(\boldsymbol{\theta})+U(\boldsymbol{\theta})\Phi(\partial_{\mathsf{a_{p}}}U^{\dagger}(\boldsymbol{\theta})))\\}$
$\displaystyle=\sum_{\hat{y}\in\mathcal{Y}}-\frac{i}{2}\ell(y,\hat{y})\Tr\\{\Lambda_{\hat{y}}W_{[L:\mathsf{a}]}[\Sigma^{\mathsf{a}}_{\mathsf{p}},\Phi^{\mathsf{a}}_{x}]W^{\dagger}_{[\mathsf{a}:L]}\\}.$
(56)

This completes the derivation.

###  -I Proof of Lemma 4.

We first prove the following lemma.

######  Lemma 5.

Consider a Hermitian operator $\mathbf{A}$ on $\mathcal{H}^{d}$, such that
$\mathbf{A}^{2}=\mathbb{I}$. Then, for any operator $\Phi$ on
$\mathcal{H}^{d}$ the following holds:

$[\mathbf{A},\Phi]=i(e^{-i\pi\mathbf{A}/4}\ \Phi\
e^{i\pi\mathbf{A}/4}-e^{i\pi\mathbf{A}/4}\ \Phi\ e^{-i\pi\mathbf{A}/4}).$

###### Proof.

The proof follows from [MNKF18]. However, for convenience, we provide a
succinct proof below. With the definition of $\mathbf{A}$, note that
$\mathbf{A}^{2}=\mathbb{I}$. Therefore, using Taylor expansion, we have,

$e^{i\beta\mathbf{A}}=\cos(\beta)\mathbb{I}+i\sin(\beta)\mathbf{A}\ \text{ for
all }\beta\in[0,2\pi).$

Next, we simplify the following expression:

$\displaystyle i(e^{-i\pi\mathbf{A}/4}\ \Phi\
e^{i\pi\mathbf{A}/4}-e^{i\pi\mathbf{A}/4}\ \Phi\ e^{-i\pi\mathbf{A}/4})$
$\displaystyle=\frac{i}{2}\big{(}(\mathbb{I}-i\mathbf{A})\Phi(\mathbb{I}+i\mathbf{A})-(\mathbb{I}+i\mathbf{A})\Phi(\mathbb{I}-i\mathbf{A})\big{)}=[\mathbf{A},\Phi].$

This completes the proof of Lemma 5. ∎

With the intention of employing the above lemma and considering the definition
of $\mathbf{V}$, we have

$\displaystyle\mathbf{V}(\Phi\otimes\outerproduct{+}{+})\mathbf{V}^{\dagger}$
$\displaystyle=\frac{1}{2}\big{(}e^{i\pi\mathbf{A}/4}\ \Phi\
e^{-i\pi\mathbf{A}/4}\otimes|0\rangle\langle 0|+e^{i\pi\mathbf{A}/4}\ \Phi\
e^{i\pi\mathbf{A}/4}\otimes|0\rangle\langle 1|$ $\displaystyle\hskip
72.26999pt+e^{-i\pi\mathbf{A}/4}\ \Phi\
e^{-i\pi\mathbf{A}/4}\otimes|1\rangle\langle 0|+e^{-i\pi\mathbf{A}/4}\ \Phi\
e^{i\pi\mathbf{A}/4}\otimes|1\rangle\langle 1|\big{)}.$

Next, using the above expression, we compute the following expectation:

$\displaystyle
2i\langle\tilde{\phi}|{\mathbf{V}^{\dagger}O\mathbf{V}}|\tilde{\phi}\rangle=2i\Tr\\{O\mathbf{V}\tilde{\Phi}\mathbf{V}^{\dagger}\\}$
$\displaystyle=i\big{(}\Tr\\{\mathbf{B}e^{i\pi\mathbf{A}/4}\ \Phi\
e^{-i\pi\mathbf{A}/4}-\mathbf{B}e^{-i\pi\mathbf{A}/4}\ \Phi\
e^{i\pi\mathbf{A}/4}\\}\big{)}$
$\displaystyle\overset{a}{=}\Tr\\{\mathbf{B}[\Phi,\mathbf{A}]\\}\overset{b}{=}\expectationvalue{[\mathbf{A},\mathbf{B}]}{\phi},$

where $(a)$ follows from Lemma 5 and $(b)$ follows from the cyclicity of
trace. This completes the proof of Lemma 4.

###  -J Proof of Proposition 1.

Without loss of generality, assume $\mathsf{a}<\mathsf{b}$. Next, consider the
following inequalities:

$\displaystyle\mathbb{E}[\mathbf{g}{(\mathsf{a_{p}},\mathsf{b_{q}})}]$
$\displaystyle=\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\frac{1}{c(c-1)}\mathbb{E}\left[\frac{c}{2}(g_{\mathsf{a_{p}}}\mathbf{e}_{\mathsf{a_{p}}}+g_{\mathsf{b_{q}}}\mathbf{e}_{\mathsf{b_{q}}})\right]$
$\displaystyle=\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\frac{1}{2(c-1)}\big{(}\mathbb{E}_{\text{Q}_{\text{XY}}}\big{[}\mathbb{E}[g_{\mathsf{a_{p}}}||\phi_{x_{1}}\rangle,y_{1}]\big{]}\mathbf{e}_{\mathsf{a_{p}}}+\mathbb{E}_{\text{Q}_{\text{XY}}}\big{[}\mathbb{E}[g_{\mathsf{b_{q}}}||\phi_{x_{2}}\rangle,y_{2}]\big{]}\mathbf{e}_{\mathsf{b_{q}}}\big{)}$
$\displaystyle\overset{a}{=}\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\frac{1}{2(c-1)}\big{(}\mathbb{E}_{\text{Q}_{\text{XY}}}[\nabla\mathcal{L}_{\mathsf{a_{p}}}(|\phi_{x_{1}}\rangle,y_{1})]\mathbf{e}_{\mathsf{a_{p}}}+\mathbb{E}_{\text{Q}_{\text{XY}}}[\nabla\mathcal{L}_{\mathsf{b_{q}}}(|\phi_{x_{2}}\rangle,y_{2})]\mathbf{e}_{\mathsf{b_{q}}}\big{)}$
$\displaystyle=\sum_{\mathsf{a_{p}}\neq\mathsf{b_{q}}}\frac{1}{2(c-1)}\big{(}\nabla\mathcal{L}_{\mathsf{a_{p}}}\mathbf{e}_{\mathsf{a_{p}}}+\nabla\mathcal{L}_{\mathsf{b_{q}}}\mathbf{e}_{\mathsf{b_{q}}}\big{)}=\nabla\mathcal{L},$

where $(a)$ follows from the construction of $g_{\mathsf{a_{p}}}\text{ and
}g_{\mathsf{b_{q}}}$.

###  -K Proof of Theorem 3.

We begin with considering Assumption 1 and using the update rule (23).
Consider the following inequalities:

$\displaystyle\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t}+1)})$
$\displaystyle\overset{}{\leq}\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\eta\nabla\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})^{\texttt{T}}\big{|}\bar{\mathbf{Z}}^{\texttt{t}}{(i,j)}\big{|}^{-1}\mathbf{g}^{\texttt{t}}(i,j)+\eta^{2}\frac{\mathsf{L}_{2}}{2}\big{\|}|\bar{\mathbf{Z}}^{\texttt{t}}{(i,j)}|^{-1}\mathbf{g}^{\texttt{t}}(i,j)\big{\|}^{2}$
$\displaystyle\overset{}{=}\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\frac{\beta}{(c\\!-\\!1)\mathsf{L}_{2}}\nabla\mathcal{L}^{\texttt{t}}(i,j)^{\texttt{T}}\Big{|}\tilde{\mathbf{Z}}^{\texttt{t}}(i,j)-\frac{2\beta}{c}\mathbb{I}\Big{|}^{-1}(g_{i}^{\texttt{t}}\mathbf{e}_{i}+g_{j}^{\texttt{t}}\mathbf{e}_{j})$
$\displaystyle\hskip
187.90244pt+\frac{\beta^{2}}{2(c\\!-\\!1)^{2}\mathsf{L}_{2}}\big{\|}|\tilde{\mathbf{Z}}_{[i,j]}^{\texttt{t}}-(2\beta/c)\mathbb{I}_{2}|^{-1}[g_{i}^{\texttt{t}},g_{j}^{\texttt{t}}]\big{\|}^{2},$

where
$\nabla\mathcal{L}^{\texttt{t}}(i,j):=(\nabla\mathcal{L}_{i}(\boldsymbol{\theta}^{(\texttt{t})})\
\mathbf{e}_{i}+\nabla\mathcal{L}_{j}(\boldsymbol{\theta}^{(\texttt{t})})\
\mathbf{e}_{j})$. After taking the expectation of both sides with respect to
$\tilde{\mathbf{Z}}_{[\text{I},\text{J}]}^{\texttt{t}},g_{\text{I}}^{\texttt{t}},g_{\text{J}}^{\texttt{t}}$
conditioned on all estimates from previous iterations, we get

$\displaystyle\mathbb{E}_{(g_{\text{I}}^{\texttt{t}},\
g_{\text{J}}^{\texttt{t}},\tilde{\mathbf{Z}}_{[\text{I},\text{J}]}^{\texttt{t}})}$
$\displaystyle[\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t}+1)})]$
$\displaystyle\overset{}{\leq}\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\frac{\beta}{(c\\!-\\!1)\mathsf{L}_{2}}\underbrace{\sum_{i\neq
j}\frac{1}{c(c-1)}\nabla\mathcal{L}^{\texttt{t}}(i,j)^{\texttt{T}}\mathbb{E}\bigg{[}\Big{|}\tilde{\mathbf{Z}}^{\texttt{t}}(i,j)-\frac{2\beta}{c}\mathbb{I}\Big{|}^{-1}(g_{i}^{\texttt{t}}\mathbf{e}_{i}+g_{j}^{\texttt{t}}\mathbf{e}_{j})\bigg{]}}_{\text{T}_{1}}$
$\displaystyle\hskip
79.49744pt+\frac{\beta^{2}}{2(c\\!-\\!1)^{2}\mathsf{L}_{2}}\underbrace{\sum_{i\neq
j}\frac{1}{c(c-1)}\mathbb{E}\big{[}\||\tilde{\mathbf{Z}}_{[i,j]}^{\texttt{t}}-(2\beta/c)\mathbb{I}_{2}|^{-1}[g_{i}^{\texttt{t}},g_{j}^{\texttt{t}}]\|^{2}\big{]}}_{\text{T}_{2}}.$
(57)

Now, we simplify the term $\text{T}_{2}$ as:

$\displaystyle\text{T}_{2}$ $\displaystyle\leq\sum_{i\neq
j}\frac{1}{c(c-1)}\mathbb{E}\big{[}\||\tilde{\mathbf{Z}}^{\texttt{t}}_{[i,j]}-(2\beta/c)\mathbb{I}_{2}|^{-1}\|^{2}\big{]}\mathbb{E}[\|[g_{i}^{\texttt{t}},g_{j}^{\texttt{t}}]\|^{2}]\leq\sum_{i\neq
j}\frac{1}{c(c-1)}{\alpha^{2}}=\alpha^{2},$

where the first inequality follows from the definition of the spectral norm
and the fact that independent quantum samples are used to construct
$\tilde{\mathbf{Z}}_{[i,j]},g_{i},\text{ and }g_{j}$, and the second
inequality follows by defining
$\alpha^{2}=\max_{(i,j)}\mathbb{E}\big{[}\||\tilde{\mathbf{Z}}_{[i,j]}^{\texttt{t}}-(2\beta/c)\mathbb{I}_{2}|^{-1}\|^{2}\big{]}\mathbb{E}[\|[g_{i}^{\texttt{t}},g_{j}^{\texttt{t}}]\|^{2}]$
and considering the following arguments. From Remark 1, there exists a
$\beta>0$ for every $c>0$ such that the $2\times 2$ matrix
$(\tilde{\mathbf{Z}}_{[i,j]}^{(\texttt{t})}-({2\beta}/{c})\mathbb{I}_{2})$ has
positive eigenvalues for all possible measurements outcomes. Moreover, given a
set of measurement outcomes, the eigenvalues of this $2\times 2$ sub-matrix
eventually saturate to a value independent of $c$ and solely dependent on
$\beta>0$. This occurs because, as $c$ increases, the diagonal entries of this
$2\times 2$ matrix are predominantly governed by $\beta$. Therefore, the
spectral norm of the inverse of this $2\times 2$ sub-matrix, i.e., the inverse
of its minimum eigenvalue, is bounded. Furthermore, for a bounded loss
function $\ell(y,\hat{y})$, the partial derivative estimators
$g^{\texttt{t}}_{i}\text{ and }g^{\texttt{t}}_{j}$ are also bounded. This
implies the product of the expectation of these estimators is also bounded.

On a similar note, we can rewrite $\text{T}_{1}$ as:

$\displaystyle\text{T}_{1}$ $\displaystyle\overset{}{=}\sum_{i\neq
j}\frac{1}{c(c-1)}{\nabla\mathcal{L}^{\texttt{t}}(i,j)}^{\texttt{T}}\mathbb{E}\Big{[}\Big{|}\tilde{\mathbf{Z}}^{\texttt{t}}(i,j)-\frac{2\beta}{c}\mathbb{I}\Big{|}^{-1}\Big{]}\nabla\mathcal{L}^{\texttt{t}}(i,j)$
$\displaystyle\overset{a}{\geq}\sum_{i\neq
j}\frac{1}{c(c-1)}{\nabla\mathcal{L}^{\texttt{t}}(i,j)}^{\texttt{T}}\Big{(}\mathbb{E}\Big{[}\Big{|}\tilde{\mathbf{Z}}^{\texttt{t}}(i,j)-\frac{2\beta}{c}\mathbb{I}\Big{|}\Big{]}\Big{)}^{\\!-1}\nabla\mathcal{L}^{\texttt{t}}(i,j)$
$\displaystyle\overset{b}{=}\sum_{i\neq
j}\frac{1}{c(c-1)}\nabla\mathcal{L}(\boldsymbol{\theta}^{(t)})^{\texttt{T}}_{[i,j]}\left(\tilde{\mathcal{F}}^{\mathcal{E}}{(i,j)}+\frac{2\beta}{c}\mathbb{I}\right)^{-1}\nabla\mathcal{L}(\boldsymbol{\theta}^{(t)})_{[i,j]}$
$\displaystyle\overset{c}{\geq}\Bigg{(}\sum_{i\neq
j}\frac{1}{c(c-1)}\nabla\mathcal{L}^{\texttt{t}}(i,j)\Bigg{)}^{\\!\\!\texttt{T}}\\!\\!\Bigg{(}\sum_{i\neq
j}\frac{1}{c(c-1)}\left(\tilde{\mathcal{F}}^{\mathcal{E}}{(i,j)}+\frac{2\beta}{c}\mathbb{I}\right)\Bigg{)}^{\\!\\!-1}\\!\\!\Bigg{(}\sum_{i\neq
j}\frac{1}{c(c-1)}\nabla\mathcal{L}^{\texttt{t}}(i,j)\Bigg{)}$
$\displaystyle=\frac{4}{c^{2}}\nabla\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})^{\texttt{T}}\Bigg{(}\frac{2}{c(c-1)}\mathcal{F}^{\mathcal{E}}(\boldsymbol{\theta})+\frac{4(c-2)}{c^{2}}\beta\mathbb{I}\Bigg{)}^{-1}\nabla\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})$
$\displaystyle\overset{d}{\geq}\frac{8\bar{\mu}}{c^{2}}(\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\mathcal{L}(\boldsymbol{\theta}^{\star})).$

In the above inequalities, $(a)$ follows because the inverse is a convex
operator function over the space of positive definite operator [Nor11], $(b)$
follows from Remark 1 and by defining
$\tilde{\mathcal{F}}^{\mathcal{E}}{(i,j)}:=\mathbb{E}[\tilde{\mathbf{Z}}^{\texttt{t}}(i,j)]-\big{(}\frac{4\beta}{c}\big{)}\mathbb{I}(i,j)$,
where $\mathbb{I}(i,j)$ is a projection operator with all zero elements except
at diagonals corresponding to coordinates $i\text{ and }j$, $(c)$ follows from
Keifer inequality [Kie59, Lemma 3.2], and $(d)$ follows from Assumption 2.
After putting the value of $\text{T}_{1}\text{ and }\text{T}_{2}$ in (57) and
taking expectation with respect to all estimates from previous iterations, we
get

$\displaystyle\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t}+1)})-\mathcal{L}(\boldsymbol{\theta}^{\star})]$
$\displaystyle\overset{}{\leq}\bigg{(}1-\frac{8\bar{\mu}\beta}{c^{2}(c\\!-\\!1)\mathsf{L}_{2}}\bigg{)}\mathbb{E}[(\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\mathcal{L}(\boldsymbol{\theta}^{\star}))]+\frac{\alpha^{2}\beta^{2}}{2(c\\!-\\!1)^{2}\mathsf{L}_{2}}$

Finally, applying this inequality recursively, we get

$\displaystyle\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\mathcal{L}(\boldsymbol{\theta}^{\star})]$
$\displaystyle\overset{}{\leq}\bigg{(}1-\frac{8\bar{\mu}\beta}{c^{2}(c\\!-\\!1)\mathsf{L}_{2}}\bigg{)}^{\texttt{t}}(\mathcal{L}(\boldsymbol{\theta}^{(0)})-\mathcal{L}(\boldsymbol{\theta}^{\star}))+\frac{\alpha^{2}\beta^{2}}{2(c\\!-\\!1)^{2}\mathsf{L}_{2}}\sum_{k=0}^{\texttt{t}-1}\Big{(}1-\frac{8\bar{\mu}}{c^{2}(c\\!-\\!1)\mathsf{L}_{2}}\Big{)}^{k}$
$\displaystyle\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}^{(\texttt{t})})-\mathcal{L}(\boldsymbol{\theta}^{\star})]$
$\displaystyle\overset{}{\leq}\bigg{(}1-\frac{8\bar{\mu}\beta}{c^{3}\mathsf{L}_{2}}\bigg{)}^{\texttt{t}}(\mathcal{L}(\boldsymbol{\theta}^{(0)})-\mathcal{L}(\boldsymbol{\theta}^{\star}))+\frac{c}{8\bar{\mu}}\alpha^{2}\beta^{2}.$

This completes the proof of Theorem 3.

###  -L Supplementary Information for Section V.

Regularization constant $\beta$: We choose $\beta$ by empirically assessing
the positive definiteness of $2\times 2$ sub-matrix $\bar{\mathbf{Z}}_{[i,j]}$
for all possible cases of measurement outcomes. If $\beta>0.643$ for $c=9$,
$\beta>0.572$ for $c=16$, $\beta>0.536$ for $c=30$, $\beta>0.5295$ for $c=36$,
and $\beta>0.5218$ for $c=48$, we observe the sub-matrix
$\bar{\mathbf{Z}}_{[i,j]}$ is positive definite for all possible measurement
outcomes. Therefore, we chose a sufficiently small value for $\beta$ that is
close, but not too close, to the threshold.

The regularization constant $\beta$ is a hyper-parameter to trade off
numerical instabilities for the faithful E-QFIM estimation. A small $\beta$
leads to a faster convergence, while a larger $\beta$ aligns the update closer
to the RQSGD approach. However, using a significantly small $\beta$, closer to
the threshold, leads to large noisy oscillations in the 2-QNSCD loss function
due to numerical instabilities in the inversion of $\bar{\mathbf{Z}}_{[i,j]}$.
Figure 5 shows the 3Q Exp2 example (from Fig.4) for different values of
$\beta$ and illustrates how the different values of $\beta$ impacts the
performance of 2-QNSCD. As $\beta$ increases, 2-QNSCD approaches the
performance of 6-RQSGD and then the 2-RQSGD.

Figure 5: Performance of 2-QNSCD with 3-Qubit for different regularization
constant $\beta$.

PQC considered in Figure 4: The PQC for three qubits configuration is shown
below. The parameters are represented using the following convention:
$\omega_{i}=\boldsymbol{\theta}_{(i/d,i\%d)}$, where $d$ is the number of
qubits, $i/d$ represents the integer (floor) division of $i$ by $d$, and
$i\%d$ ($i$ modulo $d$) gives the remainder of $i$ divided by $d$.

[column sep=0.3cm] & R_Y(ω_0) 1  R_Y(ω_3) 1  R_Y(ω_6) 1
R_Y(ω_1) 1 R_Y(ω_4) 1 R_Y(ω_7) 1
R_Y(ω_2)  R_Y(ω_5)  R_Y(ω_8)

  *[QML]: quantum machine learning
  *[i.i.d.]: independent and identically distributed
  *[SGD]: stochastic gradient descent


# A Possible Quantum Gravity Hint in Binary Black Hole Merger

Parthasarathi Majumdar<EMAIL_ADDRESS>School of Physical Sciences, Indian
Association for the Cultivation of Science, Kolkata 700032, India.

###### Abstract

We present a semi-rigorous justification of Bekenstein’s Generalized Second
Law of Thermodynamics applicable to a universe with black holes present, based
on a generic quantum gravity formulation of a black hole spacetime, where the
bulk Hamiltonian constraint plays a central role. Specializing to Loop Quantum
Gravity, and considering the inspiral and post-ringdown stages of binary black
hole merger into a remnant black hole, we show that the Generalized Second Law
implies a lower bound on the non-perturbative LQG correction to the
Bekenstein-Hawking area law for black hole entropy. This lower bound itself is
expressed as a function of the Bekenstein-Hawking area formula for entropy.
Results of the analyses of LIGO-VIRGO-KAGRA data recently performed to verify
the Hawking Area Theorem for binary black hole merger are shown to be entirely
consistent with this Loop Quantum Gravity-induced inequality. However, the
consistency is independent of the magnitude of the LQG corrections to black
hole entropy, depending only on the negative algebraic sign of the quantum
correction. We argue that results of alternative quantum gravity computations
of quantum black hole entropy, where the quantum entropy exceeds the
Bekenstein-Hawking value, may not share this consistency.

##  I Introduction

It is a consensus view that GW150914 and subsequent similar observations by
the LIGO consortium pertain to binary black hole (BBH) mergers to a black hole
remnant LIGO1 -LIGO7 . To reinforce this standpoint, several research groups
bad18 -bad22  have recently sought to investigate the validity of Hawking’s
theorem haw71  on the impossibility of decrease of the area of black hole
horizons in any physical process, by more detailed analyses of the data on BBH
coalescence. Recall that this theorem, as well as the other Laws of Black Hole
Mechanics bch73  are based directly on classical general relativity, and as
such, their verification from observational data is also an endorsement of
that theory as the correct description of physical spacetime.

Inspired by ref. bch73 , Bekenstein bek73  proposed that in a universe with
black holes present, a Generalized Second law of Thermodynamics must hold, in
which the entropy of black holes (which was supposed to originate from a
quantum theory of gravity) is taken into account. Taken together with
Bekenstein’s other hypothesis that black hole entropy must be a (linear)
function of the horizon area, and adopting confirmatory arguments from
Hawking’s seminal work on black hole radiance haw75 , these proposals are the
key pillars on which Black Hole Thermodynamics is founded. The Generalized
Second Law reduces to Hawking’s area theorem when restricted to classical
general relativity. Calculations of black hole entropy in LQG abck98  and in
superstring theory (restricted to five dimensional extremal black holes)
vafs96  both confirm the BH area law. However, following Bekenstein’s argument
that black hole entropy must have quantum gravity origins, one expects
specific corrections to the classical area theorem for every serious proposal
of quantum gravity.

In this paper, we first attempt a semi-rigorous justification of both
Bekenstein’s hypotheses based on a generic formulation of quantum gravity
where the role of the quantum Hamiltonian constraint is highlighted. We next
specialize to Loop Quantum Gravity (LQG) where an ab initio non-perturbative
computation of black hole entropy has been performed by different groups over
two decades km98  \- abhi-pm14 , leading to specific corrections to the semi-
classical Bekenstein-Hawking (BH) entropy. These LQG corrections are
themselves functions only of the BH entropy. Incorporating these corrections
into the Generalized Second Law as applied to BBH coalescence studied for
almost a decade by the LVK collaboration, an inequality emerges, giving an
estimate of the magnitude of the LQG corrections. This inequality can be
expressed directly in terms of the measured total horizon area (BH entropy) of
the inspiralling black holes, very much prior to merger, and in terms of the
‘area (BH entropy) excess’ deduced much later, post-ringdown, from the
measured area of the merger remnant. The successful assay on verification of
the Hawking area theorem bad18  \- bad22  is then used to show that our LQG
bound is entirely consistent with results of these analyses of LVK data.

##  II Generalized Second Law

Figure 1: Classical black hole spacetime

A generic classical black hole spacetime, depicted in Fig. 1, can be described
mathematically by ${\cal B}={\cal M}-{\cal J}^{-}({\cal I}^{+})$, where ${\cal
M}$ is the entire spacetime and ${\cal J}^{-}({\cal I}^{+})$ is the
chronological past of asymptotic future null infinity. The inner boundary of
${\cal B}~{},~{}\partial{\cal B}=h_{+}$ is called the future event horizon.

The quantum description of such a spacetime may begin from the assumption of
the Hilbert space of the system ${\cal H}$ having the structure ${\cal
H}_{\cal B}\otimes{\cal H}_{h_{+}}$. Any general state $|\Psi\rangle\in{\cal
H}$ can then be expanded as

$\displaystyle|\Psi\rangle=\sum_{{\cal B},h_{+}}C_{{\cal B}h_{+}}|\psi_{\cal
B}\rangle\otimes|\psi_{h_{+}}\rangle$ (1)

where, the complex matrix coefficients $C_{{\cal B}h_{+}}$ are not necessarily
diagonal, thereby permitting possible entanglement between the bulk (${\cal
B}$) and horizon (boundary) states. The Hamiltonian for the spacetime is
assumed to have the structure ${\hat{H}}={\hat{H}}_{\cal B}\otimes{\bf
I}_{h_{+}}\oplus{\bf I}_{\cal B}\otimes{\hat{H}}_{h_{+}}$, i.e.,
${\hat{H}}_{\cal B}$ acts only on $|\psi_{\cal B}\rangle\in{\cal H}_{\cal B}$,
while ${\hat{H}}_{h_{+}}$ acts only on $|\psi_{h_{+}}\rangle\in{\cal
H}_{h_{+}}$. A third and important assumption is that states of the black hole
Hilbert space ${\cal H}_{\cal B}$ are solutions of the quantum Hamiltonian
constraint : ${\hat{H}}_{\cal B}|\psi_{\cal B}\rangle=0$.

As a consequence, it follows that the ‘average energy’ of the system

$\displaystyle\langle\Psi|{\hat{H}}|\Psi\rangle$ $\displaystyle=$
$\displaystyle\sum_{h_{+}}D_{h_{+}}\langle\psi_{h_{+}}|{\hat{H}}_{h_{+}}|\psi_{h_{+}}\rangle$
$\displaystyle D_{h_{+}}$ $\displaystyle=$ $\displaystyle\sum_{\cal
B}|C_{{\cal B},h_{+}}|^{2}|||\psi_{\cal B}\rangle||^{2}.$ (2)

We now consider a canonical ensemble of such spacetimes in equilibrium with a
heat bath with an inverse temperature $\beta$; the canonical partition
function is given by the standard definition : ${\cal
Z}=Tr\exp-\beta{\hat{H}}$ where the trace is over all states
$|\Psi\rangle\in{\cal H}$. Eqn (2) is now seen to imply that ${\cal
Z}=Tr_{h_{+}}\exp-\beta{\hat{H}}_{h_{+}}\equiv{\cal Z}_{h_{+}}(\beta)$. Thus
the Hamiltonian constraint reduces the thermodynamics of the system to the
thermodynamics of the horizon states which then serve as microstates for
computation of the canonical entropy of the system. If these horizon states
also diagonalize a suitably defined area operator, then the canonical entropy

$\displaystyle
S(\beta)\equiv\left(1+\frac{\partial}{\partial\log\beta}\right){\cal
Z}_{h_{+}}=S(A_{h_{+}})$ (3)

Thus, somewhat heuristically, we are led to Bekenstein’s contention that black
holes must have an entropy (gravitational in character) which is to be a
function of the horizon area. Further, he hypothesized bek73  that the
functional form of this entropy must be linear, which when reinforced by
Hawking’s seminal work on black hole radiance haw75 , leads to the Bekenstein-
Hawking area law for black hole entropy
$S_{BH}(A_{h_{+}})=A_{h_{+}}/4l_{P}^{2}$ with $l_{P}$ being the Planck length.
The veracity of the area law has been verified in ab initio calculations in
several serious proposals of quantum gravity, including loop quantum gravity
abck98  (for four dimensional generic black holes), and for five dimensional
extremal black holes in string theory vafs96 . In the former case however,
quantum spacetime fluctuations km98  \- abhi-pm14  lead to a whole slew of
quantum corrections to the Bekenstein-Hawking area law, as briefly
recapitulated in the next section.

We end this section with the observation that if two black holes, initially
far away, orbit each around other, leading to an eventual merger to a remnant
black hole with emission of gravitational waves, treating this is as an
isolated system, the thermodynamic second law of entropy increase would imply
that

$\displaystyle S_{bh}(A_{h_{+}})+S_{GW}\geq
S_{bh1}(A_{h_{1+}})+S_{bh2}(A_{h_{2+}}).$ (4)

where, $S_{bh}$ is the entropy of the remnant black hole, while
$S_{bh1},S_{bh2}$ are entropies of the inspiralling ones. This is known as the
Generalized Second Law of thermodynamics in a universe where black holes are
present and may merge emitting gravitational waves. It is obvious that if
$S_{bh}=S_{BH}$, then (4) is just a simple addendum to Hawking’s classical
black hole area theorem haw71 . However, with quantum spacetime corrections to
$S_{bh}$ beyond the area law, eqn (4) may imply further non-trivial
predictions.

##  III Quantum spacetime corrections to Bekenstein-Hawking entropy

Isolated horizons abf00 -abl01 , a non-stationary generalization of stationary
event horizons, are a particularly useful concept for the ab initio
computation of black hole entropy. Classically, the symplectic structure on
such horizons is that of an $SU(2)$ Chern-Simons theory of connections which
are pullbacks of the spacetime connection in the first order formulation of
general relativity, to the spherical foliation of the horizons. Solder two-
forms constructed from bulk densitized triads in the Sen-Ashtekar formulation
of general relativity represent sources for the horizon Chern-Simons
connection fields. In bulk LQG ashlew , holonomies of connections along the
edges of spin network and the fluxes of the densitized triads through surfaces
bounded by the edges, represent the quantum degrees of freedom. The inner
boundary of this quantum geometrical structure is a punctured $S^{2}$ (for
non-rotating isolated horizons), with punctures carrying spin deposited on the
$S^{2}$ by bulk spin network edges. In this framework, fluxes are
distributional, thus providing ‘pointlike’ sources for the quantum Chern-
Simons field strength. The states on the punctured $S^{2}$ are the microstates
in a microcanonical ensemble, being the states of the $SU(2)$ Chern-Simons
theory coupled to the spins at punctures km98 .

Figure 2: Quantum black hole

The dimensionality of the Hilbert space of these states is itself related to
the number of conformal blocks of the conformally invariant $SU(2)_{k}$ Wess-
Zumino-Witten model that exists on a spatial foliation of the isolated horizon
with punctures at the location of the sources. For large $k$, this number can
be computed in terms of the spins km98 , yielding, for a spin configuration
$j_{1},...j_{P}$

$\displaystyle{\cal N}(j_{1},...j_{P})$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{P}\sum_{m_{i}=-j_{i}}^{j_{i}}[\delta_{\sum_{n=1}^{P}m_{n},0}$
(5) $\displaystyle-$
$\displaystyle\frac{1}{2}\delta_{\sum_{n=1}^{P}m_{n},-1}-\frac{1}{2}\delta_{\sum_{n=1}^{P}m_{n},1}].$

The total number of states is given by

$\displaystyle{\cal N}=\sum_{P}\prod_{i=1}^{P}\sum_{j_{i}}{\cal
N}(j_{1},...j_{P}).$ (6)

Usual Boltzmann entropy is given by $S=\log{\cal N}$, and in the limit of
large $k=A/l_{P}^{2}$, one obtains for the microcaonical entropy of quantum
isolated horizonskm2000 -abhi-pm14 , the result

$\displaystyle S_{bh}=S_{BH}-\frac{3}{2}\log S_{BH}+{\cal O}(S_{BH}^{-1})~{},$
(7)

where, $S_{BH}\equiv A_{h+}/4l_{P}^{2}$ is the semiclassical Bekenstein-
Hawking area law for any black hole with $A_{h+}$ being the cross-sectional
area of the horizon, and $l_{P}=(G\hbar/c^{3})^{1/2}$ is the Planck length. In
some of the cited works it has been claimed that the isolated horizon states
are those of a $U(1)$ Chern-Simons theory; however, as shown in ref. bkm09 ,
taking account of the additional gauge fixing in these papers, the corrections
given in (7) remain valid.

##  IV Prediction from the Generalized Second Law

We define the remnant Bekenstein-Hawking entropy $S_{BH}(A_{h_{+}})\equiv
S_{BHr}$, and the inspiral black holes have $S_{BH}(A_{h_{1+}})\equiv
S_{BH1},S_{BH}(A_{h_{2+}})\equiv S_{BH2}$, so that the Generalized Second Law
(4) can be re-expressed, including the LQG corrections in (7), as

$\displaystyle S_{BHr}+S_{GW}-\frac{3}{2}\log S_{BHr}$ $\displaystyle\geq$
$\displaystyle S_{BH1}+S_{BH2}$ (8) $\displaystyle-$
$\displaystyle\frac{3}{2}\log(S_{BH1}S_{BH2})$

Defining $S_{BHi}\equiv S_{BH1}+S_{BH2}$ as the inspiral black hole entropy,
and $\Delta S_{BH}\equiv S_{BHr}-S_{BHi}$ as the change in entropy due to the
coalescence, the inequality (8) can be rewritten as

$\displaystyle\Delta
S_{BH}+S_{GW}\geq\log\left(\frac{S_{BH1}S_{BH2}}{S_{BHr}}\right)^{-3/2}.$ (9)

This can be reorganized and expressed in terms of direct measureables

$\displaystyle
S_{BHi}^{-1}\log\left\\{\frac{S_{BHi}[1-(\delta_{12}S_{BH}/S_{BHi})^{2}]}{4[1+(\Delta
S_{BH}/S_{BHi})]}\right\\}\geq$ (10) $\displaystyle-$
$\displaystyle\frac{2}{3}\frac{\Delta S_{BH}+S_{GW}}{S_{BHi}}$

where $\delta_{12}S_{BH}\equiv|S_{BH1}-S_{BH2}|$.

A perusal of the analyses in ref.s bad18 -bad22  reveals that the relative
entropy excess $\Delta
S_{BH}/S_{BHi}\in[\Delta_{max}S_{BH}/S_{BHi}~{},~{}\Delta_{min}S_{BH}/S_{BHi}]$
where error bars have been taken into account. This enables rewriting (10) as
a strict inequality

$\displaystyle
S_{BHi}^{-1}\log\left\\{\frac{S_{BHi}[1-(\delta_{12}S_{BH}/S_{BHi})^{2}]}{4[1+(\Delta_{min}S_{BH}/S_{BHi})]}\right\\}>$
(11) $\displaystyle-$
$\displaystyle\frac{2}{3}\frac{\Delta_{max}S_{BH}+S_{GW}}{S_{BHi}}$

We now make a few approximations : clearly for BBH mergers like GW150914, the
inspiralling black holes are similar, such that
$(\delta_{12}S_{BH}/S_{BHi})^{2}<<1$; likewise, the analyzed data from ref.s
bad18 -bad22  shows that $\Delta_{min}S_{BH}/S_{BHi}<<1$. As regards the
gravitational wave entropy $S_{GW}$, a preliminary estimate made in ref. mr21
implies that $S_{GW}/S_{BHi}<<\Delta_{max}S_{BH}/S_{BHi}$. With these
approximations, the inequality (11) reduces to

$\displaystyle\frac{\log(S_{BHi}/4)}{S_{BHi}}>-\frac{2}{3}\frac{\Delta_{max}S_{BH}}{S_{BHi}}.$
(12)

That this inequality is valid is obvious from the data analyses of ref.s bad18
-bad22 : $S_{BHi}>>4$, ensuring that the lhs is strictly positive. Also, for
most data $\Delta_{max}S_{BH}/S_{BHi}>1$, rendering the rhs strictly negative.
Thus, as mentioned earlier, the lower bound on LQG corrections to the BH
entropy, derived by substitution in the Generalized Second Law, is entirely
consistent with the analyzed LVK data. This is perhaps the first time that a
prediction based on a quantum gravity proposal has been fully borne out by LVK
data on BBH mergers.

##  V Discussion

We should perhaps emphasize that our claim of consistency of the outcome of
combining the loop quantum gravity result for quantum black hole entropy and
the Generalized Second Law, with the analyses in ref.s bad18 -bad22  of the
LVK data on gravitational waves, is n͡ot a claim that LVK data has now given a
precise confirmation of a quantum gravity result. The present observational
accuracy of the data would have to increase many, many orders of magnitude
before such a claim may be made. The main point of the paper is that the
consistency pointed out in the paper in inequality (12), holds irrespective of
the value of the constant prefactor $-2/3$ in the rhs, so long as it is a
negative real number ! The number $-2/3$ emerges from the loop quantum gravity
calculation of black hole entropy whose result has been presented in eqn (7),
and is likely to differ for calculations of black hole entropy based on other
approches to quantum gravity. All such results with a negative coefficient of
the logarithmic correction to the area law are consistent with the analyses of
LVK data which confirms Hawking’s area theorem. A finer distinction between
members of this class of theories of quantum gravity, i.e., where the quantum
black hole entropy is less than the Bekenstein-Hawking value, is of course not
possible with present levels of accuracy.

Contrast this situation with those quantum gravity approaches in which the
logarithmmic correction appears with a positive constant, i.e.,
$S_{bh}=S_{BH}+\xi\log S_{BH}+\cdots$ for macroscopic black holes, with a
positive real $\xi$. The brief analysis performed above now leads to an upper
bound on the correction to the area law, which transcribes into

$\displaystyle\frac{\log(S_{BHi}/4)}{S_{BHi}}<\xi^{-1}\frac{\Delta
S_{BH}}{S_{BHi}}$

Unlike in the case for loop quantum gravity-like calculations, both sides of
this inequality are now positive numbers. The consistency with the
aforementioned analyses of LVK data is now no longer guaranteed. For a range
of values of $\xi$, a tension may arise between this theoretical result and
the analyses of LVK data confirming the area theorem.

To me, discerning this power of the data and its analyses to discriminate
between two distinct classes of quantum gravity calculations of black hole
entropy is unexpected and therefore very novel. What is remarkable is that the
accuracy, with which the analyses presented in ref.s [9]-[11] claim the
validation of Hawking’s area theorem, is sufficient to demonstrate full
consistency of LQG-like calculation of quantum black hole entropy with those
analyses. No additional accuracy of the data is required for this
demonstration. Intuitively, for reasons which are intriguing but perhaps not
completely transparent at this point, the area theorem analyses of LVK data
seem to favour quantum black hole entropy calculations in which the quantum
entropy is less than the Bekenstein-Hawking value, rather than those in which
quantum corrected entropy exceeds that value.

While observational accuracy in gravitational wave detection continues to
increase with time, further discrimination on the basis of the data between
quantum gravity results in the same category may gradually emerge in future.

We should additionally mention the caveat that a key assumption regarding
comparison with LVK data is that the inspiralling as well as post-merger
remnant black holes in a BBH merger are slowly spinning so that the non-
rotating approximation is approximately applicable. The LQG corrections to the
Bekenstein-Hawking entropy constitute a robust result in the non-rotating
regime. For rotating horizons, there are ambiguities in the LQG approach to
the calculation of black hole entropy, which are yet to be satisfactorily
resolved. It is hoped that once these issues are resolved, a similar
consistency with LVK data, as we have sought to present here, will emerge. We
hope to report on this in a future publication.

##  VI Acknowledgements

I thank Prof Badri Krishnan and Soumendra Kishore Roy for providing me with
ref.s bad06  \- bad22

## References

  * (1) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], Phys. Rev. Lett. 116(6), 061102 (2016). e-print arXiv:1602.03837 [gr-qc]
  * (2) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], Phys. Rev. Lett. 116(24), 241103 (2016). e-print-arXiv:1606.04855 [gr-qc]
  * (3) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], Phys. Rev. Lett. 119(14), 141101 (2017). eprint-arXiv:1709.09660 [gr-qc]
  * (4) B. P. Abbott et al. [LIGO Scientific and VIRGO Collaborations], Phys. Rev. Lett. 118(22), 221101 (2017). Erratum: [Phys. Rev. Lett. 121(12), 129901 (2018)]. eprint-arXiv:1706.01812 [gr-qc]
  * (5) B. P. Abbott et al. [LIGO Scientific and VIRGO Collaborations], Phys. Rev. Lett. 119(16), 161101 (2017). eprint-arXiv:1710.05832 [gr-qc]
  * (6) B. P. Abbott et al. [LIGO Scientific and VIRGO Collaborations], Phys. Rev. Lett. 121(16), 161101 (2018). eprint-arXiv:1805.11581 [gr-qc]
  * (7) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], Astrophys. J. 851(2), L35 (2017). eprint-arXiv:1711.05578 [astro-ph.HE]
  * (8) D. Pooh-Kolb, O. Birnholtz, J-L. Jaramillo, B. Krishnan and E. Schnetter, Horizons in a binary black hole merger I: Geometry and area increase. e-print arXiv:2006.03939 [gr-qc].
  * (9) M. Cabero, C. D. Capano, O. Fischer-Birnholtz, B. Krishnan, A. B. Nielsen, A. H. Nitz, C. M. Biwer, Phys. Rev. D 97, 124069 (2018).
  * (10) M. Isi, W. M. Farr, M. Giesler, M. A. Scheel, S. A. Teukolsky, Phys. Rev. Lett., 127, 011103 (2021).
  * (11) S. Kastha, C. D. Capano, J. Westerweck, M. Cabero, B. Krishnan, A. B. Nielsen, Phys. Rev. D 105, 064042 (2022).
  * (12) S. W. Hawking, Phys. Rev. Lett. 26, 1344 (1971).
  * (13) J. A. Bardeen, B. Carter, S. W. Hawking, 31, 161 (1973).
  * (14) J. Bekenstein, Phys. Rev. D7, 2333 (1973).
  * (15) S. W. Hawking, Commu. Math. Phys. 46, 206 (1975).
  * (16) A. Ashtekar, J. Baez, A. Corichi and K. Krasnov, Phys. Rev. Lett. 80, 904 (1998).
  * (17) A. Strominger and C. Vafa, Phys. Lett. B 379, 99 (1996), eprint arXiv : hep-th/9601029 [hep-th].
  * (18) A. Ashtekar, C. Beetle, S. Fairhurst, Class. Quant. Grav., 17, 253 (2000). eprint-arXiv: gr-qc/9907068.
  * (19) A. Ashtekar, C. Beetle and J. Lewandowski, Class. Quant. Grav. 19, 1195 (2001). eprint-arXiv : gr-qc/0111067.
  * (20) A. Ashtekar, J. Lewandowski, Class. Quant. Grav. 21, R53 (2004), eprint-arXiv:gr-qc/0404018.
  * (21) R. K. Kaul and P. Majumdar, Phys. Lett. B439, 267 (1998). eprint-arXiv:gr-qc/9802111
  * (22) P. Majumdar, Ind. Jou. Phys. B43, 147 (1998). eprint-arXiv:gr-qc/9807045.
  * (23) R. K. Kaul and P. Majumdar, Phys. Rev. Lett. 84, 5255 (2000). eprint-arXiv:gr-qc/0002040.
  * (24) M. Domagala and J. Lewandowski, Class. Quant. Grav. 21, 5233 (2004). eprint-arXiv: gr-qc/0407051.
  * (25) K. A. Meissner, Class. Quant. Grav. 21, 5245 (2004). eprint-arXiv:gr-qc/0407052.
  * (26) A. Ghosh and P. Mitra, Phys. Lett. B616, 114 (2005). eprint-arXiv:gr-qc/0411035.
  * (27) A. Ghosh and P. Mitra, Phys. Rev. Lett. 102, 141302 (2009). eprint-arXiv:0809.4170 [gr-qc].
  * (28) J. Engle, K. Noui and A. Perez, Phys. Rev. Lett. 105, 031302 (2010). eprint-arXiv:0905.3168.
  * (29) J. Engle, K. Noui, A. Perez and D. Pranzetti, Phys. Rev. D82, 044050 (2010). eprint-arXiv:1006.0634.
  * (30) R. K. Kaul, Sigma 8, 005 (2012). e-print-arXiv:1201.6102.
  * (31) A. Majhi, Class. Quant. Grav. 31, 095002 (2014). eprint-arXiv:1205.3487.
  * (32) A. Majhi and P. Majumdar, Class. Quant. Grav. 31, 195003 (2014). eprint-arXiv:1301.4553.
  * (33) R. Basu, R. K. Kaul and P. Majumdar, Phys. Rev. D 82, 024007 (2010). eprint-arXiv : 0907.0846.
  * (34) P. Majumdar and A. Ray, Phys. Rev. D 104-4, 044036 (2021). eprint-arXiv : 2008.13425.


# Learning to Merge Tokens
in Vision Transformers

Cedric Renggli
ETH Zurich &André Susano Pinto∗
Google Research &Neil Houlsby
Google Research Basil Mustafa
Google Research &Joan Puigcerver
Google Research &Carlos Riquelme∗
Google Research Authors contributed equally to the work. Cedric’s work was
done while interning at Google Research. Correspondence to
<EMAIL_ADDRESS>and {andresp<EMAIL_ADDRESS>
###### Abstract

Transformers are widely applied to solve natural language understanding and
computer vision tasks. While scaling up these architectures leads to improved
performance, it often comes at the expense of much higher computational costs.
In order for large-scale models to remain practical in real-world systems,
there is a need for reducing their computational overhead. In this work, we
present the PatchMerger, a simple module that reduces the number of patches or
tokens the network has to process by merging them between two consecutive
intermediate layers. We show that the PatchMerger achieves a significant
speedup across various model sizes while matching the original performance
both upstream and downstream after fine-tuning.

##  1 Introduction

The success of modern deep learning is tightly coupled with increasing model
and dataset sizes. This trend is especially visible in natural language
processing (NLP) and in computer vision. In NLP, some recent models such as
BERT (Devlin et al., 2018) or GPT-3 (Brown et al., 2020) achieve the state-of-
the-art performance on many language tasks. One major ingredient to enable the
efficient scaling of such models are transformer blocks (Vaswani et al.,
2017). Transformer blocks perform attention on a token-level (Bahdanau et al.,
2014). In language models, for instance, a token may correspond to a word.
Dosovitskiy et al. (2020) adapted this technique to the vision domain,
introducing the vision transformer (ViT) architecture. The key idea is to
split the image into a sequence of square patches (e.g., $14\times 14$ pixels)
and embed them into a fixed-size representation. The patches or tokens111We
use the terms token and patch in the context of vision transformers
interchangeably to refer to the representations passed between transformer
blocks. are then fed into the transformer blocks. The ViT model size and
computational cost depends on (1) the number of tokens (dependent of the patch
size, smaller patches means more patches in total), (2) the number of layers
(i.e., how many transformer encoder blocks we apply), and (3) the dimension of
the token representations (referred to as the hidden dimension).

Increasing model capacity while limiting its computational cost is an active
research area. In NLP (Shazeer et al., 2017), sparse mixtures of experts have
proved successful in allowing models to scale up to trillions of parameters.
Sparse models only apply a small subset of the parameters to process each
example, as dictated by trainable routers. This conditional computation
approach was then extended in Riquelme et al. (2021) to Vision Mixture of
Experts (V-MoE). Whilst V-MoE successfully increases the number of parameters
by an order of magnitude, the model still handles increasingly more tokens at
higher resolutions.

Further, Riquelme et al. (2021) showed that one can save compute by skipping
the computation of expert blocks for some tokens while having very little
impact on the model’s performance. They propose an algorithm to assign
different priorities to each token with the hope to save compute on the least
important ones. Batch Priority Routing works well even when only processing
15-30% of the tokens through the expert blocks. Unfortunately, all tokens are
still processed by the non-expert blocks (which represent a large fraction of
the total blocks).

Inspired by these insights and by related work inspecting the impact of the
number of tokens on the downstream accuracy (c.f, Section 2), we explore if
the number of tokens required to classify an image can be dramatically reduced
at an early stage with minimal computational extra costs while keeping the
performance mostly intact.

To achieve this goal, we introduce a simple module called the PatchMerger.
This module can be placed between any two encoder blocks and it will reduce
the number of tokens by merging them together. Importantly, the number of
output tokens is independent from the number of input tokens and the same
network can handle a different number of input tokens. This capability is
crucial to support fine-tuning a model at different resolution than it was
pre-trained with, and some naive alternative methods to alter the number of
tokens fail to satisfy this requirement.

Our main contributions are as follow:

  1. 1.

We propose a simple, yet novel learned module called the PatchMerger to reduce
the number of tokens inside Vision Transformers.

  2. 2.

We provide extensive experimental results showing that by using the
PatchMerger we can achieve comparable upstream and downstream performance
across all ViT and V-MoE variants, while saving a significant amount of
compute and time (40-60% for large models).

  3. 3.

We provide additional comparative studies justifying the design choices
regarding where to place the PatchMerger and how aggressively to merge tokens.

##  2 Background and Related Work

An effective recipe to improve model performance in both NLP and computer
vision is to scale the total amount of compute (Brown et al., 2020; Zhai et
al., 2021). Fortunately, expensive upstream models have been shown to preserve
their gains when finetuned to downstream tasks. Consequently, researchers now
compare the performance of models with a comparable overall training cost.

Dosovitskiy et al. (2020) shows that Vision Transformers can match state-of-
the-art CNNs while requiring substantially fewer computational resources to
train. ViT represents an image as a sequence of patches (e.g. an image of
256x256 pixels is split into 1024 tokens of 8x8 pixels) and it processes them
with the Transformer architecture (Vaswani et al., 2017), a well-known player
in the language community. A Transformer is composed of a stack of blocks with
residual connections; each of them includes a self-attention and a MLP layer.
The number of tokens is kept constant throughout the network up to a
classification head.

This constant number of tokens being processed during the transformer layers
is in contrast with the more typical pyramidal structure of CNN based
architectures, where the input size decreases as we progress along the
network. Accordingly, there has been a number of works that play with and try
to mimic this sequentially cheaper behavior, including PyramidViT (Wang et
al., 2021), the Perceiver (Jaegle et al., 2021a; b) and the TokenLearner (Ryoo
et al., 2021). Our work is very similar in spirit to the last, whereas our
implementation and merging module is conceptually simpler. The Swin
Transformer (Liu et al., 2021) avoids quadratic cost in the number of tokens
by limiting the attention range, and it merges adjacent tokens through the
layers; other recent works such as the BoTNet (Srinivas et al., 2021)
effectively combine convolutions and attention layers.

Another line of work on compute efficiency is sparsity and conditional
computation. Recently, in the computer vision domain, Riquelme et al. (2021)
have shown that by replacing the dense layer of some transformer blocks with
mixture of experts one can obtain higher performance at roughly the same
computational cost. Additionally, they also show that small routing modules
learnt from scratch can successfully decide when to skip the MLP processing
for some tokens. This strongly suggests that not all tokens are needed, an
idea we heavily exploit in this work.

##  3 The PatchMerger Module

Figure 1: (Left) Overview of the PatchMerger module with $N$ input tokens and
$M$ output ones.
(Right) Placement and token shapes when adding a PatchMerger between two
encoder blocks.

The PatchMerger outputs a fixed number of tokens when applied to any number of
input tokens. We place it between two consecutive transformer encoder layers.
Accordingly, all the subsequent layers will process the new (and reduced)
number of tokens. Intuitively, the way it works is as follows. Suppose we set
the number of output patches to be $M$. Then, for any incoming patch $p$, the
PatchMerger computes $M$ scores $s_{1:M}(p)$ — one per output patch — based on
a linear transformation of the patch representation at that point, say
$z_{p}$. We normalize the scores to sum up to 1 by applying a softmax
transformation: $\sigma(s_{1:M}(p))$. Finally, $p$ will contribute to each new
output patch $i$ with its representation weighted by the scored computed for
that output patch, that is, $\sigma(s_{i}(p))\ z_{p}$.

This simple idea has several interesting implications. First, similar patches
are _routed_ similarly, i.e., they end up contributing or being merged into
the same subset of output patches. This can be useful, for example, to reduce
the amount of compute required by redundant background patches in object-
centric images. Second, the way an old patch is distributed into new patches
is independent of the patch’s original _position_ or index, as it would happen
with a raw linear merging operation. Finally, we can freely increase or
decrease the number of input patches while keeping the learned parameters
intact. If the number of training and inference tokens differ significantly,
there can be a mismatch in the scale of the weighted sum for output patches.
However, a layer norm is applied right after the PatchMerger, in the following
transformer block, which helps to mitigate this potential effect. Moreover,
our experiments suggest finetuning is able to cope and adapt to this extremely
quickly.

#### Connections to Attention.

Figure 1 gives a graphical overview of the PatchMerger. Layer normalization is
applied before merging blocks. The PatchMerger then consists of a learned
matrix $W\in\mathbb{R}^{D\times M}$, where $D$ is the size of the latent token
representation. If we represent the $N$ input patches after layer
normalization by a matrix $\mathbf{X}\in\mathbb{R}^{N\times D}$, the merged
representations $\mathbf{Y}\in\mathbb{R}^{M\times D}$ are computed as follows:

$\mathbf{Y}=\textrm{softmax}\left(\left(\mathbf{X}W\right)^{T}\right)\mathbf{X}=\textrm{softmax}\left(W^{T}\mathbf{X}^{T}\right)\mathbf{X}.$
(1)

Equation (1) is similar to the non-scaled dot-product attention formula from
Vaswani et al. (2017):

$\text{Att}(Q,K,V)=\text{softmax}\left(QK^{T}\right)V.$ (2)

In particular, we use the input patches as both keys and values, and simply
learn a fixed set of queries — one per output patch. This is partially similar
to the default implementation of encoder-decoder attention, where both keys
and values are linear projections of the encoder output (Bahdanau et al.,
2014). However, their queries are computed based on the output of the previous
decoder layer. Other recent works have also explored input-independent
learnable queries (Jaegle et al., 2021a). Moreover, unlike the dot-product
attention in (2), the softmax in (1) is applied per input token (i.e. along
each column), typically referred to as _bottom-up_ attention (Abnar, 2019). We
tried to apply this idea directly to the attention layer in one of the
transformer blocks, but it led to severe instabilities (and we had to deal
with the mismatch in shapes due to the residual connection). Consequently, we
decided to just keep PatchMerger modules in-between full transformer blocks.

##  4 Experimental Evaluation

In this section we present experiments showing that using the PatchMerger
matches the performance of its backbone network (either VIT or V-MoE) while
requiring significant fewer FLOPs and runtime (between 40%-50% for the largest
models).

Training Data. We train all of our models on JFT (Hinton et al., 2015), a
proprietary dataset containing 300M images. Each image is classified to one or
several of the 18291 classes, mostly natural images (animals, landscapes,
objects, etc), and we use a (224 $\times$ 224 $\times$ 3) resolution. We
follow the model sizes and training strategies from (Dosovitskiy et al., 2020;
Riquelme et al., 2021): training for 5 epochs for Small, 7 for Base, and 14
for the Large and Huge models. The patch sizes are $(32,32)$ for Small and
Base, $(16,16)$ for Large, and $(14,14)$ for Huge, leading to 49, 196, and 256
training patches per image respectively (note we usually append an additional
cls token). We report the precision at one in a test set, that is, how often
the top-1 model prediction is indeed one of the possibly multiple labels for
the test image.

Transfer to ImageNet. We want to train _transferable_ models, so that an
expensive training can be amortized over a wide range of downstream tasks. We
test this property in two ways: via few-shot evaluation and full finetuning.
In particular, we transfer to ImageNet (Deng et al., 2009). For few-shot
evaluation, we freeze the model weights, and replace the original JFT head
with a new from-scratch head for ImageNet. Then, we train only the head on a
few examples per class (5-shot corresponds to 5 examples per ImageNet class,
and so on). For fine-tuning, we train all the JFT-checkpoint weights on the
whole ImageNet dataset for a few epochs. We report the top-1 model accuracy.

PatchMerger Design Choices. As introduced in the previous section, we can use
the PatchMerger in several ways. We experimented with many design choices –a
single or several mergers, more or less aggressive token reduction, etc.–,
while in this section we only focus on the ones that proved simplest and most
successful. Given a backbone network, we place one merger layer in the middle
of the network, and it outputs 8 patches. All the backbone networks have an
even number of encoder blocks (that is, 8, 12, 24, or 32), and we place the
merger between the first and second half of blocks (i.e., after the first 4,
6, 12, or 16 blocks). The number of tokens that backbone networks use depends
on the patch size; however, regardless of the number of initial patches, we
always merge them into 8 patches. This approach dramatically reduces the
amount of compute required in the second half of encoder blocks, whereas the
amount of compute in the first half does not change. Later in this section we
independently test each of these design choices (where to place the merger,
and how much to merge).

A common practice when finetuning a pre-trained model consists in increasing
the image size for the new task. If the patch size remains constant, then the
pre-trained embedding layer can be loaded, applied, and finetuned as usual. As
images are larger, the total number of patches then increases. However, the
PatchMerger does _not_ adjust the bottleneck: we still merge in the middle of
the network all the incoming patches into just 8 of them. This means the
amount of downstream processing will grow with respect to the upstream (or
pre-trained) model in the first half of the network, but the second half’s
compute will remain intact after the PatchMerger. For the original backbone
network (i.e., without PatchMerger module), however, compute grows everywhere.
Thus, the compute gap between the PatchMerger equipped network and its
backbone will be even more severe at finetuning and inference time.

Results. We first present upstream and few-shot results. Figure 2 and Figure 3
show the performance versus training FLOPs trade-offs for ViT and V-MoE
respectively. For completeness, Figure 7 and Figure 8 in the appendix present
our results with respect to training runtime (rather than FLOPs). All numbers
are presented in Table 1 (ViT) and Table 2 (V-MoE).

The Merger ViT (Figure 2) obtains comparable –sometimes even better–
performance than its backbone ViT models with a much lower cost. In
particular, the Pareto frontier for Merger ViT models completely dominates the
ViT one, and by a wide margin. When fully fine-tuning on ImageNet, shown in
Figure 4a), we also see that the large merged models (L/32, L/16, and H/14)
match their backbone counterparts.

Moreover, at the largest scale, the Merger ViT-H/14 reaches the same
performance as ViT-H/14 both in JFT and ImageNet 10-shot while requiring only
51.6% of the FLOPs and 63.5% of the runtime. There are several ways to use
these savings in compute to improve the model even further; for instance, by
adding more transformer blocks or by using more tokens to start with. In
Figure 2 we show the latter approach: Merger ViT-H/11 where we use the VIT-H
backbone network (32 encoder blocks) but with a smaller patch size ($11\times
11$). This implies more tokens in the first half of the network, whereas the
second half requires the same compute as only 8 tokens travel through it. As
shown in Figure 2 and Figure 4, while this approach is still significantly
cheaper than the standard VIT-H/14 (takes $\sim 80\%$ of the FLOPs and
runtime), it definitely outperforms it both upstream, at few-shot, and after
full finetuning.

When applied to MoE models (Figure 3), we reach similar positive conclusions
for large models (L/16 and H/14), where savings amount to around 53% of the
FLOPs and 44% of the runtime. Again, the Pareto frontier for merged MoE models
dominates that of their MoE backbone, whereas we notice slight losses in
performance for the small experts models. Figure 4b) shows that small merged
expert models underperform their backbones after finetuning too, while being
much cheaper. For large models, the finetuning Pareto frontier for merged
models seems to offer a modest improvement. Note that we add expert layers
only in the last-2 non-consecutive encoder blocks (last-5 for H/14) as
proposed in Riquelme et al. (2021). As the MoEs are placed in the second half
of the network, all expert layers and their routers only receive 8 tokens per
input image, which can decrease the expert utilization rate as compared to the
case with more tokens per image.

(a) Upstream precision at one.

(b) 10-shot accuracy on ImageNet.

Figure 2:  Patch Merger for ViT. Performance versus total training FLOPs.
Colors represent different ViT variants, markers represent either standard

$\bullet$

ViT or

$\blacksquare$

Merger ViT. The brown Merger ViT (top-right most) corresponds to H/11. Lines
show the Pareto frontier of Merger ViT (solid) and ViT (dashed). Figure 7 in
the Appendix shows performance versus runtime for these models.

(a) Upstream precision at one.

(b) 10-shot accuracy on ImageNet.

Figure 3:  Patch Merger for V-MoE. Performance versus total training FLOPs.
Colors represent different V-MoE variants, markers represent either standard

$\mathbf{x}$

V-MoE or Merger V-MoE. Lines show the Pareto frontier of Merger V-MoE (solid)
and V-MoE (dashed). Figure 8 in the Appendix shows performance versus runtime
for these models.

(a) ViT. Finetuning accuracy on Imagenet.

(b) V-MoE. Finetuning accuracy on Imagenet.

Figure 4:  Full finetuning on ImageNet. Performance versus total training
FLOPs. Colors represent different ViT and V-MoE variants (including H/11 for
Merger ViT), markers represent either standard

$\bullet$

ViT,

$\blacksquare$

Merger ViT,

$\mathbf{x}$

V-MoE or Merger V-MoE. Lines show the Pareto frontiers in each case. Figure 9
in the Appendix shows performance versus runtime for these models.

###  4.1 Comparative Studies

In this subsection we briefly explore the two main algorithmic design choices
for the PatchMerger, namely, where to place the merger and how many tokens to
output. Obviously, the later we place it, and the more tokens we output, the
better performance we expect –as the model would be closer to the original
backbone. However, we also want to drastically reduce the training cost, which
requires the opposite.

Where to place the PatchMerger. While one could place several mergers along
the network and sequentially reduce the total number of tokens, for the sake
of simplicity we constrain our experiments to a single merger, and try to
figure out the performance trade-offs offered by placing the merger before
each encoder block.

Figure 5 shows one such experiment with a ViT-B/32 model with 12 encoder
blocks. We show the upstream precision@1 on JFT, and the ImageNet 10/shot
performance. For each encoder block, we show the performance of a model
trained with a merger placed right _before_ the encoder block. We see that
placing the merger too early in the network –while leading to extremely cheap
models– definitely hurts performance, as the model still needs to use more
tokens. On the other hand, around half of the network –before the sixth
block–, it seems that the merged models achieve full and comparable
performance. This experiment justifies our choice in the previous section.

How many tokens to output. Figure 6 addresses another key question: what is
the right number of tokens to keep after merging. While the answer can be
model and input patch-size dependent, we experiment with a ViT-B/16 model in
this case –as it receives more tokens than a ViT-B/32 and could offer a better
intuition for larger models. As we expected, keeping more tokens is better. On
one hand, if we keep as few as 1 or 2 tokens only, the impact on performance
is severe. At the other extreme, it seems that keeping beyond 32 tokens of the
196 input tokens only offers diminishing returns. Accordingly, we believe that
a number of tokens in the range of 8-32 could be optimal. These are ViT
models; however, for expert models having a few more tokens per input can make
routing and balance easier at the expense of slightly higher computational
cost.

##  5 Conclusion and Future Work

We have shown that a simple module can effectively merge and combine together
tokens for ViT and V-MoE, thus leading to much cheaper and practical models
while preserving the original performance in most cases. In light of the
recent trends of scaling models to massive sizes, we believe this type of
research will have a significant practical and environmental impact. The
PatchMerger assigns a fixed (and reduced) amount of compute to all inputs;
however, not all inputs may require the same amount of processing. Exploring
mechanisms that reduce the overall training cost by assigning adaptive per-
input compute levels is an exciting avenue of future research.

Figure 5: Placement Comparison. The discontinuous line corresponds to placing
the merger in the middle of the network as done in previous sections –after
the 6th, before the 7th encoder block, in this case. The number of output
tokens is 8 in all cases.  Figure 6: Number of Output Tokens Comparison. The
discontinuous line corresponds to outputting 8 tokens as done in previous
sections. The merger is placed in the middle of the network (after the 6th,
before the 7-th encoder block), in all cases.

## References

  * Abnar (2019) Samira Abnar.  From attention in transformers to dynamic routing in capsule nets.  2019\.  URL https://samiraabnar.github.io/articles/2019-03/capsule.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2020.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Jaegle et al. (2021a) Andrew Jaegle, Sebastian Borgeaud, Jean-Baptiste Alayrac, Carl Doersch, Catalin Ionescu, David Ding, Skanda Koppula, Daniel Zoran, Andrew Brock, Evan Shelhamer, Olivier Hénaff, Matthew M. Botvinick, Andrew Zisserman, Oriol Vinyals, and João Carreira.  Perceiver io: A general architecture for structured inputs & outputs.  2021a.
  * Jaegle et al. (2021b) Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and Joao Carreira.  Perceiver: General perception with iterative attention.  2021b.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 10012–10022, 2021.
  * Riquelme et al. (2021) Carlos Riquelme, Joan Puigcerver, Basil Mustafa, Maxim Neumann, Rodolphe Jenatton, André Susano Pinto, Daniel Keysers, and Neil Houlsby.  Scaling vision with sparse mixture of experts.  _arXiv preprint arXiv:2106.05974_ , 2021.
  * Ryoo et al. (2021) Michael S. Ryoo, AJ Piergiovanni, Anurag Arnab, Mostafa Dehghani, and Anelia Angelova.  Tokenlearner: What can 8 learned tokens do for images and videos?  2021\.
  * Shazeer et al. (2017) Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  _arXiv preprint arXiv:1701.06538_ , 2017.
  * Srinivas et al. (2021) Aravind Srinivas, Tsung-Yi Lin, Niki Parmar, Jonathon Shlens, Pieter Abbeel, and Ashish Vaswani.  Bottleneck transformers for visual recognition.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 16519–16529, 2021.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pp. 5998–6008, 2017.
  * Wang et al. (2021) Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 568–578, October 2021.
  * Zhai et al. (2021) Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  2021\.

##  Appendix A Appendix

Model | TPU-Days | ExoFLOPs | JFT Prec@1 | INet/1shot | INet/5shot | INet/10shot | INet/finetuned
---|---|---|---|---|---|---|---
ViT-H/14 | 2387.71 | 4275.92 | 56.56 | 61.35 | 76.76 | 79.12 | 87.97
Merger ViT-H/11 | 1920.82 | 3464.17 | 58.15 | 62.77 | 77.53 | 79.84 | 88.24
Merger ViT-H/14 | 1518.49 | 2207.33 | 57.27 | 62.07 | 77.25 | 79.26 | 87.90
ViT-L/16 | 651.18 | 1572.74 | 53.37 | 59.04 | 73.92 | 76.51 | 86.84
Merger ViT-L/16 | 388.44 | 819.29 | 53.71 | 59.99 | 74.99 | 77.01 | 87.01
ViT-L/32 | 97.29 | 196.11 | 46.52 | 50.34 | 66.59 | 69.58 | 84.45
Merger ViT-L/32 | 66.49 | 114.38 | 46.61 | 51.29 | 67.61 | 70.32 | 84.08
ViT-B/16 | 95.04 | 224.45 | 44.58 | 48.21 | 63.50 | 66.94 | –
Merger ViT-B/16 | 54.22 | 117.22 | 43.75 | 49.49 | 64.35 | 67.15 | –
ViT-B/32 | 27.62 | 56.07 | 39.48 | 40.66 | 55.47 | 58.93 | 81.39
Merger ViT-B/32 | 17.76 | 32.99 | 38.62 | 40.53 | 57.23 | 60.02 | 79.96
ViT-S/32 | 7.22 | 12.27 | 29.05 | 29.37 | 43.21 | 46.38 | 76.34
Merger ViT-S/32 | 4.83 | 7.34 | 27.82 | 26.42 | 40.27 | 43.75 | 73.77
Table 1: ViT and Merged ViT Models. TPU-days and FLOPs refer to the total training cost. Model | TPU-Days | ExoFLOPs | JFT Prec@1 | INet/1shot | INet/5shot | INet/10shot | INet/finetuned
---|---|---|---|---|---|---|---
V-MoE-H/14 | 2735.70 | 4750.73 | 60.12 | 62.95 | 78.08 | 80.10 | 88.41
Merger V-MoE-H/14 | 1520.59 | 2220.96 | 59.84 | 63.21 | 77.56 | 79.97 | 88.10
V-MoE-L/16 | 761.27 | 1666.10 | 56.76 | 61.46 | 76.53 | 78.64 | 87.47
Merger V-MoE-L/16 | 388.19 | 823.54 | 56.14 | 61.72 | 75.86 | 78.03 | 87.04
V-MoE-L/32 | 110.65 | 207.94 | 49.68 | 54.52 | 69.90 | 72.80 | 85.05
Merger V-MoE-L/32 | 67.11 | 116.70 | 48.75 | 52.03 | 68.98 | 71.63 | 84.46
V-MoE-B/16 | 130.86 | 250.70 | 48.31 | 54.92 | 68.84 | 71.81 | –
Merger V-MoE-B/16 | 54.78 | 118.59 | 46.65 | 53.33 | 67.53 | 70.05 | –
V-MoE-B/32 | 36.80 | 62.75 | 43.17 | 48.04 | 62.45 | 65.72 | 83.27
Merger V-MoE-B/32 | 18.51 | 34.61 | 41.77 | 44.88 | 60.24 | 63.62 | 80.57
V-MoE-S/32 | 12.40 | 14.40 | 33.26 | 35.49 | 50.90 | 54.16 | 78.63
Merger V-MoE-S/32 | 5.33 | 7.95 | 32.85 | 33.59 | 49.23 | 52.74 | 75.07
Table 2: V-MoE and Merged V-MoE Models. TPU-days and FLOPs refer to the total
training cost.

(a) Upstream precision at one.

(b) 10-shot accuracy on ImageNet.

Figure 7:  Patch Merger for ViT. Performance versus total training runtime.
Colors represent different ViT variants, markers represent either standard

$\bullet$

ViT or

$\blacksquare$

Merger ViT. The brown Merger ViT (top-right most) corresponds to H/11. Lines
show the Pareto frontier of Merger ViT (solid) and ViT (dashed). Figure 2 in
the main text shows performance versus FLOPs for these models.

(a) Upstream precision at one.

(b) 10-shot accuracy on ImageNet.

Figure 8:  Patch Merger for V-MoE. Performance versus total training runtime.
Colors represent different V-MoE variants, markers represent either standard

$\mathbf{x}$

V-MoE or Merger V-MoE. Lines show the Pareto frontier of Merger V-MoE (solid)
and V-MoE (dashed). Figure 3 in the main text shows performance versus FLOPs
for these models.

(a) ViT. Finetuning accuracy on Imagenet.

(b) V-MoE. Finetuning accuracy on Imagenet.

Figure 9:  Full finetuning on ImageNet. Performance versus total training
runtime. Colors represent different ViT and V-MoE variants (including H/11 for
Merger ViT), markers represent either standard

$\bullet$

ViT,

$\blacksquare$

Merger ViT,

$\mathbf{x}$

V-MoE or Merger V-MoE. Lines show the Pareto frontiers in each case. Figure 4
in the main text shows performance versus FLOPs for these models.