{}\pgfsys@moveto{61.17325pt}{-14.22638pt}\pgfsys@moveto{61.17325pt}{-14.22638pt}\pgfsys@curveto{61.77325pt}{-14.52637pt}{62.17325pt}{-15.22638pt}{62.17325pt}{-16.22638pt}\pgfsys@lineto{62.17325pt}{-26.45276pt}\pgfsys@curveto{62.17325pt}{-27.45276pt}{62.57324pt}{-28.15277pt}{63.17325pt}{-28.45276pt}\pgfsys@curveto{62.57324pt}{-28.75275pt}{62.17325pt}{-29.45276pt}{62.17325pt}{-30.45276pt}\pgfsys@lineto{62.17325pt}{-40.67914pt}\pgfsys@curveto{62.17325pt}{-41.67914pt}{61.77325pt}{-42.37915pt}{61.17325pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{64.70625pt}{-29.95276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.6}{$\mathrm{junk}$}}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$
$\displaystyle=~{}{\leavevmode\hbox to135.03pt{\vbox
to85.76pt{\pgfpicture\makeatletter\hbox{\hskip
58.32121pt\lower-42.87914pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{-14.22638pt}{-21.33957pt}\pgfsys@curveto{0.0pt}{-21.33957pt}{0.0pt}{21.33957pt}{-14.22638pt}{21.33957pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{-21.33957pt}{-14.22638pt}\pgfsys@curveto{-7.11319pt}{-14.22638pt}{-7.11319pt}{14.22638pt}{-21.33957pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{-28.45276pt}{-7.11319pt}\pgfsys@curveto{-14.22638pt}{-7.11319pt}{-14.22638pt}{7.11319pt}{-28.45276pt}{7.11319pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-14.22638pt}{21.33957pt}\pgfsys@lineto{-45.52458pt}{21.33957pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-21.33957pt}{14.22638pt}\pgfsys@lineto{-56.90552pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-28.45276pt}{7.11319pt}\pgfsys@lineto{-56.90552pt}{7.11319pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-14.22638pt}{-21.33957pt}\pgfsys@lineto{-42.67914pt}{-21.33957pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-21.33957pt}{-14.22638pt}\pgfsys@lineto{-49.79233pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-28.45276pt}{-7.11319pt}\pgfsys@lineto{-56.90552pt}{-7.11319pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{14.22638pt}{-21.33957pt}\pgfsys@curveto{0.0pt}{-21.33957pt}{0.0pt}{21.33957pt}{14.22638pt}{21.33957pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{21.33957pt}{-14.22638pt}\pgfsys@curveto{7.11319pt}{-14.22638pt}{7.11319pt}{14.22638pt}{21.33957pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{28.45276pt}{-7.11319pt}\pgfsys@curveto{14.22638pt}{-7.11319pt}{14.22638pt}{7.11319pt}{28.45276pt}{7.11319pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{14.22638pt}{21.33957pt}\pgfsys@lineto{45.52458pt}{21.33957pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{21.33957pt}{14.22638pt}\pgfsys@lineto{56.90552pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{7.11319pt}\pgfsys@lineto{56.90552pt}{7.11319pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{14.22638pt}{-21.33957pt}\pgfsys@lineto{42.67914pt}{-21.33957pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{21.33957pt}{-14.22638pt}\pgfsys@lineto{49.79233pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{-7.11319pt}\pgfsys@lineto{56.90552pt}{-7.11319pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{14.22638pt}{-21.33957pt}\pgfsys@curveto{0.0pt}{-21.33957pt}{0.0pt}{21.33957pt}{14.22638pt}{21.33957pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{14.22638pt}{-21.33957pt}\pgfsys@lineto{42.67914pt}{-21.33957pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{49.79233pt}{-14.22638pt}\pgfsys@curveto{56.90552pt}{-14.22638pt}{56.90552pt}{-42.67914pt}{49.79233pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{42.67914pt}{-21.33957pt}\pgfsys@curveto{49.79233pt}{-21.33957pt}{49.79233pt}{-35.56595pt}{42.67914pt}{-35.56595pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{-42.67914pt}{-21.33957pt}\pgfsys@curveto{-49.79233pt}{-21.33957pt}{-49.79233pt}{-35.56595pt}{-42.67914pt}{-35.56595pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{}}{}{{}}{}{}{}{}\pgfsys@moveto{-49.79233pt}{-14.22638pt}\pgfsys@curveto{-56.90552pt}{-14.22638pt}{-56.90552pt}{-42.67914pt}{-49.79233pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{42.67914pt}{-35.56595pt}\pgfsys@lineto{-42.67914pt}{-35.56595pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{-49.79233pt}{-42.67914pt}\pgfsys@lineto{49.79233pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{} {}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.8,0.8,1}\pgfsys@color@rgb@fill{0.8}{0.8}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-42.67914pt}{-2.84544pt}\pgfsys@moveto{-42.67914pt}{-2.84544pt}\pgfsys@lineto{-42.67914pt}{-24.18501pt}\pgfsys@lineto{-25.6073pt}{-24.18501pt}\pgfsys@lineto{-25.6073pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{-25.6073pt}{-24.18501pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.8,0.8,1}\pgfsys@color@rgb@fill{0.8}{0.8}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{42.67914pt}{-2.84544pt}\pgfsys@moveto{42.67914pt}{-2.84544pt}\pgfsys@lineto{42.67914pt}{-24.18501pt}\pgfsys@lineto{25.6073pt}{-24.18501pt}\pgfsys@lineto{25.6073pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{25.6073pt}{-24.18501pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-38.10223pt}{-16.93188pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$U$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.10645pt}{-17.9041pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\,U^{\dagger}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{46.21214pt}{19.79457pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.6}{$\ket{0^{a}}$}}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{{}{}}}{{}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-54.9882pt}{19.79457pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.6}{$\bra{0^{a}}$}}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{64.70625pt}{8.66621pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.6}{$\mathrm{in}$}}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{64.70625pt}{-8.95842pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.6}{$\mathrm{out}$}}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}}{{}} {}
{}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}}
}}{{}}{{}}}
{}\pgfsys@moveto{61.17325pt}{7.11319pt}\pgfsys@moveto{61.17325pt}{7.11319pt}\pgfsys@curveto{61.77325pt}{7.37991pt}{62.17325pt}{8.00233pt}{62.17325pt}{8.89148pt}\pgfsys@lineto{62.17325pt}{8.8915pt}\pgfsys@curveto{62.17325pt}{9.78064pt}{62.57324pt}{10.40306pt}{63.17325pt}{10.66978pt}\pgfsys@curveto{62.57324pt}{10.93651pt}{62.17325pt}{11.55893pt}{62.17325pt}{12.44807pt}\pgfsys@lineto{62.17325pt}{12.44809pt}\pgfsys@curveto{62.17325pt}{13.33723pt}{61.77325pt}{13.95966pt}{61.17325pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$
$\displaystyle=\bra{0^{a}}_{\mathrm{aux}}{\left((I^{\otimes
n}\otimes\mathcal{E}_{U}){\left(\ket{\mathrm{EPR}_{n+a}}\\!\\!\bra{\mathrm{EPR}_{n+a}}\right)}\right)}\ket{0^{a}}_{\mathrm{aux}}$
Figure 6: Tensor network diagram for $\Phi_{U}$ where we adopt the standard
convention that

$U$

$\,=U^{\top}$ and write $m\mathrel{\mathop{\mathchar 58\relax}}=n+a$ for the
total number of qubits. Our register labelling follows Figure 3.

This relationship between channels with and without clean auxiliary qubits
immediately allows us to extend our concentration results via the following
Proposition.

######  Proposition 25.

Suppose $\mathcal{E}$ is a quantum channel mapping $(n+a)$ to $1$ qubits, and
$\mathcal{E}^{\prime}$ is the following quantum channel mapping $n$ to $1$
qubits.

$\mathcal{E}^{\prime}(\rho)=\mathcal{E}(\rho\otimes\ket{0^{a}}\\!\\!\bra{0^{a}}),\qquad\rho\in\mathcal{M}_{N}$

Then $\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]\leq
2^{a}\cdot\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]$ for each
$k\in\\{0,1,\dots,n+1\\}$.

###### Proof.

By Equation 16, we can express the Pauli coefficients of
$\Phi_{\mathcal{E}^{\prime}}$ as

$\displaystyle\widehat{\Phi_{\mathcal{E}^{\prime}}}(P)=\sum_{Q\in\mathcal{P}_{a}}\widehat{\Phi_{\mathcal{E}}}(P\otimes
Q)\bra{0^{a}}Q\ket{0^{a}}=\sum_{Q\in\\{I,Z\\}^{\otimes
a}}\widehat{\Phi_{\mathcal{E}}}(P\otimes Q)$ (17)

for each $P\in\mathcal{P}_{n+1}$. Now, making use of the Cauchy Schwarz
inequality, we get our desired bound on
$\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]$:

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]$
$\displaystyle=\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\mathrel{\mathop{\mathchar
58\relax}}\\\ |P|>k\end{subarray}}{\left|\sum_{Q\in\\{I,Z\\}^{\otimes
a}}\widehat{\Phi_{\mathcal{E}}}(P\otimes Q)\right|}^{2}$ $\displaystyle\leq
2^{a}\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\mathrel{\mathop{\mathchar
58\relax}}\\\ |P|>k\end{subarray}}\sum_{Q\in\\{I,Z\\}^{\otimes
a}}{\left|\widehat{\Phi_{\mathcal{E}}}(P\otimes Q)\right|}^{2}$
$\displaystyle=2^{a}\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]$

which completes the proof. ∎

####  3.2.2 “Dirty” Auxiliary States

In contrast with a _clean_ auxiliary state that is always initialized to the
$\ket{0^{a}}$ state, we consider the case where the auxiliary state given to
the circuit is _dirty_ , that is there is no guarantee what the auxiliary
state will be, yet the circuit still has the desired behavior. This
corresponds to an auxiliary state that is maximally mixed
($\psi=\frac{1}{2^{a}}I^{\otimes a}$):

$\displaystyle\mathcal{E}^{\prime}(\rho)=\mathcal{E}{\left(\rho\otimes\tfrac{1}{2^{a}}I^{\otimes
a}\right)}.$

Following a similar argument to that used for “clean” auxiliary states, one
can show that

$\displaystyle\Phi_{\mathcal{E}^{\prime}}=\frac{1}{2^{a}}\cdot\operatorname*{Tr}_{\mathrm{aux}}{\left(\Phi_{\mathcal{E}}\right)}\qquad\text{and}\qquad\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]\leq\mathbf{W}^{>k}[\Phi_{\mathcal{E}}],\quad\text{for
each }k\geq 1.$ (18)

As opposed to clean auxiliary states, dirty auxiliary states cannot blow up
high-degree Pauli weight, and can be considered “free.” Below we prove
analogous statements for general auxiliary states of which both dirty and
clean auxiliary states are a special case.

####  3.2.3 Arbitrary Auxiliary States

More generally, we consider channels that have access to arbitrary auxiliary
states, that are not necessarily pure states. As we will see in the following
Proposition, the Choi representation of such channels is also conveniently
related to the auxiliary-free channel.

######  Proposition 26.

Let $\mathcal{E}$ be a quantum channel mapping $n+a$ qubit states to single
qubit states, and let $\psi\in\mathcal{M}_{2^{a}}$ be a quantum state. Let
$\mathcal{E}^{\prime}$ be the $n$ to $1$ qubit channel resulting from fixing
the last $a$ input qubits of $\mathcal{E}$ to $\psi$.

$\displaystyle\mathcal{E}^{\prime}(\rho)=\mathcal{E}(\rho\otimes\psi)\qquad\text{for}~{}\rho\in\mathcal{M}_{N}.$

We label the registers of $\Phi_{\mathcal{E}}$, as $\mathrm{in}$ ($n$ qubits),
$\mathrm{out}$ (1 qubit), $\mathrm{aux}$ ($a$ qubits) as follows.

$\displaystyle\Phi_{\mathcal{E}}={\left(I^{\otimes n}_{\mathrm{in}}\otimes
I^{\otimes
a}_{\mathrm{aux}}\otimes\mathcal{E}_{\mathrm{out}}\right)}{\left(\ket{\mathrm{EPR}_{n+a}}\\!\\!\bra{\mathrm{EPR}_{n+a}}_{(\mathrm{in},\mathrm{aux}),\mathrm{out}}\right)}.$

Then
$\Phi_{\mathcal{E}^{\prime}}=\operatorname*{Tr}_{\mathrm{aux}}{\left(\Phi_{\mathcal{E}}(I^{\otimes
n}_{\mathrm{in}}\otimes(\psi^{\top})_{\mathrm{aux}}\otimes
I_{\mathrm{out}})\right)}$.

###### Proof.

We have

$\displaystyle\operatorname*{Tr}_{\mathrm{aux}}{\left(\Phi_{\mathcal{E}}{\left(I^{\otimes
n+1}_{A^{c}}\otimes\psi^{\top}_{\mathrm{aux}}\right)}\right)}$
$\displaystyle=\sum_{\begin{subarray}{c}x,x^{\prime}\in\\{0,1\\}^{n}\\\
y,y^{\prime}\in\\{0,1\\}^{a}\end{subarray}}\operatorname*{Tr}_{\mathrm{aux}}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes{\left(|{y}\rangle\langle{y^{\prime}}|\psi^{\top}\right)}_{\mathrm{aux}}\otimes\mathcal{E}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes|{y}\rangle\langle{y^{\prime}}|\right)}\right)}$
$\displaystyle=\sum_{\begin{subarray}{c}x,x^{\prime}\in\\{0,1\\}^{n}\\\
y,y^{\prime}\in\\{0,1\\}^{a}\end{subarray}}\mbox{\rm
Tr}{\left(|{y}\rangle\langle{y^{\prime}}|\psi^{\top}\right)}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes\mathcal{E}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes|{y}\rangle\langle{y^{\prime}}|\right)}\right)}$
$\displaystyle=\sum_{x,x^{\prime}\in\\{0,1\\}^{n}}|{x}\rangle\langle{x^{\prime}}|\otimes\mathcal{E}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes{\left(\sum_{y,y^{\prime}\in\\{0,1\\}^{a}}\bra{y^{\prime}}\psi^{\top}\ket{y}|{y}\rangle\langle{y^{\prime}}|\right)}\right)}$
$\displaystyle=\sum_{x,x^{\prime}\in\\{0,1\\}^{n}}|{x}\rangle\langle{x^{\prime}}|\otimes\mathcal{E}{\left(|{x}\rangle\langle{x^{\prime}}|\otimes\psi\right)}=\Phi_{\mathcal{E}}$

where in the third equality we used the fact that $\mathcal{E}$ is a linear
map. ∎

Next, we generalize Proposition 25 for arbitrary auxiliary quantum states.
Upon restricting $a$ of the input qubits of a channel $\mathcal{E}$ to be the
state $\psi\in\mathcal{M}_{2^{a}}$, we see that the high degree weight of the
Choi representation blows up by at most
$2^{a}\mathinner{\\!\left\lVert\psi\right\rVert}_{F}^{2}$.

######  Proposition 27.

Let $\mathcal{E},\mathcal{E}^{\prime},\psi$ be as in Proposition 26. Then

$\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]\leq
2^{a}\cdot\mathinner{\\!\left\lVert\psi\right\rVert}_{F}^{2}\cdot\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]\text{
for each }k\in\\{0,1,\dots n+1\\}.$

###### Proof.

As shown in Proposition 26, we have
$\Phi_{\mathcal{E}^{\prime}}=\operatorname*{Tr}_{\mathrm{aux}}{\left(\Phi_{\mathcal{E}}(I^{\otimes
n}_{\mathrm{in}}\otimes(\psi^{\top})_{\mathrm{aux}}\otimes
I_{\mathrm{out}})\right)}$. Therefore,

$\displaystyle\widehat{\Phi_{\mathcal{E}^{\prime}}}(P)=\sum_{Q\in\mathcal{P}_{a}}\widehat{\Phi_{\mathcal{E}}}(P\otimes
Q)\operatorname*{Tr}(Q\psi^{\top})$ $\displaystyle\text{for each
}P\in\mathcal{P}_{n+1}.$ (19)

And so,

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]$
$\displaystyle=\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\\\
|P|>k\end{subarray}}{\left|\widehat{\Phi_{\mathcal{E}}}(P)\right|}^{2}=\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\\\
|P|>k\end{subarray}}{\left|\sum_{Q\in\mathcal{P}_{a}}\widehat{\Phi_{\mathcal{E}}}(P\otimes
Q)\cdot\operatorname*{Tr}(Q\psi^{\top})\right|}^{2}.$

Using the Cauchy Schwarz inequality, we can upper-bound this with

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]$
$\displaystyle\leq{\left(\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\\\
|P|>k\end{subarray}}\sum_{Q\in\mathcal{P}_{a}}{\left|\widehat{\Phi_{\mathcal{E}}}(P\otimes
Q)\right|}^{2}\right)}{\left(\sum_{Q^{\prime}\in\mathcal{P}_{a}}{\left|\operatorname*{Tr}(Q\psi^{\top})\right|}^{2}\right)}$
(20)

We can upper-bound the expression inside the first set of parenthesis with

$\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n+1}\\\
|P|>k\end{subarray}}\sum_{Q\in\mathcal{P}_{a}}{\left|\widehat{\Phi_{\mathcal{E}}}(P\otimes
Q)\right|}^{2}\leq\mathbf{W}^{>k}[\Phi_{\mathcal{E}}].$

Furthermore, note that for each $Q\in\mathcal{P}_{a}$, we have
$\operatorname*{Tr}(Q\psi^{\top})=2^{a}\widehat{\psi^{\top}}(Q)$. Combining
this with Parseval’s equation (Equation 7), the sum in the second set of
parenthesis in Equation 20 is equal to

$\displaystyle\sum_{Q^{\prime}\in\mathcal{P}_{a}}{\left|\operatorname*{Tr}(Q\psi^{\top})\right|}^{2}=2^{2a}\sum_{Q^{\prime}\in\mathcal{P}_{a}}{\left|\widehat{\psi^{\top}}(Q^{\prime})\right|}^{2}=2^{a}\mathinner{\\!\left\lVert\psi\right\rVert}_{F}^{2}.$

Plugging these into Equation 20 we get our desired inequality.

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}^{\prime}}]$ $\displaystyle\leq
2^{a}\mathinner{\\!\left\lVert\psi\right\rVert}_{F}^{2}\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]$

which completes the proof. ∎

Combining Proposition 27 and Theorem 19 we immediately get the following
Theorem.

######  Theorem 28.

Let $C$ be an $(n+a)$-qubit $\mathsf{QAC}$ circuit of depth $d$ and size $s$.
Let $\psi\in\mathcal{M}_{2^{a}}$ be an $a$-qubit quantum state. For each
$k\in[n+1]$,

$\displaystyle\mathbf{W}^{>k}[\Phi_{C,\psi}]\leq O{\left(s^{2}\cdot
2^{a-k^{1/d}}\mathinner{\\!\left\lVert\psi\right\rVert}_{F}^{2}\right)}.$ (21)

We note that the settings discussed at the start of this subsection, where the
auxiliary state is either _clean_ ($\ket{0^{a}}\\!\\!\bra{0^{a}}$) or _dirty_
($2^{-a}I^{\otimes a}$) are special cases of Theorem 28.

Note that this concentration bound is unaffected by the number of dirty
auxiliary qubits. Furthermore, the bound does not change if instead of
$\ket{0^{c}}$ we used an arbitrary $c$-qubit pure state, including states such
as $\ket{\textsf{CAT}_{c}}$ state which are believed to require $\mathsf{QAC}$
depth $\Omega(\log(c))$ to prepare.

###  3.3 $\mathsf{QAC}^{0}$ Lower Bounds for Parity and Majority

In this section, we consider Boolean functions $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ and show that when viewing them as a
quantum channel $\mathcal{E}_{f}$, their Pauli spectrum is essentially the
same as their Fourier spectrum. Using this observation, we connect our low-
degree concentration results from the previous section to prove correlation
bounds against $\mathsf{QAC}^{0}$ circuits with limited auxiliary qubits for
computing high-degree Boolean functions. In particular, we provide explicit
bounds for $\mathrm{Parity}_{n}$ and $\mathrm{Majority}_{n}$ functions.

The following proposition relates the Fourier spectrum of a Boolean function
$f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ to the Pauli
spectrum this function, viewed as a quantum channel as discussed above. We
refer the reader to [O’D14] for further background.

######  Proposition 29.

Suppose $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ is a
Boolean function. Let $\mathcal{E}_{f}$ be the channel mapping $n$ qubits to a
$1$-qubit state as follows:

$\displaystyle\mathcal{E}_{f}(\rho)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{x\in\\{0,1\\}^{n}}\bra{x}\rho\ket{x}\ket{f(x)}\\!\\!\bra{f(x)},$
$\displaystyle\Phi_{\mathcal{E}_{f}}=\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\\!\bra{x}\otimes\ket{f(x)}\\!\\!\bra{f(x)}.$
(22)

Then we have

$\Phi_{\mathcal{E}_{f}}=\frac{1}{2}{\left(I^{\otimes(n+1)}+\sum_{S\subseteq[n]}\widehat{f}(S)Z_{S}\otimes
Z\right)}$

where $Z_{S}$ is defined in Equation 8 and $\widehat{f}(S)=\operatorname{{\bf
E}}_{x\sim\\{0,1\\}^{n}}[(-1)^{f(x)}\chi_{S}(x)]$ 111111Recall from Section
1.3.1 that $\chi_{S}(x)\mathrel{\mathop{\mathchar 58\relax}}=\prod_{i\in
S}x_{i}$.

###### Proof.

For convenience, we will write $\mathcal{E}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{E}_{f}$ and $\Phi\mathrel{\mathop{\mathchar
58\relax}}=\Phi_{\mathcal{E}_{f}}$ throughout the proof. Note that

$\displaystyle I^{\otimes
n}\otimes\mathcal{E}{\left(\ket{\mathrm{EPR}_{n}}\\!\\!\bra{\mathrm{EPR}_{n}}\right)}$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\\!\bra{x}\otimes{\left(\sum_{y\in\\{0,1\\}^{n}}\braket{y}{x}\\!\\!\braket{x}{y}\ket{f(y)}\\!\\!\bra{f(y)}\right)}$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\\!\bra{x}\otimes\ket{f(x)}\\!\\!\bra{f(x)}.$
(23)

It is straightforward to check that the Pauli decomposition of
$\ket{x}\\!\\!\bra{x}$ is given by

$\ket{x}\\!\\!\bra{x}=\frac{1}{2^{n}}\sum_{y\in\\{0,1\\}^{n}}(-1)^{x\cdot
y}Z_{y}$

where we identify $y\in\\{0,1\\}^{n}$ with the indicator string of the set
$S\mathrel{\mathop{\mathchar 58\relax}}=\\{i\in[n]\mathrel{\mathop{\mathchar
58\relax}}y_{i}=1\\}$. Combining this with Equation 23, we get that

$\displaystyle I^{\otimes
n}\otimes\mathcal{E}{\left(\ket{\mathrm{EPR}_{n}}\\!\\!\bra{\mathrm{EPR}_{n}}\right)}$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}{\left(\frac{1}{2^{n}}\sum_{y\in\\{0,1\\}^{n}}(-1)^{x\cdot
y}Z_{y}\right)}\otimes{\left(\frac{1}{2}\sum_{b\in\\{0,1\\}}(-1)^{f(x)\cdot
b}Z_{b}\right)}$
$\displaystyle=\frac{1}{2}\sum_{\begin{subarray}{c}y\in\\{0,1\\}^{n}\\\
b\in\\{0,1\\}\end{subarray}}{{\left(\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{x\cdot
y+f(x)\cdot b}\right)}}Z_{y}\otimes Z_{b}.$

Note, however, that

${{\frac{1}{2^{n}}\sum_{y\in\\{0,1\\}^{n}}(-1)^{x\cdot y+f(x)\cdot
b}}}=\begin{cases}\mathbf{1}{\left\\{y=0^{n}\right\\}}&\text{if}~{}b=0\\\
\widehat{f}(y)&\text{if}~{}b=1\end{cases}$

where we once again identify $y$ with a subset $S\mathrel{\mathop{\mathchar
58\relax}}=\\{i\in[n]\mathrel{\mathop{\mathchar 58\relax}}y_{i}=1\\}$, and so
we have

$\displaystyle I^{\otimes
n}\otimes\mathcal{E}{\left(\ket{\mathrm{EPR}_{n}}\\!\\!\bra{\mathrm{EPR}_{n}}\right)}=\frac{1}{2}{\left(I^{\otimes(n+1)}+\sum_{S\subseteq[n]}\widehat{f}(S)Z_{S}\otimes
Z\right)}.$ (24)

Now that we have shown the correspondence between the Pauli spectrum and the
Fourier spectrum of $f$, we next bound the correlation between a quantum
channel and a Boolean function entirely in terms of their Pauli and Fourier
spectra respectively.

######  Proposition 30.

Suppose $\mathcal{E}$ is an $n$ to $1$-qubit channel. For each
$x\in\\{0,1\\}^{n}$ let random variable $Q_{\mathcal{E}}(x)\in\\{0,1\\}$ be
the outcome of measuring $\mathcal{E}(\ket{x}\\!\\!\bra{x})$ in the
computational basis. Then for each $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ and each $k\in[n+1]$,

$\displaystyle\mathop{{\bf
Pr}\/}_{x\in\\{0,1\\}^{n}}{\left[Q_{\mathcal{E}}(x)=f(x)\right]}\leq
1-\frac{1}{2}\sqrt{\mathbf{W}^{>k-1}(f)}+\sqrt{\mathbf{W}^{>k}(\Phi_{\mathcal{E}})}.$

###### Proof.

Let $\mathcal{E},f$ be as in Proposition 30, and let $\mathcal{E}_{f}$ be as
defined in Proposition 29. Let $\widetilde{\mathcal{E}}$ be the _classical
version_ of $\mathcal{E}$. That is, the channel resulting from applying a
computational basis measurement before and after applying $\mathcal{E}$.

$\displaystyle\widetilde{\mathcal{E}}{}(\rho)=M_{1}{\left(\mathcal{E}(M_{n}(\rho)))\right)}$
$\displaystyle\rho\in\mathcal{M}_{N}$

Where $M_{\ell}$ denotes the $\ell$-qubit measurement channel: for each $x\neq
x^{\prime}\in\\{0,1\\}^{\ell}$,
$M_{\ell}{\left(\ket{x}\\!\\!\bra{x}\right)}=\ket{x}\\!\\!\bra{x}$ and
$M_{\ell}{\left(|{x}\rangle\langle{x^{\prime}}|\right)}=0$.

For each $x\in\\{0,1\\}^{n}$, we denote $w_{x}=\operatorname{{\bf
Pr}}{\left[Q_{\mathcal{E}}(x)\neq f(x)\right]}$, so that the probability that
$Q_{\mathcal{E}}$ is incorrect is $\mathop{{\bf E}\/}_{x}[w_{x}]$. We first
observe that for each $x\in\\{0,1\\}^{n}$, we can express $w_{x}$ in terms of
the distance in Frobenius norm between the outputs of
$\widetilde{\mathcal{E}}$ and $\mathcal{E}_{f}$ on input $x$.

$\displaystyle w_{x}$
$\displaystyle=\frac{1}{\sqrt{2}}\mathinner{\\!\left\lVert\widetilde{\mathcal{E}}{\left(\ket{x}\\!\\!\bra{x}\right)}-\mathcal{E}_{f}{\left(\ket{x}\\!\\!\bra{x}\right)}\right\rVert}_{F}$

Using the fact that $w_{x}\in[0,1]$,

$\displaystyle\mathop{{\bf E}\/}_{x}[w_{x}]\geq\mathop{{\bf
E}\/}_{x}[w_{x}^{2}]$ $\displaystyle=\mathop{{\bf
E}\/}_{x}\frac{1}{2}\mathinner{\\!\left\lVert\widetilde{\mathcal{E}}{\left(\ket{x}\\!\\!\bra{x}\right)}-\mathcal{E}_{f}{\left(\ket{x}\\!\\!\bra{x}\right)}\right\rVert}_{F}^{2}.$

We will show how we can write this in terms of the Choi representations of
$\mathcal{E}$ and $\mathcal{E}_{f}$. It is easy to verify that

$\displaystyle\mathop{{\bf
E}\/}_{x\in\\{0,1\\}^{n}}\frac{1}{2}\mathinner{\\!\left\lVert{\left(\widetilde{\mathcal{E}}{}-\mathcal{E}_{f}\right)}{\left(\ket{x}\\!\\!\bra{x}\right)}\right\rVert}_{F}^{2}$
$\displaystyle=\frac{1}{2^{n+1}}\mathinner{\\!\left\lVert\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\\!\bra{x}\otimes(\widetilde{\mathcal{E}}{}-\mathcal{E}_{f})(\ket{x}\\!\\!\bra{x})\right\rVert}_{F}^{2}$
$\displaystyle=\frac{1}{2^{n+1}}\mathinner{\\!\left\lVert\sum_{x,x^{\prime}\in\\{0,1\\}^{n}}|{x}\rangle\langle{x^{\prime}}|\otimes(\widetilde{\mathcal{E}}{}-\mathcal{E}_{f})(|{x}\rangle\langle{x^{\prime}}|)\right\rVert}_{F}^{2}$
$\displaystyle=\frac{1}{2^{n+1}}\mathinner{\\!\left\lVert\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}_{f}}\right\rVert}_{F}^{2}.$

Where the second equality follows from that $\widetilde{\mathcal{E}}$ and
$\mathcal{E}_{f}$ are both classical in the sense that
$\widetilde{\mathcal{E}}(|{x}\rangle\langle{x^{\prime}}|)=\mathcal{E}_{f}|{x}\rangle\langle{x^{\prime}}|=0$
for all $x\neq x^{\prime}\in\\{0,1\\}^{n}$. Furthermore, the Choi
representation for $\widetilde{\mathcal{E}}$ is equivalent to the measured
Choi representation for $\mathcal{E}$:
$\Phi_{\widetilde{\mathcal{E}}}=M_{n+1}{\left(\Phi_{\mathcal{E}}\right)}$. So

$\displaystyle\mathop{{\bf
E}\/}_{x}[w_{x}]\geq\frac{1}{2^{n+1}}\mathinner{\\!\left\lVert\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}_{f}}\right\rVert}_{F}^{2}=\frac{1}{2^{n+1}}\mathinner{\\!\left\lVert
M_{n+1}{\left(\Phi_{\mathcal{E}}\right)}-\Phi_{\mathcal{E}_{f}}\right\rVert}_{F}^{2}.$

We will upper bound this in terms of the Pauli spectrum of
$\Phi_{\mathcal{E}}$ and $\Phi_{\mathcal{E}_{f}}$. Now using Parseval’s
equation (Equation 7), it holds that for each $k\in\\{0,\dots,n+1\\}$

$\displaystyle\mathop{{\bf E}\/}_{x}[w_{x}]$
$\displaystyle\geq\mathbf{W}^{>k}{\left[M(\Phi_{\mathcal{E}})-\Phi_{\mathcal{E}_{f}}\right]}$
(25)
$\displaystyle\geq{\left(\sqrt{\mathbf{W}^{>k}{\left[\Phi_{\mathcal{E}_{f}}\right]}}-\sqrt{\mathbf{W}^{>k}{\left[M(\Phi_{\mathcal{E}})\right]}}\right)}^{2}.$
(26)

In the last inequality we used the reverse triangle inequality:
$\mathinner{\\!\left\lVert
a-b\right\rVert}\geq{\left|\mathinner{\\!\left\lVert
a\right\rVert}-\mathinner{\\!\left\lVert b\right\rVert}\right|}$. Next, we
observe that the application of the measurement channel $M$ to any
$A\in\mathcal{M}_{2N}$ does not increase its Pauli weight at _any_ level:
$\mathbf{W}^{k}[M(A)]\leq\mathbf{W}^{k}[A]$ for each $k\geq 0$. This is
because the measurement has the effect of either preserving a Pauli
coefficient or mapping it to 0. To illustrate this, consider that when the
single-qubit measurement channel is applied to the $i$th qubit of a Pauli $P$,
it leaves $P$ unchanged if $P_{i}\in\\{I,Z\\}$ and maps $P$ to $0$ if
$P_{i}\in\\{X,Y\\}$. Consequently, for each $k\in[n+1]$, we have
$\mathbf{W}^{>k}{\left[M(\Phi_{\mathcal{E}})\right]}\leq\mathbf{W}^{>k}{\left[\Phi_{\mathcal{E}}\right]}$.

Finally, by Proposition 29, we establish that for each $k\geq 1$,
$\mathbf{W}^{>k}{\left[\Phi_{\mathcal{E}_{f}}\right]}=\frac{1}{4}\mathbf{W}^{>k-1}{\left[f\right]}$.
Combining this with the previous equation, we arrive at our desired expression

$\displaystyle\mathop{{\bf
E}\/}_{x}w_{x}\geq\frac{1}{2}\sqrt{\mathbf{W}^{>k-1}{\left[f\right]}}+\sqrt{\mathbf{W}^{>k}{\left[\Phi_{\mathcal{E}}\right]}},$

which completes the proof. ∎

Combining Proposition 30 with our concentration bound Theorem 16, directly
implies the following theorem:

######  Theorem 31.

Suppose $C$ is a $\mathsf{QAC}$ circuit with depth $d$ and size $s$ and $\psi$
is a $a$-qubit auxiliary state. For each $x\in\\{0,1\\}^{n}$, let
$C(x)\in\\{0,1\\}$ be the random variable indicating the standard basis
measurement outcome of $\mathcal{E}_{C,\psi}(\ket{x}\\!\\!\bra{x})$. Then for
each Boolean function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$,

$\displaystyle\mathop{{\bf
Pr}\/}_{x\in\\{0,1\\}^{n}}{\left[C(x)=f(x)\right]}\leq
1-\frac{1}{2}\sqrt{\mathbf{W}^{>k-1}[f]}+O{\left(s\cdot
2^{-k^{1/d}/2}\right)}\cdot 2^{a/2}$ (27)

In particular,

$\displaystyle\mathop{{\bf
Pr}\/}_{x}{\left[C(x)=\mathrm{Parity}(x)\right]}\leq\frac{1}{2}+O{\left(s\cdot
2^{-(n^{1/d}-a)/2}\right)}$ (28)

and

$\displaystyle\mathop{{\bf
Pr}\/}_{x}{\left[C(x)=\mathrm{Majority}(x)\right]}\leq
1-\Omega{\left(\frac{1}{\sqrt{n}}\right)}+2^{-\Omega{\left(n^{1/d}-a-\log
s\right)}}.$ (29)

###### Proof.

Equation 27 follows directly from combining Proposition 30 and Theorem 16. The
Parity bound (Equation 28) is achieved by plugging in $k=n-1$, since
$\mathbf{W}^{>n-1}[\mathrm{Parity}_{n}]=1$. The majority bound is achieved by
$k=\Omega(n)$ since
$\mathbf{W}^{>k}{\left[\mathrm{Majority}\right]}\geq\frac{1}{\sqrt{k}}$. ∎

This completes the proof. ∎

######  Remark 32.

More generally, we note that Theorem 16 implies that $\mathsf{QAC}^{0}$
circuits with $\frac{1}{2}n^{1/d}$ clean auxiliary qubits cannot compute a
Boolean function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ that has a non-zero amount of mass on
sufficiently high degree Fourier coefficients. As a consequence, as is the
case with the results of [LMN93], we obtain a lower bound against
$\mathsf{QAC}^{0}$ circuits computing Boolean functions with large _total
influence_ (cf. Chapter 2 of [O’D14]) and more generally for unitaries with
large total influence (in the sense of [CNY23]).

For the sake of simplicity, however, we restrict our attention to the parity
and majority functions and refer the interested reader to Section 5 of [LMN93]
(or alternatively Chapter 4 of [O’D14]) instead.

##  4 Learning Low-Degree Channels

We will now leverage our concentration result to propose a learning algorithm
for $\mathsf{QAC}^{0}$ circuits. More generally, we establish quasipolynomial
sample complexity for learning the Choi representation of any low-degree
concentrated quantum channel. We consider channels $\mathcal{E}$ mapping $n$
input qubits to $\ell$ output qubits— not just single output channels. Recall
that the Choi representation of the channel $\Phi_{\mathcal{E}}$ is of
dimension $M\times M$ where $M\mathrel{\mathop{\mathchar 58\relax}}=2^{m}$ and
$m=n+\ell$. Recall that a quantum channel $\mathcal{E}$ or its Choi
representation $\Phi_{\mathcal{E}}$ is $\epsilon$-_concentrated up to degree_
$k$, if $\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]\leq\epsilon$.

For our primary discussion of the learning procedure, we will consider a
learning model in which we are given access to many copies of Choi state, i.e.
the normalized Choi representation121212Note that Choi state tomography is
often referred to as the “ancilla-assisted” learning model [Leu00, MRL08].
$\rho_{\mathcal{E}}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\Phi_{\mathcal{E}}}{\operatorname*{Tr}(\Phi_{\mathcal{E}})}=\frac{1}{N}\Phi_{\mathcal{E}}$.
Indeed, the Choi state is a valid quantum state as it has $\mbox{\rm
Tr}(\rho_{\mathcal{E}})=1$ and is Hermitian. The Choi state can be prepared by
applying the channel $\mathcal{E}$ to half of $n$ (normalized) Bell pairs.
Thus this is weaker than given general query access to $\mathcal{E}$. We note
that a Choi state is a generalization of sampling a random example $(x,f(x))$
of a Boolean function — as these are equivalent when the channel is
$\mathcal{E}_{f}$.

With this background, we can now state the main result of the section:

######  Theorem 33 (Quantum Low-Degree Learning).

Let $k\geq 1$ and let $\mathcal{E}$ be an $n$\- to $\ell$-qubit quantum
channel that is $\epsilon/2$-concentrated up to Pauli degree $k$. Denote
$m=n+\ell$ as the total number of input and output qubits of the channel. Then
there exists an algorithm, which given
$O{\left((3m)^{k}\cdot\frac{1}{4^{\ell}\epsilon}\cdot\log(1/\delta)\right)}$
copies of the Choi state, outputs a description of quantum channel
$\widetilde{\mathcal{E}}$ such that
$\frac{1}{M}\mathinner{\\!\left\lVert\Phi_{\mathcal{E}}-\Phi_{\widetilde{\mathcal{E}}}\right\rVert}_{F}^{2}\leq\epsilon$
with probability at least $1-\delta$.

In the special case where $\mathcal{E}$ is the classical channel for Boolean
function $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$,
learning approximately low-degree functions is a direct corollary of our
result.

######  Corollary 34.

For each $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$
with Fourier weight that is $2\epsilon$-concentrated up to degree $k$, given
$O((3n)^{k}\frac{1}{\epsilon}\log(1/\delta))$ random examples $(x,f(x))$, we
can learn $\widetilde{f}$ such that $\operatorname{{\bf
Pr}}_{x}[f(x)\neq\widetilde{f}(x)]=\sqrt{\epsilon}$

###### Proof.

First note that
$\rho_{f}=\frac{1}{N}\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\\!\bra{x}\otimes\ket{f(x)}\\!\\!\bra{f(x)}$.
So given $\rho_{f}$ is equivalent to given a random example $(x,f(x))$ for $x$
drawn uniformly from $\\{0,1\\}^{n}$. Furthermore, by Proposition 29, we have
that since $f$ is $2\epsilon$-concentrated up to level $k$, then
$\mathcal{E}_{f}$ is $\epsilon/2$-concentrated up to level $k$. Therefore, by
Theorem 33 it follows that with
$O{\left((3m)^{k}\cdot\frac{1}{4^{\ell}\epsilon}\cdot\log(1/\delta)\right)}$
copies of the Choi state, with probability $1-\delta$, we learn a
$\widetilde{\Phi}$ such that
$\frac{1}{M}\mathinner{\\!\left\lVert\Phi_{f}-\widetilde{\Phi}\right\rVert}_{F}^{2}\leq\epsilon$.
Without loss of generality, we can assume that the Choi representation learned
by our algorithm is of the form in Proposition 29:
$\widetilde{\Phi}=\frac{1}{2}I+\sum_{S\subseteq[n]}\widehat{f}(S)Z_{S}\otimes
Z$ — since otherwise we could drop terms not of this form without increasing
our error. Thus $\widetilde{\Phi}$ is the Choi representation of some
probabilistic function $g$. Finally, observe that for any classical
deterministic function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$ and probabilistic function $g$,
$\operatorname{{\bf Pr}}_{x}[f(x)\neq
g(x)]=\frac{1}{\sqrt{2}}\operatorname{{\bf
E}}_{x}\mathinner{\\!\left\lVert\mathcal{E}_{f}(\ket{x}\\!\\!\bra{x})-\mathcal{E}_{g}(\ket{x}\\!\\!\bra{x})\right\rVert}_{F}\leq{\left(\frac{1}{2}\operatorname{{\bf
E}}_{x}\mathinner{\\!\left\lVert\mathcal{E}_{f}(\ket{x}\\!\\!\bra{x})-\mathcal{E}_{g}(\ket{x}\\!\\!\bra{x})\right\rVert}_{F}^{2}\right)}^{1/2}$.
Furthermore, it can be easily verified that since $\mathcal{E}_{f}$ and
$\widetilde{\mathcal{E}}$ are classical, $\frac{1}{2}\operatorname{{\bf
E}}_{x}\mathinner{\\!\left\lVert\mathcal{E}_{f}(\ket{x}\\!\\!\bra{x})-\mathcal{E}_{g}(\ket{x}\\!\\!\bra{x})\right\rVert}_{F}^{2}=\frac{1}{2N}\mathinner{\\!\left\lVert\Phi_{f}-\widetilde{\Phi}\right\rVert}_{F}^{2}=\frac{1}{M}\mathinner{\\!\left\lVert\Phi_{f}-\widetilde{\Phi}\right\rVert}_{F}^{2}\leq\epsilon$.
The result follows. ∎

We denote $\mathcal{F}_{k}$ as the subset of all Paulis of degree at most $k$.

$\mathcal{F}_{k}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{P\in\mathcal{P}_{m}\mathrel{\mathop{\mathchar
58\relax}}|P|\leq k\right\\}}.$

Note that the size of $|\mathcal{F}_{k}|$ is at most $O(m^{k})$.Our
construction follows a similar “meta-algorithm” for learning low-degree
Boolean function as outlined in Chapter 3 of [O’D14], based on original work
by [LMN93].

  1. 1.

Estimate Pauli Coefficients: For each of the low degree Paulis
$P\in\mathcal{F}_{k}$, we first learn an approximation $\widetilde{\Phi}(P)$
for $\widehat{\Phi}_{\mathcal{E}}(P)$ within additive error $\eta$. Setting
$\eta$ sufficiently small, we get an $\epsilon$-approximation to
$\Phi_{\mathcal{E}}$.

  2. 2.

Rounding: Round $\widetilde{\Phi}$ to the nearest
$\Phi_{\widetilde{\mathcal{E}}}$ such that $\widetilde{\mathcal{E}}$ is a
quantum channel. We design this convex projection to reduce distance from
$\Phi_{\mathcal{E}}$, ensuring that $\Phi_{\widetilde{\mathcal{E}}}$ is also
$\epsilon$-close to $\Phi_{\mathcal{E}}$.

Before proving Theorem 33, we first show how to obtain additive
$\eta$-approximations of the Choi representation coefficients
$\widetilde{\Phi}(P)$ for each low degree Pauli $P\in\mathcal{F}_{k}$.

######  Lemma 35.

For each $\delta,\epsilon\in(0,1)$, and $n$\- to $\ell$-qubit channel
$\mathcal{E}$, there exists an algorithm that given
$T=O{\left(\frac{3^{k}}{4^{\ell}\eta^{2}}\cdot\log(1/\delta)\right)}$ copies
of $\rho_{\mathcal{E}}$, outputs
$\\{\widetilde{\Phi_{\mathcal{E}}}(P)\\}_{P\in\mathcal{F}_{k}}$ such that
$|\widetilde{\Phi_{\mathcal{E}}}(P)-\widehat{\Phi}_{\mathcal{E}}(P)|\leq\eta$
for each $P\in\mathcal{F}_{k}$.

###### Proof.

We denote $\Phi=\Phi_{\mathcal{E}}$ and $\rho=\rho_{\mathcal{E}}$. Recall that
$\rho=\frac{1}{N}\Phi$. So we have that

$\operatorname*{Tr}(P\rho)=\frac{1}{N}\sum_{Q\in\mathcal{P}_{m}}\widehat{\Phi}(Q)\operatorname*{Tr}(PQ)=\widehat{\Phi}(P)\operatorname*{Tr}(I^{\otimes
m})=\frac{1}{2^{\ell}}\widehat{\Phi}(P).$

To approximate $\widehat{\Phi}(Q)$ to within $\eta$ additive error, it is
sufficient to approximate observable $\mbox{\rm Tr}(P\rho)$ to within
$\eta_{0}=\eta\cdot L$ additive error. A standard application of the Chernoff
bound gives that, with probability $1-\delta$, we can obtain a
$\pm\eta_{0}$-estimate $\widetilde{\rho}(Q)$ of $\mbox{\rm Tr}(Q\rho)$ by
performing
$O{\left(1/{\eta_{0}^{2}}\cdot\log{\left(1/{\delta}\right)}\right)}$
measurements of $\rho$ with respect to Pauli observable $Q$. Repeating this
procedure for each of the $O(m^{k})$ Paulis in $\mathcal{F}_{k}$,
$O\left(\frac{m^{k}}{\eta_{0}^{2}}\log\left(1/\delta\right)\right)$ samples
suffice to learn $\eta_{0}$-approximations of each of the low-degree Choi
state coefficients: $|\widehat{\rho}(Q)-\widetilde{\rho}(Q)|\leq\eta_{0}$ for
each $Q\in\mathcal{F}_{k}$. Already this gives us an algorithm to learn $\eta$
approximations of the Choi coefficients for $\mathcal{F}_{k}$ with sample
complexity

$O{\left(\frac{m^{k}}{4^{\ell}\eta^{2}}\log(1/\delta)\right)}.$

However, we can approximate the set of expectations
$\\{\operatorname*{Tr}(P\rho)\\}_{P\in\mathcal{F}_{k}}$ with even better
sample complexity by leveraging a well-established, sample-optimal quantum
tomography procedure, known as Classical Shadow Tomography (CST) due to Huang
et al. [HKP20] — which we use as a black-box.

######  Theorem 36 (Classical Shadow Tomography [HKP20] with Low-Degree Pauli
Observables).

Assume we are given an unknown $n$-qubit state $\rho$, and accuracy parameters
$\eta_{0},\delta\in[0,1]$, and

$\displaystyle
O{\left(\frac{3^{k}}{\eta_{0}^{2}}\log{\left(\frac{m^{k}}{\delta}\right)}\right)}$
(30)

copies of $\rho$ that we make random Pauli measurements on. Then with
probability at least $(1-\delta)$, we output an estimate
$\widetilde{s}(P)\in[-1,1]$ for each $P\in\mathcal{F}_{k}$ such that
${\left|\widetilde{s}(P)-\operatorname*{Tr}(P\rho)\right|}\leq\eta_{0}$.

By applying CST as in Theorem 36 on the Choi state with $\eta_{0}=\eta\cdot
L$, we get our desired sample complexity of
$O{\left(\frac{3^{k}}{4^{\ell}\eta^{2}}\log{\left(\frac{m^{k}}{\delta}\right)}\right)}$.
∎

In this work, we do not provide an explicit rounding procedure, but instead
treat finding the nearest Choi representation corresponding to a quantum
channel as a black box. In Section 4.2 we illustrate that the rounding task
can be described as a convex optimization problem. As far as the authors are
aware, it is currently unknown whether such a procedure can be done in time
$O(|\mathcal{F}_{k}|)$.

We are now equipped to prove Theorem 33.

###### Proof of Theorem 33.

Let $\eta=\sqrt{\frac{\epsilon}{2|\mathcal{F}_{k}|}}$, and suppose
$|\widetilde{\Phi}(P)-\widehat{\Phi}(P)|\leq\eta$ for each
$P\in\mathcal{F}_{k}$. Since $\Phi$ is $\epsilon/2$-concentrated up to level
$k$ we have that

$\displaystyle\sum_{P\in\mathcal{P}_{n}}\left|\widehat{\Phi}(P)-\widetilde{\Phi}(P)\right|^{2}$
$\displaystyle=\sum_{P\in\mathcal{F}_{k}}\left|\widehat{\Phi}(P)-\widetilde{\Phi}(P)\right|^{2}+\sum_{P\notin\mathcal{F}_{k}}\left|\widehat{\Phi}(P)\right|^{2}$
(31)
$\displaystyle\leq|\mathcal{F}_{k}|\cdot\frac{\epsilon}{2|\mathcal{F}_{k}|}+\frac{\epsilon}{2}=\epsilon.$
(32)

By Parseval’s (Equation 7) it follows that
$\frac{1}{M}\mathinner{\\!\left\lVert\Phi-\widetilde{\Phi}\right\rVert}_{F}^{2}\leq\frac{\epsilon}{2}$.
The next step is to round $\widetilde{\Phi}$ to the nearest Choi
representation $\Phi_{\widetilde{\mathcal{E}}}$ for a quantum channel
$\widetilde{\mathcal{E}}$. As we will discuss in Section 4.2, this rounding
can be formulated as a convex projection which will only further reduce the
error. Thus,

$\displaystyle\frac{1}{M}\mathinner{\\!\left\lVert\Phi-\Phi_{\widetilde{\mathcal{E}}}\right\rVert}_{F}^{2}\leq\frac{1}{M}\mathinner{\\!\left\lVert\Phi-\widetilde{\Phi}\right\rVert}_{F}^{2}\leq\epsilon.$

∎

###  4.1 Learning $\mathsf{QAC}^{0}$ Channels

Combining Theorem 33 with our low-degree concentration bound of
$\mathsf{QAC}^{0}$ in Section 3, a learning algorithm for $\mathsf{QAC}^{0}$
circuit immediately follows, which we describe in Section 4.1. All together,
the learning algorithm applied to $\mathsf{QAC}^{0}$ channels closely follows
the template of the “low-degree algorithm” introduced by Linial, Mansour, and
Nisan to learn $\mathsf{AC}^{0}$ circuits (see Section 1.3.1).

######  Theorem 37 (Quasipolynomial Learning of $\mathsf{QAC}^{0}$).

Let $C$ be a $(n+a)$-qubit $\mathsf{QAC}$ circuit of depth-$d$ and size-$s$
with $a\leq\frac{1}{2}\log{\left(s^{2}/\epsilon\right)}$. Let
$\mathcal{E}=\mathcal{E}_{C,\ket{0^{a}}}$. For each $\delta>0$ and error
$\epsilon$, we can learn a channel $\widetilde{\mathcal{E}}$, with
$\frac{1}{M}\mathinner{\\!\left\lVert\Phi_{\mathcal{E}}-\Phi_{\widetilde{\mathcal{E}}}\right\rVert}_{F}^{2}\leq\epsilon$
except with probability $\delta$, using
$T=n^{O{\left(\log^{d}(s^{2}/\epsilon)\right)}}\cdot\log\left(\frac{1}{\delta}\right)$
copies of the Choi state.

###### Proof.

Following from Theorem 28, the weight of $\mathcal{E}$ above level $k$ is at
most

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]\leq
O{\left(s^{2}2^{-k^{1/d}+a}\right)}.$

Setting $\widetilde{k}=\log^{d}(s^{2}/\epsilon)$ and using that
$a\leq\frac{1}{2}\log(s^{2}/\epsilon)=\widetilde{k}^{1/d}$, we see that
$\Phi_{\mathcal{E}}$ is $O(\epsilon)$-concentrated below $\widetilde{k}$, i.e.
$\mathbf{W}^{>\widetilde{k}}[\Phi_{\mathcal{E}}]\leq O(\epsilon)$.

Noting that the $\mathsf{QAC}^{0}$ channel has $\ell=1$ output qubits and
plugging this concentration degree bound into the sample complexity of Theorem
33 implies that the Quantum-Low-Degree-Algorithm uses

$\displaystyle O{\left(\frac{n^{2\widetilde{k}}}{\epsilon\cdot
4^{\ell}}\log{\left(\frac{n^{\widetilde{k}}}{\delta}\right)}\right)}=n^{O{\left(\log^{d}(s^{2}/\epsilon)\right)}}\cdot\log(1/\delta).$

copies of the Choi state, or pure state queries to learn an
$\epsilon$-approximation of $\Phi_{\mathcal{E}}$ with probability $1-\delta$.
∎

Note that naive tomography would result in a $O(4^{n})$ bound on the sample
complexity (and hence runtime) of learning the Choi representation $\Phi$.
Theorem 37 obtains significant savings by requiring only a quasi-polynomial
number of samples (When $\epsilon,\log(1/\delta)=O(1/\text{poly}(n))$).

###  4.2 Rounding onto a CPTP Map via Convex Optimization

Figure 7: The projection
$\Phi_{\widetilde{\mathcal{E}}}=\underset{\Phi\in\mathfrak{C}_{n,\ell}}{\arg\min}\>\|\widetilde{\Phi}-\Phi\|_{F}^{2}\in\mathfrak{C}_{n,\ell}$
maps the learned matrix $\widetilde{\Phi}\in\mathbb{C}^{M\times M}$ onto the
nearest valid Choi representation. Since the space of valid Choi
representations, $\mathfrak{C}_{n,\ell}$, is a closed convex set, the distance
between $\Phi_{\widetilde{\mathcal{E}}}$ and any other Choi representation
must be less than or equal to the distance between $\widetilde{\Phi}$ and any
Choi representation. Therefore, if $\widetilde{\Phi}$ is $\epsilon$-close to
$\Phi_{\mathcal{E}}\in\mathfrak{C}_{n,\ell}$, $\Phi_{\widetilde{\mathcal{E}}}$
is $\epsilon$-close to $\Phi_{\mathcal{E}}\in\mathfrak{C}_{n,\ell}$.

The final step of the Quantum-Low-Degree-Algorithm outlined in the previous
section is to round the learned matrix $\widetilde{\Phi}$, encoding a low-
degree approximation of $\Phi_{\mathcal{E}}$, to a Choi representation
$\Phi_{\widetilde{\mathcal{E}}}$, encoding a completely-positive trace-
preserving (CPTP) map $\widetilde{\mathcal{E}}$. In order to encode a CPTP
map, $\Phi_{\widetilde{\mathcal{E}}}$ must satisfy131313For a good reference
on the mathematical properties of Choi representations and CPTP maps, we refer
the interested reader to [Wat18]. the Complete-Positivity (CP) criterion:

$\displaystyle\Phi_{\widetilde{\mathcal{E}}}\succeq 0\quad\text{(positive
semi-definite)}$ (33)

and the Trace-Preserving (TP) criterion:

$\displaystyle\operatorname*{Tr}{}_{\mathrm{out}}(\Phi_{\widetilde{\mathcal{E}}})=I_{\mathrm{in}}.$
(34)

Generically, this involves solving a convex constrained minimization problem.
Namely, if we let $\mathfrak{C}_{n,\ell}$ denote the set of all Choi
representation matrices corresponding to an $m$ to $\ell$-qubit CPTP, then

$\displaystyle\Phi_{\widetilde{\mathcal{E}}}=\underset{\Phi\in\mathfrak{C}_{n,\ell}}{\arg\min}\>\|\widetilde{\Phi}-\Phi\|_{F}^{2}.$
(35)

Since $\mathfrak{C}_{n,\ell}$ is a convex set, as demonstrated in Appendix B,
projecting onto $\mathfrak{C}_{n,\ell}$ by minimizing with respect to the
Frobenius norm reduces the overall error of our learning algorithm. As
depicted in Figure 7, with this projection, $\Phi_{\widetilde{\mathcal{E}}}$
lies closer to the true Choi representation $\Phi_{\mathcal{E}}$ than
$\widetilde{\Phi}$ does. Also note that this minimization over the set
$\mathfrak{C}_{n,\ell}$ can equivalently be expressed as a constrained
minimization problem over the larger space of complex matrices
$\mathbb{C}^{M\times M}$:

$\displaystyle E^{*}=\underset{E\in\mathbb{C}^{M\times
M}}{\arg\min}\|E\|_{F}^{2}\hskip 7.22743pt\text{ such that }\hskip
7.22743pt\begin{cases}\operatorname*{Tr}{}_{\mathrm{out}}(E)=I_{\text{in}}-\operatorname*{Tr}{}_{\mathrm{out}}(\widetilde{\Phi})\\\
\widetilde{\Phi}-E\succeq 0\end{cases},$ (36)

where $\Phi_{\widetilde{\mathcal{E}}}=\widetilde{\Phi}-E^{*}$. Note, however,
that generic convex optimization algorithms generally only guarantee efficient
convergence to $\epsilon$-approximate solutions, whereas we need an exact
solution to ensure that $\Phi_{\widetilde{\mathcal{E}}}$ encodes a physical
quantum channel.

###  4.3 Learning with Measurement Queries

Finally, in our proof of Lemma 35, we proposed an efficient procedure for
approximately learning Pauli coefficients of the Choi representation of
quantum channel. Despite the promising sample complexity of this approach,
there is a notable physical implementation challenge. Namely, physical
implementation would require producing a Choi state, necessitating the
preparation and manipulation of a physical Bell state over $2m$-qubits. This,
however, is very difficult in practice for large $m$, especially with modern
NISQ multi-qubit gate fidelities and state coherence times.

In light of these challenges, we will now offer a second approach for learning
the Choi representation coefficients which is more implementation-friendly.
Rather than performing tomography on the Choi state, the physical
implementation will amount to preparing $n$-qubit input states, applying the
channel $\mathcal{E}$, and performing measurements corresponding to
$\ell$-qubit Pauli observables. Notably, all these operations are far more
practically feasible than the repeated preparation and measurement of
$n$-qubit Choi state $\rho_{\mathcal{E}}$. The relevant query model consists
of _measurement queries_.

##### Measurement queries

For each measurement query, the learner provides an $n$-qubit quantum state
$\rho$ along with an observable $O\in\mathcal{M}_{L}$, and is given the
measurement outcome of $\mathcal{E}(\rho)$ with respect to observable $O$.

######  Lemma 38.

For each $\delta,\epsilon\in(0,1)$, and $m$\- to $\ell$-qubit channel
$\mathcal{E}$, there exists an algorithm that given
$T=O{\left(\frac{n^{k}}{4^{\ell}\eta^{2}}\cdot\log(1/\delta)\right)}$
measurement queries to $\mathcal{E}$ outputs
$\\{\widetilde{\Phi_{\mathcal{E}}}(P)\\}_{P\in\mathcal{F}_{k}}$ such that
$|\widetilde{\Phi_{\mathcal{E}}}(P)-\Phi_{\mathcal{E}}(P)|\leq\eta$ for each
$P\in\mathcal{F}_{k}$.

###### Proof.

We denote $\Phi=\Phi_{\mathcal{E}}$. Recall from 8 that for any input state
$\rho\in\mathcal{M}_{N}$,
$\mathcal{E}(\rho)=\operatorname*{Tr}_{\mathrm{in}}(\Phi(\rho^{\top}\otimes
I^{\otimes n}))$ where we label the first $n$ qubits of $\Phi$ as
“$\mathrm{in}$” and the remaining $\ell$ qubits as “$\mathrm{out}$”. For each
Pauli $P\in\mathcal{P}_{n}$, we let $P_{\mathrm{in}}\in\mathcal{P}_{n}$ and
$P_{\mathrm{out}}\in\mathcal{P}_{\ell}$ be such that $P=P_{\mathrm{in}}\otimes
P_{\mathrm{out}}$. The key insight of this proof is that measurement of a
quantum channel $\mathcal{E}$, with respect to an input $\rho$ and observable
$O$, is related to a linear combination of the Choi representation
coefficients $\widehat{\Phi}(P)$ as follows.

$\displaystyle\operatorname*{Tr}\left(O\mathcal{E}(\rho)\right)$
$\displaystyle=\operatorname*{Tr}{\left(O\operatorname*{Tr}_{\mathrm{in}}{\left(\Phi(\rho_{\mathrm{in}}^{\top}\otimes
I_{\mathrm{out}})\right)}\right)}$
$\displaystyle=\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\operatorname*{Tr}{\left(O\operatorname*{Tr}_{\mathrm{in}}{\left((P_{\mathrm{in}}\otimes
P_{\mathrm{out}})(\rho_{\mathrm{in}}^{\top}\otimes
I_{\mathrm{out}})\right)}\right)}$
$\displaystyle=\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\operatorname*{Tr}(\rho
P_{\mathrm{in}})\operatorname*{Tr}(OP_{\mathrm{out}}).$

Given repeated query access to $\mathcal{E}$, we will see how to learn the
Choi representation coefficient $\widehat{\Phi}(P)$ corresponding to any Pauli
$P\in\mathcal{P}_{n}$. To this end, there are two related procedures: one for
the set of all Paulis $Q\in\\{I^{\otimes n}\otimes\mathcal{P}_{\ell}\\}$ and
another for the remaining Paulis $R\in\mathcal{P}_{n}\backslash\\{I^{\otimes
n}\otimes\mathcal{P}_{\ell}\\}$.

For any $Q\in\\{I^{\otimes n}\otimes\mathcal{P}_{\ell}\\}$,
$\widehat{\Phi}(Q)$ can be estimated via repeated queries of $\mathcal{E}$
with respect to input $\rho^{\prime}=\frac{1}{N}I_{\mathrm{in}}$ and
observable $O^{\prime}=Q_{\mathrm{out}}$.141414For the $\mathsf{QAC}^{0}$
channels of interest in this work, the channel output is a single qubit. In
this case, $|Q|\leq 1$, meaning $Q$ is guaranteed to lie in the desired set of
low-degree Paulis, i.e. $Q\in\mathcal{F}_{k}$. Namely, the measurement
expectation is proportional to $\widehat{\Phi}(Q)$.

$\displaystyle\operatorname*{Tr}\left(O^{\prime}\mathcal{E}(\rho^{\prime})\right)$
$\displaystyle=\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\operatorname*{Tr}\left(\frac{1}{N}I_{\mathrm{in}}P_{\mathrm{in}}\right)\operatorname*{Tr}(Q_{\mathrm{out}}P_{\mathrm{out}})$
$\displaystyle=\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\cdot\mathbbm{1}{\left\\{P_{\mathrm{in}}=I_{\mathrm{in}}\right\\}}\cdot
L\cdot\mathbbm{1}{\left\\{P_{\mathrm{out}}=Q_{\mathrm{out}}\right\\}}$
$\displaystyle=L\widehat{\Phi}(I_{\mathrm{in}}\otimes Q_{\mathrm{out}})$
$\displaystyle=L\widehat{\Phi}(Q).$

Therefore, to learn $\widehat{\Phi}(Q)$ to error $\eta$, we simply need to
learn $\operatorname*{Tr}\left(O^{\prime}\mathcal{E}(\rho^{\prime})\right)$ to
error $\eta_{0}=2^{\ell}\eta$,

On the other hand, for each $R\in\mathcal{P}_{n}\backslash\\{I^{\otimes
n}\otimes\mathcal{P}_{\ell}\\}$, to estimate $\widehat{\Phi}(R)$ we consider
the expectation of $\mathcal{E}(\rho^{*})$ for input
$\rho^{*}=\frac{1}{N}(I_{\mathrm{in}}+R_{\mathrm{in}})$ with respect to
observable $O^{*}=R_{\mathrm{out}}$. We can write it as follows.

$\displaystyle\operatorname*{Tr}\left(O^{*}\mathcal{E}(\rho^{*})\right)$
$\displaystyle=\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\operatorname*{Tr}\left(\left(\frac{I_{\mathrm{in}}+R_{\mathrm{in}}}{N}\right)P_{\mathrm{in}}\right)\operatorname*{Tr}(R_{\mathrm{out}}P_{\mathrm{out}})$
$\displaystyle=\frac{1}{N}\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\left(\operatorname*{Tr}\left(P_{\mathrm{in}}\right)+\operatorname*{Tr}\left(R_{\mathrm{in}}P_{\mathrm{in}}\right)\right)\operatorname*{Tr}(R_{\mathrm{out}}P_{\mathrm{out}})$
$\displaystyle=\frac{1}{N}\sum_{P\in\mathcal{P}_{n}}\widehat{\Phi}(P)\left(N\cdot\mathbbm{1}{\left\\{P_{\mathrm{in}}=I_{\mathrm{in}}\right\\}}+N\cdot\mathbbm{1}{\left\\{P_{\mathrm{in}}=R_{\mathrm{in}}\right\\}}\right)\cdot
L\cdot\mathbbm{1}{\left\\{P_{\mathrm{out}}=R_{\mathrm{out}}\right\\}}$
$\displaystyle=L\left(\widehat{\Phi}(I_{\mathrm{in}}\otimes
R_{\mathrm{out}})+\widehat{\Phi}(R_{\mathrm{in}}\otimes
R_{\mathrm{out}})\right)$
$\displaystyle=L\left(\widehat{\Phi}(I_{\mathrm{in}}\otimes
R_{\mathrm{out}})+\widehat{\Phi}(R)\right).$

Note that $\widehat{\Phi}(I_{\mathrm{in}}\otimes
R_{\mathrm{out}})\in\\{I^{\otimes n}\otimes\mathcal{P}_{\ell}\\}$, so we can
estimate $\widehat{\Phi}(R)$ within error $\eta$ if we have a $2^{\ell-1}\eta$
estimate of $\operatorname*{Tr}{\left(O^{*}\mathcal{E}(\rho)\right)}$ and a
$\eta/2$ estimate of $\widehat{\Phi}(R)$. Therefore, to get an additive $\eta$
estimate for $\widehat{\Phi}(P)$ for each $P\in\mathcal{F}_{k}$, it is
sufficient for us to estimate
$\operatorname*{Tr}(O^{\prime}\mathcal{E}(\rho^{\prime})$ and
$\operatorname*{Tr}(O^{*}\mathcal{E}(\rho^{*}))$ within error $\eta
2^{\ell}/2$ for each $P\in\mathcal{F}_{k}$ where
$O^{\prime},O^{*},\rho^{\prime},\rho^{*}$ depend on $P$ as described above.

Via a Chernoff bound, for each input $\rho$ and observable $P$,
$\operatorname*{Tr}\left(O\mathcal{E}(\rho)\right)$ can be learned to within
additive error $\eta_{0}$, with probability $1-\delta_{0}$ via
$O(1/\eta_{0}^{2}\cdot\log(1/\delta_{0}))$ queries. We repeat this process for
each $P\in\mathcal{F}_{k}$ with $\eta_{0}=2^{\ell-1}\eta$, and
$\delta_{0}=\delta/|\mathcal{F}_{k}|$. By a union bound, we learn
$\eta$-approximations of all $|\mathcal{F}_{k}|=O(n^{k})$ low-degree
coefficients with probability at least $1-\delta$ using

$\displaystyle
O\left(\frac{n^{k}}{4^{\ell}\>\eta^{2}}\log\left(\frac{n^{k}}{\delta}\right)\right)$
(37)

queries to the quantum channel $\mathcal{E}$. ∎

Note that the sample complexity of this procedure is slightly worse than given
the Choi state directly, scaling as $O(n^{k})$ rather than $O(3^{k})$.
Following the analysis in the Proof of Theorem 33, this method provides us
with a learning algorithm with
$O{\left(n^{2k}\frac{1}{\epsilon}\log(1/\delta)\right)}$ measurement queries.

## References

  * [ABN23] Anurag Anshu, Nikolas P Breuckmann, and Chinmay Nirkhe.  NLTS Hamiltonians from good quantum codes.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1090–1096, 2023.
  * [AGL+23] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani.  A polynomial-time classical algorithm for noisy random circuit sampling.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 945–957, New York, NY, USA, 2023. Association for Computing Machinery.
  * [BC17] Jacob C Bridgeman and Christopher T Chubb.  Hand-waving and interpretive dance: an introductory course on tensor networks.  Journal of physics A: Mathematical and theoretical, 50(22):223001, 2017.
  * [BCK+14] Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman.  Computing with a full memory: Catalytic space.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 857–866, New York, NY, USA, 2014. Association for Computing Machinery.
  * [BGH07] Debajyoti Bera, Frederic Green, and Steven Homer.  Small depth quantum circuits.  ACM SIGACT News, 38(2):35–50, 2007.
  * [BGL23] Sergey Bravyi, David Gosset, and Yinchen Liu.  Classical simulation of peaked shallow quantum circuits.  arXiv preprint arXiv:2309.08405, 2023.
  * [Bla09] Eric Blais.  Testing juntas nearly optimally.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 151–158, New York, NY, USA, 2009. Association for Computing Machinery.
  * [BLS+22] Dolev Bluvstein, Harry Levine, Giulia Semeghini, Tout T Wang, Sepehr Ebadi, Marcin Kalinowski, Alexander Keesling, Nishad Maskara, Hannes Pichler, Markus Greiner, et al.  A quantum processor based on coherent transport of entangled atom arrays.  Nature, 604(7906):451–456, 2022.
  * [Bop97] Ravi B Boppana.  The average sensitivity of bounded-depth circuits.  Information processing letters, 63(5):257–261, 1997.
  * [Bra09] M. Braverman.  Poly-logarithmic independence fools $AC^{0}$ circuits.  In Proc. 24th Annual IEEE Conference on Computational Complexity (CCC), pages 3–8, 2009.
  * [BY23] Zongbo Bao and Penghui Yao.  Nearly optimal algorithms for testing and learning quantum junta channels.  arXiv preprint arXiv:2305.12097, 2023.
  * [CHHL19] Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett.  Pseudorandom generators from polarizing random walks.  Theory of Computing, 15(1):1–26, 2019.
  * [CHLT18] Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal.  Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.  In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen.  Testing and learning quantum juntas nearly optimally.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185. SIAM, 2023.
  * [EH17] Lior Eldar and Aram W Harrow.  Local Hamiltonians whose ground states are hard to approximate.  In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pages 427–438. IEEE, 2017.
  * [EIS22] Alexandros Eskenazis, Paata Ivanisvili, and Lauritz Streck.  Low-degree learning and the metric entropy of polynomials.  arXiv preprint arXiv:2203.09659, 2022.
  * [FFG+03] Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang.  Quantum lower bounds for fanout.  arXiv preprint quant-ph/0312208, 2003.
  * [FLN+02] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky.  Monotonicity testing over general poset domains.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 474–483, 2002.
  * [FSS84] M. Furst, J. Saxe, and M. Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Mathematical Systems Theory, 17(1):13–27, 1984.
  * [GDC+22] Andrew Y Guo, Abhinav Deshpande, Su-Kuan Chu, Zachary Eldredge, Przemyslaw Bienias, Dhruv Devulapalli, Yuan Su, Andrew M Childs, and Alexey V Gorshkov.  Implementing a fast unbounded quantum fanout gate using power-law interactions.  Physical Review Research, 4(4):L042016, 2022.
  * [GKH+21] Pranav Gokhale, Samantha Koretsky, Shilin Huang, Swarnadeep Majumder, Andrew Drucker, Kenneth R Brown, and Frederic T Chong.  Quantum fan-out: Circuit optimizations and technology modeling.  In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 276–290. IEEE, 2021.
  * [GS14] Christophe Garban and Jeffrey E Steif.  Noise sensitivity of Boolean functions and percolation, volume 5.  Cambridge University Press, 2014.
  * [Hås86] J. Håstad.  Computational Limitations for Small Depth Circuits.  MIT Press, Cambridge, MA, 1986.
  * [Hås01] Johan Håstad.  A slight sharpening of LMN.  Journal of Computer and System Sciences, 63(3):498–508, 2001.
  * [Hås14] Johan Håstad.  On the correlation of parity and small-depth circuits.  SIAM Journal on Computing, 43(5):1699–1708, 2014.
  * [HCP22] Hsin-Yuan Huang, Sitan Chen, and John Preskill.  Learning to predict arbitrary quantum processes.  arXiv preprint arXiv:2210.14894, 2022.
  * [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, October 2020.
  * [HŠ05] Peter Høyer and Robert Špalek.  Quantum fan-out is powerful.  Theory of computing, 1(1):81–103, 2005.
  * [IMP12] Russell Impagliazzo, William Matthews, and Ramamohan Paturi.  A satisfiability algorithm for $AC0$.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 961–972. SIAM, 2012.
  * [Kha93] Michael Kharitonov.  Cryptographic hardness of distribution-specific learning.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 372–381, 1993.
  * [KKMS05] A. Kalai, A. Klivans, Y. Mansour, and R. Servedio.  Agnostically learning halfspaces.  In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), pages 11–20, 2005.
  * [KM93] E. Kushilevitz and Y. Mansour.  Learning decision trees using the Fourier spectrum.  SIAM J. on Computing, 22(6):1331–1348, 1993.
  * [KMS18] Subhash Khot, Dor Minzer, and Muli Safra.  On monotonicity testing and boolean isoperimetric-type theorems.  SIAM J. Comput., 47(6):2238–2276, 2018.
  * [Lan14] Zeph Landau.  Tensor networks and quantum algorithms, 2014.  Tutorial at the Simons Institute for the Theory of Computing. Available here.
  * [Leu00] Debbie Wun Chi Leung.  Towards robust quantum computation.  PhD thesis, Stanford University, California, January 2000.
  * [LMN93] N. Linial, Y. Mansour, and N. Nisan.  Constant depth circuits, Fourier transform and learnability.  Journal of the ACM, 40(3):607–620, 1993.
  * [MFF14] Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons.  Hardness of classically simulating the one-clean-qubit model.  Physical review letters, 112(13):130502, 2014.
  * [MO08] Ashley Montanaro and Tobias J Osborne.  Quantum boolean functions.  arXiv preprint arXiv:0810.2435, 2008.
  * [Moo99] Cristopher Moore.  Quantum circuits: Fanout, parity, and counting.  arXiv preprint quant-ph/9903046, 1999.
  * [MRL08] M. Mohseni, A. T. Rezakhani, and D. A. Lidar.  Quantum-process tomography: Resource analysis of different strategies.  Phys. Rev. A, 77:032322, Mar 2008.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [NW94] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of computer and System Sciences, 49(2):149–167, 1994.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [PFGT20] Daniel Padé, Stephen Fenner, Daniel Grier, and Thomas Thierauf.  Depth-2 QAC circuits cannot simulate quantum parity.  arXiv preprint arXiv:2005.12169, 2020.
  * [Raz87] Alexander A Razborov.  Lower bounds on the size of bounded depth circuits over a complete basis with logical addition.  Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987.
  * [Ros21] Gregory Rosenthal.  Bounds on the $QAC0$ Complexity of Approximating Parity.  In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [RRG+22] Kenneth Rudinger, Guilhem J Ribeill, Luke CG Govia, Matthew Ware, Erik Nielsen, Kevin Young, Thomas A Ohki, Robin Blume-Kohout, and Timothy Proctor.  Characterizing midcircuit measurements on a superconducting qubit using gate set tomography.  Physical Review Applied, 17(1):014014, 2022.
  * [RT22] Ran Raz and Avishay Tal.  Oracle separation of BQP and PH.  ACM Journal of the ACM (JACM), 69(4):1–21, 2022.
  * [RWZ22] Cambyse Rouzé, Melchior Wirth, and Haonan Zhang.  Quantum Talagrand, KKL and Friedgut’s theorems and the learnability of quantum Boolean functions.  arXiv preprint arXiv:2209.07279, 2022.
  * [Smo87] P. Smolensky.  Information processing in dynamical systems: Foundations of harmony theory.  In D. E. Rumelhart, J. L. McClelland, et al., editors, Parallel Distributed Processing: Volume 1: Foundations, pages 194–281. MIT Press, Cambridge, 1987.
  * [SVZ23] Joseph Slote, Alexander Volberg, and Haonan Zhang.  Noncommutative Bohnenblust-Hille inequality in the Heisenberg-Weyl and Gell-Mann bases with applications to fast learning.  arXiv preprint arXiv:2301.01438, 2023.
  * [Tal17] Avishay Tal.  Tight bounds on the Fourier spectrum of $AC0$.  In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [VDH02] Wim Van Dam and Patrick Hayden.  Renyi-entropic bounds on quantum communication.  arXiv preprint quant-ph/0204093, 2002.
  * [VTV21] Ruben Verresen, Nathanan Tantivasadakarn, and Ashvin Vishwanath.  Efficiently preparing Schrödinger’s cat, fractons and non-Abelian topological order in quantum devices.  arXiv preprint arXiv:2112.03061, 2021.
  * [VZ23] Alexander Volberg and Haonan Zhang.  Noncommutative Bohnenblust–Hille inequalities.  Mathematische Annalen, pages 1–20, 2023.
  * [Wan11] Guoming Wang.  Property testing of unitary operators.  Physical Review A, 84(5):052328, 2011.
  * [Wat18] John Watrous.  The theory of quantum information.  Cambridge university press, 2018.
  * [Wil17] Mark M. Wilde.  Quantum Information Theory.  Cambridge University Press, 2017.
  * [Yao85] A. Yao.  Separating the polynomial time hierarchy by oracles.  In Proceedings of the Twenty-Sixth Annual Symposium on Foundations of Computer Science, pages 1–10, 1985.

##  Appendix A Generalizing to linear combinations of channels

In this appendix, we show that our result on low-degree Pauli concentration
(Theorem 16) can be generalized from $\mathsf{QAC}^{0}$ channels to linear
combinations of such channels.

######  Lemma 39.

Suppose $\mathcal{E}$ is a linear combination of channels
$\mathcal{E}_{1},\mathcal{E}_{2},\dots,\mathcal{E}_{t}$ .

$\displaystyle\mathcal{E}(\rho)=\sum_{i=1}^{t}\alpha_{i}\mathcal{E}_{i}(\rho)$

such that $\mathbf{W}^{>k}(\Phi_{\mathcal{E}_{i}})\leq\epsilon$ for each
$i\in[t]$. Then for each $k$,

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]\leq{\left(\sum_{i=1}^{t}\alpha_{i}\right)}^{2}\epsilon.$

###### Proof.

Let $n$ and $\ell$ be the number of input and output qubits to $\mathcal{E}$
respectively, and let $N=2^{n},L=2^{\ell}$ and $m=n+\ell$, $M=2^{m}$. For each
$i\in[t]$, let $\Phi_{i}=\Phi_{\mathcal{E}_{i}}$. Note that

$\displaystyle\Phi_{\mathcal{E}}={\left(I^{\otimes
n}\otimes\mathcal{E}\right)}{\left(\ket{\mathrm{EPR}_{n}}\\!\\!\bra{\mathrm{EPR}_{n}}\right)}=\sum_{i=1}^{t}(I^{\otimes
n}\otimes\mathcal{E}_{i}){\left(\ket{\mathrm{EPR}_{n}}\\!\\!\bra{\mathrm{EPR}_{n}}\right)}=\sum_{i=1}^{t}\alpha_{i}\Phi_{i}.$

Consider a particular $k$, and let
$H_{i}=\sum_{\begin{subarray}{c}P\in\mathcal{P}_{m}\mathrel{\mathop{\mathchar
58\relax}}\\\ |P|>k\end{subarray}}\widehat{\Phi_{i}}(P)P$. Furthermore, let
$\widehat{H_{i}}$ be the vector of Pauli coefficients of $H_{i}$. So
$\mathbf{W}^{>k}(\Phi_{i})=\mathinner{\\!\left\lVert\widehat{H_{i}}\right\rVert}_{2}^{2}$
for each $i\in[t]$. Now

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]$
$\displaystyle=\mathinner{\\!\left\lVert\sum_{i=1}^{t}\alpha_{i}\widehat{H_{i}}\right\rVert}_{2}^{2}.$

Applying the triangle inequality,

$\displaystyle\mathbf{W}^{>k}[\Phi_{\mathcal{E}}]$
$\displaystyle\leq{\left(\sum_{i=1}^{t}\alpha_{i}\mathinner{\\!\left\lVert\widehat{H_{i}}\right\rVert}_{2}\right)}^{2}$
$\displaystyle={\left(\sum_{i=1}^{t}\alpha_{i}\sqrt{\mathbf{W}^{>k}[\Phi_{i}}]\right)}^{2}$
$\displaystyle\leq{\left(\sum_{i=1}^{t}\alpha_{i}\right)}^{2}\epsilon$

∎

##  Appendix B Convex CPTP Projection

Leveraging the fact that $\widetilde{\Phi}$ is $\epsilon$-close to
$\Phi_{\mathcal{E}}$, we will now prove that the Choi representation
$\Phi_{\widetilde{\mathcal{E}}}$, resulting from the convex Frobenius norm
minimizaton described in Section 4.2, is also $\epsilon$-close to
$\Phi_{\mathcal{E}}$. Note that, in the case that
$\widetilde{\Phi}\in\mathfrak{C}_{n,\ell}$, the projection simply maps
$\widetilde{\Phi}$ to itself, which implies that
$\Phi_{\widetilde{\mathcal{E}}}=\widetilde{\Phi}$ is $\epsilon$-close to
$\Phi_{\mathcal{E}}$. Therefore, we only need to consider the case in which
$\widetilde{\Phi}_{\mathcal{E}}\notin\mathfrak{C}_{n,\ell}$.

We begin by decomposing the error between $\widetilde{\Phi}$ and
$\Phi_{\mathcal{E}}$ in terms of $\Phi_{\widetilde{\mathcal{E}}}$, as

$\displaystyle\left\|\widetilde{\Phi}-\Phi_{\mathcal{E}}\right\|_{F}^{2}$
$\displaystyle=\left\|(\widetilde{\Phi}-\Phi_{\widetilde{\mathcal{E}}})+(\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}})\right\|_{F}^{2}$
$\displaystyle=\left\|\widetilde{\Phi}-\Phi_{\widetilde{\mathcal{E}}}\right\|_{F}^{2}+2\left\langle\widetilde{\Phi}-\Phi_{\widetilde{\mathcal{E}}},\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}}\right\rangle+\left\|\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}}\right\|_{F}^{2}.$

Since the Frobenius norm squared is non-negative, if we can simply prove that

$\displaystyle\left\langle\widetilde{\Phi}-\Phi_{\widetilde{\mathcal{E}}},\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}}\right\rangle\geq
0,$

then it follows that

$\displaystyle\left\|\Phi_{\widetilde{\mathcal{E}}}-\Phi_{\mathcal{E}}\right\|_{F}^{2}\leq\left\|\widetilde{\Phi}-\Phi_{\mathcal{E}}\right\|_{F}^{2}<\epsilon.$

Therefore, to prove that $\Phi_{\widetilde{\mathcal{E}}}$ is $\epsilon$-close
to $\Phi_{\mathcal{E}}$, we will prove Appendix B.

To do so, note that $\mathfrak{C}_{n,\ell}$ is a closed convex set in the
Hilbert space $\mathbb{C}^{M\times M}$, equipped with Frobenius norm inner
product $\langle A,B\rangle=\operatorname*{Tr}[A^{\dagger}B]$. Furthermore, in
Equation 35, we defined $\Phi_{\widetilde{\mathcal{E}}}$ to be the minimizer
of the Frobenius norm distance with respect to $\widetilde{\Phi}$. Therefore
$\Phi_{\widetilde{\mathcal{E}}}$ must satisfy the First-Order Optimality
Condition:

######  Fact 40 (First-Order Optimality Condition).

For an optimization problem

$\displaystyle\underset{X\in\mathcal{X}}{\arg\min}f(X)$

over closed convex set $\mathcal{X}$ and with convex differentiable $f$,
feasible point $X$ is optimal if and only if

$\displaystyle\langle\nabla f(X),Y-X\rangle\geq 0,\>\>\forall
Y\in\mathcal{X}.$

From Equation 35, $\Phi_{\widetilde{\mathcal{E}}}$ is the minimizer of the
function $f(\Phi)=\|\Phi-\Phi_{\mathcal{E}}\|_{F}^{2}$, for which $\nabla
f(\Phi)=2(\Phi-\widetilde{\Phi})$. The First-Order Optimality Condition,
therefore, implies that

$\displaystyle\forall\>\Phi_{\mathcal{E}}\in\mathfrak{C}_{n,\ell}\>\mathrel{\mathop{\mathchar
58\relax}}\>\langle\nabla
f(\Phi_{\widetilde{\mathcal{E}}}),\Phi_{\mathcal{E}}-\Phi_{\widetilde{\mathcal{E}}}\rangle=2\langle\Phi_{\widetilde{\mathcal{E}}}-\widetilde{\Phi}_{\mathcal{E}},\Phi_{\mathcal{E}}-\Phi_{\widetilde{\mathcal{E}}}\rangle\geq
0,$ (38)

thereby proving Appendix B.