Explicit sufficient reduced-process sample counts

Assume that for every $m\in\mathbb N$ the quotient of the $m$-qubit Pauli normalizer by equality of conjugation maps has a supplied finite enumeration, where the Pauli subgroup is generated by tensor products of Pauli matrices with phases $1,i,-1,-i$. For every $n,k\in\mathbb N$ satisfying $n>0$ and $k\le n$, and every real $\varepsilon,\delta$ satisfying $0<\varepsilon<1$ and $0<\delta<1$, four simultaneous recovery assertions hold with the explicit sample counts below. For their meaning, a channel is any map $\mathcal E(X)=\sum_jK_jXK_j^\dagger$ with finitely many Kraus matrices and $\sum_jK_j^\dagger K_j=I$, its normalized Choi matrix is

$$(C_{\mathcal E})_{(a,b),(a',b')}= 2^{-n}\bigl[\mathcal E(|a\rangle\langle a'|)\bigr]_{b,b'},$$

and for each injection $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$ its reduced matrix is

$$(C_{\mathcal E,w})_{(u,v),(u',v')}= \sum_{\substack{a,b\in\{0,1\}^n\\a\circ w=b\circ w=0}} (C_{\mathcal E})_{(a[w\leftarrow u],\,b[w\leftarrow v]), (a[w\leftarrow u'],\,b[w\leftarrow v'])},$$

where the bracket notation means overwriting the indicated coordinates. Each recovery assertion means that there exists an estimator from the specified number of records and an injection $w$ to a complex matrix on $2k$ qubits, such that for every channel the event $\forall w,\ \|\widehat C(r,w)-C_{\mathcal E,w}\|\le\varepsilon$ has measure or finite record weight at least $1-\delta$; the estimator need not satisfy any stated measurability, positivity, or normalization condition. Set

$$\ell=\log\frac{2(8n)^{2k}}{\delta},\qquad \ell_1=\log\frac{(24n)^{2k}}{\delta},\qquad s_k(B)= \begin{cases}0,&k=0,\\ \max\{0,\lceil B\rceil\},&k\ne0.\end{cases}$$

The first assertion holds for every measurement primitive $P$ on $2n$ qubits, in Frobenius norm, with

$$N_P=s_k\!\left(\frac{68\,4^k}{\varepsilon^2}\,\ell\,R_P(k)\right).$$

Such a primitive consists of a probability measure $\mu_P$ on unitaries with injective linear measurement channel

$$\mathcal M_P(X)= \int\sum_b\operatorname{Tr}(U^\dagger|b\rangle\langle b|U\,X) \,U^\dagger|b\rangle\langle b|U\,d\mu_P(U).$$

The record measure is the product of the single-record measures with density $\max\{\operatorname{Re}(UC_{\mathcal E}U^\dagger)_{bb},0\}$ against $\mu_P$, summed over $b$. To define $R_P(k)$, for every $w$ as above and every $2k$-qubit Pauli tensor $A$, extend $A$ to an observable $A_w$ on the input and output $n$-qubit registers by using $w$ in both registers and the identity on the remaining wires: its matrix entry is $A$ at the restricted pair of strings when both registers agree outside the image of $w$, and zero otherwise. Then $R_P(k)$ is the maximum of $V_P(A_w)$ over all such $w,A$, where, for Hermitian $O$, with $O^\circ=O-2^{-2n}\operatorname{Tr}(O)I$,

$$V_P(O)= \left[ \sqrt{\sup_{\substack{\tau\succeq0\\\operatorname{Tr}\tau=1}} \int\sum_b \operatorname{Re}(U\tau U^\dagger)_{bb} \left(\operatorname{Re}[U\mathcal M_P^{-1}(O^\circ)U^\dagger]_{bb}\right)^2 \,d\mu_P(U)} \right]^2,$$

and $V_P(O)=0$ for non-Hermitian $O$; a maximum over an empty finite index type is defined as zero. The remaining three assertions use finite frames: a frame with matrices $Q_{a,b}$ assigns a record $r$ the weight

$$\prod_{j<N}\frac{\operatorname{Re}\operatorname{Tr}(Q_{r_j}C_{\mathcal E})} {|\operatorname{Basis}|},$$

and assigns an event the sum of these weights. The global frame uses quotient classes of normalizer unitaries as basis choices and $Q_{a,b}=U_a^\dagger|b\rangle\langle b|U_a$ for chosen representatives; it recovers in Frobenius norm with

$$N_{\mathrm{global,F}}= s_k\!\left(\frac{204\,4^{n+k}}{\varepsilon^2}\ell\right).$$

The Pauli frame uses choices $a=(A_j,s_j)_{j<2n}$, where $A_j\in\{X,Y,Z\}$, $s_j\in\{-1,1\}$, and $Q_{a,b}=\bigotimes_j(I+s_j(-1)^{b_j}A_j)/2$; it recovers in Frobenius norm with

$$N_{\mathrm{Pauli,F}}= s_k\!\left(\frac{68\,36^k}{\varepsilon^2}\ell\,H(k)\right), \qquad H(k)=\max_{A\text{ a }2k\text{-qubit Pauli tensor}}\|A\|_{\mathrm{op}}^2,$$

and in trace norm with

$$N_{\mathrm{Pauli,1}}= s_k\!\left(\frac{(8/3)\,144^k}{\varepsilon^2}\ell_1\right).$$

Here the trace norm is $\operatorname{Re}\operatorname{Tr}\sqrt{X^\dagger X}$. The four assertions can have different estimators. The case $k=0$ is included, and all four sample counts are then exactly zero.