Definitions for Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers

QAlgorithms.Papers.Independent.Intakethird100.P66.BasisChoiceFrame

For each natural number $n$, including zero, this defines a structure consisting of a type $B$, a specified finite enumeration of $B$, evidence that $B$ is nonempty, and a function assigning to every $a\in B$ and every $n$-bit string $b$ an arbitrary complex matrix $P_{a,b}$ indexed by $n$-bit strings. No equations or positivity, Hermiticity, idempotence, orthogonality, or normalization conditions are required of these matrices. For $n=0$, there is one bit string and each assigned matrix has one entry.

QAlgorithms.Papers.Independent.Intakethird100.P66.CliffordBlocks

This defines a proposition about frames on any natural number of bits, where a frame consists of a finite, nonempty choice set and assigned complex matrices for every choice and outcome string. It is generated by exactly three rules: the zero-bit frame with singleton choice set and matrix $[1]$ satisfies the proposition; for every natural number $m$ and specified finite enumeration of its projective group, the global frame satisfies it; and for all natural numbers $a,b$ and frames $F,G$ satisfying it on those respective lengths, their tensor frame satisfies it on $a+b$ bits. In the global rule, the projective group is the normalizer of the unitary subgroup generated by $i^c\bigotimes_jP_j$, with $c\in\{0,1,2,3\}$ and $P_j\in\{I,X,Y,Z\}$, quotiented by equality of conjugation on every complex matrix; its assigned matrices have entries $\overline{(U_a)_{b,x}}(U_a)_{b,y}$ for the designated representative $U_a$. In the tensor rule, choices are paired, outcomes and indices are split into consecutive blocks, and corresponding matrix entries are multiplied. Only frames obtainable by finitely many applications of these rules satisfy the proposition; zero-length global and tensor blocks are included.

QAlgorithms.Papers.Independent.Intakethird100.P66.ErrorNorm

This declaration defines a type with exactly two distinct values, named frobenius and trace, and no additional data attached to either value.

QAlgorithms.Papers.Independent.Intakethird100.P66.OverlapsRecover

For natural numbers $n,M$, let $\mathcal B_j=\{0,1\}^j$, and let $F$ consist of a finite nonempty type $A$ and arbitrary complex matrices $F_{a,b}$ indexed by $\mathcal B_{2n}$ for $a\in A$ and $b\in\mathcal B_{2n}$; no projector, positivity, or normalization conditions are imposed on these matrices. Given matrices $O_0,\ldots,O_{M-1}$ indexed by $\mathcal B_{2n}$, a natural number $N$, and real numbers $\varepsilon,\delta$, this predicate says that there exists a function $\widehat o:(A\times\mathcal B_{2n})^N\to\mathbb R^M$ such that, for every map $E$ on matrices indexed by $\mathcal B_n$ having a finite representation $E(X)=\sum_{a=0}^{s-1}K_aXK_a^\dagger$ with $\sum_{a=0}^{s-1}K_a^\dagger K_a=I$, the matrix

$$(C_E)_{(u,v),(u',v')}=2^{-n}E(|u\rangle\langle u'|)_{v,v'}$$

satisfies

$$1-\delta\le \sum_{r\in(A\times\mathcal B_{2n})^N} \mathbf1_{\{\forall i<M,\ |\widehat o(r)_i-\operatorname{Re}\operatorname{Tr}(O_iC_E)|\le\varepsilon\}} \prod_{j=0}^{N-1} \left(\frac{1}{|A|}\operatorname{Re}\operatorname{Tr}(F_{r_j}C_E)\right),$$

where pairs of $n$-bit strings index $C_E$ by concatenation, $F_{r_j}=F_{a,b}$ when $r_j=(a,b)$, and the indicator equals one precisely when its condition holds. The same estimate must work for every such $E$; neither the $O_i$ nor the estimate has additional constraints. The displayed record weights are the specified real expressions and are not assumed nonnegative or normalized. Zero values of $n,M,N$ are included: $M=0$ makes the accuracy condition vacuous, and $N=0$ leaves one empty record with product weight one. There are no range assumptions on $\varepsilon$ or $\delta$.

QAlgorithms.Papers.Independent.Intakethird100.P66.PaperFrame

This defines a proposition about frames on any natural number $m$ of bits, generated by two rules. First, for every $m$, it holds for the frame whose choices are functions $a_j=(A_j,t_j)\in\{X,Y,Z\}\times\{\mathrm{false},\mathrm{true}\}$ and whose matrix for outcome $b$ has entries $\prod_j[(I+s_j\sigma_{A_j})/2]_{x_j,y_j}$, with $s_j=1$ when $t_j\ne b_j$ and $s_j=-1$ otherwise, using the usual Pauli matrices. Second, it holds for any frame obtained by finitely combining the singleton zero-bit frame with matrix $[1]$ and global frames by appended tensor products. Each global block of length $r$ requires a specified finite enumeration of the quotient of the normalizer of the unitary subgroup generated by $i^c\bigotimes_jP_j$, for $c\in\{0,1,2,3\}$ and $P_j\in\{I,X,Y,Z\}$, where two normalizer elements are identified when their conjugation functions agree on every complex matrix; its matrices have entries $\overline{(U_a)_{b,x}}(U_a)_{b,y}$ for designated representatives. Tensor products pair choice sets and multiply matrix entries after splitting outcomes and indices into consecutive blocks. These are the only generating rules, and they include $m=0$.

QAlgorithms.Papers.Independent.Intakethird100.P66.PrimitiveOverlapsRecover

For any natural numbers $n,M,N$, real numbers $\varepsilon,\delta$, measurement primitive $P$ on $2n$ qubits, and family $O_0,\ldots,O_{M-1}$ of arbitrary complex matrices indexed by $Q_{2n}=\{0,1\}^{2n}$, this proposition asserts the existence of a measurable estimator, independent of the channel, that returns $M$ real numbers from $N$ recorded pairs of a unitary matrix and a bit string. Here $Q_j=\{0,1\}^j$, including the singleton $Q_0$, and $P$ consists of a Borel probability measure $\mu$ on unitary matrices indexed by $Q_{2n}$, together with injectivity of the complex linear map

$$\mathcal M_\mu(X)_{ij} =\sum_{a,b\in Q_{2n}} \left(\int \sum_{t\in Q_{2n}} \overline{U_{ti}}U_{tj}U_{ta}\overline{U_{tb}}\,d\mu(U)\right)X_{ab}.$$

Specifically, there must exist a measurable function $\widehat o$ assigning a real number $\widehat o(r,i)$ to every record $r=((U_j,b_j))_{j=0}^{N-1}$ and every $i\in\{0,\ldots,M-1\}$, such that the following holds for every channel $E$. A channel here means a function on complex matrices indexed by $Q_n$ for which there exist a natural number $s$ and matrices $K_0,\ldots,K_{s-1}$ satisfying $\sum_hK_h^\dagger K_h=I$ and $E(X)=\sum_hK_hXK_h^\dagger$ for every $X$. Identify concatenated $n$-bit strings with pairs and define

$$(\rho_E)_{(a,b),(a',b')} =2^{-n}\bigl(E(|a\rangle\langle a'|)\bigr)_{b,b'}, \qquad a,b,a',b'\in Q_n,$$

where $|a\rangle\langle a'|$ is the matrix with its sole nonzero entry, equal to $1$, at $(a,a')$. Define the one-shot measure on pairs $(U,b)$ by

$$\nu_E(A)= \sum_{b\in Q_{2n}}\int \mathbf 1_A(U,b)\, \max\!\left\{\operatorname{Re}(U\rho_EU^\dagger)_{bb},0\right\}\,d\mu(U),$$

and use its $N$-fold product as the record measure. Then

$$\max\{1-\delta,0\} \le \nu_E^{\otimes N} \left\{r:\ \text{for every }0\le i<M,\ \left|\widehat o(r,i)-\operatorname{Re}\operatorname{tr}(O_i\rho_E)\right| \le\varepsilon\right\},$$

with the left side viewed as an extended nonnegative real number. The matrices $O_i$ need not be Hermitian, positive, or norm bounded; only the real parts of the displayed traces are estimated. All natural-number values, including $n=0$, $M=0$, and $N=0$, and all real values of $\varepsilon,\delta$, are included. When $M=0$, the simultaneous accuracy condition is vacuous. When $N=0$, there is a unique empty record with product-measure mass $1$, so the estimator has no recorded observations on which to depend.

QAlgorithms.Papers.Independent.Intakethird100.P66.PrimitiveReducedRecovers

For any natural numbers $n,k,N$, real numbers $\varepsilon,\delta$, and measurement primitive $P$ on $2n$ qubits, this proposition asserts the existence of a measurable estimator, independent of the channel, with the following property. Write $Q_j=\{0,1\}^j$, including the singleton $Q_0$. The primitive $P$ consists of a Borel probability measure $\mu$ on the unitary matrices indexed by $Q_{2n}$, together with injectivity of the complex linear map

$$\mathcal M_\mu(X)_{ij} =\sum_{a,b\in Q_{2n}} \left(\int \sum_{t\in Q_{2n}} \overline{U_{ti}}U_{tj}U_{ta}\overline{U_{tb}}\,d\mu(U)\right)X_{ab}.$$

The estimator takes a record $r=((U_j,b_j))_{j=0}^{N-1}$ and any injection $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$, and returns a complex matrix $\widehat\rho(r,w)$ indexed by $Q_{2k}$. For every function $E$ from complex matrices indexed by $Q_n$ to such matrices that is a channel—meaning that there exist a natural number $s$ and matrices $K_0,\ldots,K_{s-1}$ satisfying $\sum_h K_h^\dagger K_h=I$ and $E(X)=\sum_h K_hXK_h^\dagger$ for every $X$—define the matrix $\rho_E$, using concatenated bit strings as pairs, by

$$(\rho_E)_{(a,b),(a',b')} =2^{-n}\bigl(E(|a\rangle\langle a'|)\bigr)_{b,b'}, \qquad a,b,a',b'\in Q_n,$$

where $|a\rangle\langle a'|$ has entry $1$ at $(a,a')$ and $0$ elsewhere. Define a one-shot measure $\nu_E$ on pairs $(U,b)$ by

$$\nu_E(A)= \sum_{b\in Q_{2n}}\int \mathbf 1_A(U,b)\, \max\!\left\{\operatorname{Re}(U\rho_EU^\dagger)_{bb},0\right\}\,d\mu(U),$$

and let the record measure be the $N$-fold product $\nu_E^{\otimes N}$. For each injection $w$, define $\rho_{E,w}$ by the following entries: for $a,b,a',b'\in Q_k$,

$$(\rho_{E,w})_{(a,b),(a',b')} = \sum_{\substack{u,v\in Q_n\\ u(w(i))=v(w(i))=0\ \text{for every }i}} (\rho_E)_{(u[w\leftarrow a],\,v[w\leftarrow b]), (u[w\leftarrow a'],\,v[w\leftarrow b'])},$$

where $u[w\leftarrow a]$ replaces $u(w(i))$ by $a(i)$ and leaves all other coordinates unchanged. The required bound is

$$\max\{1-\delta,0\} \le \nu_E^{\otimes N} \left\{r:\ \text{for every injection }w,\ \left(\sum_{x,y\in Q_{2k}} \left|\bigl(\widehat\rho(r,w)-\rho_{E,w}\bigr)_{xy}\right|^2\right)^{1/2} \le\varepsilon\right\}.$$

The left side is regarded as an extended nonnegative real number. No sign or range restrictions on $\varepsilon,\delta$, or positivity restrictions on $n,k,N$, are imposed. If $k>n$, there are no such injections and the condition inside the event is vacuous; if $k=0$, the unique empty injection is still included. If $N=0$, the record is the unique empty record and its product measure has mass $1$.

QAlgorithms.Papers.Independent.Intakethird100.P66.ReducedRecovers

For every natural number $n$, let $Q_n=\{0,1\}^n$ and let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary complex matrices $P_{a,b}$ on $Q_{2n}$. For every pair of natural numbers $k,N$, either choice $\nu$ of Frobenius or trace norm, and arbitrary real numbers $\varepsilon,\delta$, this predicate asserts that there exists one estimator $\widehat J$ assigning a complex matrix on $Q_{2k}$ to each record $r:\{0,\ldots,N-1\}\to\mathcal B\times Q_{2n}$ and each injection $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$, such that the following inequality holds for every function $E$ on complex matrices on $Q_n$ admitting a finite Kraus representation $E(X)=\sum_{h=0}^{q-1}K_hXK_h^\dagger$ with $q\in\mathbb N$ and $\sum_hK_h^\dagger K_h=I$:

$$1-\delta\ \le\ \sum_{\substack{r:\{0,\ldots,N-1\}\to\mathcal B\times Q_{2n}\\ \forall w,\ \|\widehat J(r,w)-R_w(J_E)\|_\nu\le\varepsilon}} \ \prod_{j=0}^{N-1} \frac{\operatorname{Re}\operatorname{tr}(P_{a_j,b_j}J_E)}{|\mathcal B|}, \qquad r(j)=(a_j,b_j).$$

Here, under the identification of a concatenated bit string with its two halves, $(J_E)_{(u,v),(u',v')}=2^{-n}(E(e_{u,u'}))_{v,v'}$, with $e_{u,u'}$ the matrix unit, and

$$\bigl(R_w(J)\bigr)_{(u,v),(u',v')} = \sum_{\substack{a,b\in Q_n\\a\circ w=0,\ b\circ w=0}} J_{(a[w\leftarrow u],\,b[w\leftarrow v]),\, (a[w\leftarrow u'],\,b[w\leftarrow v'])},$$

where $a[w\leftarrow u]$ replaces the bits of $a$ at positions $w(i)$ by $u(i)$ and leaves all other bits unchanged. The chosen error is $\|X\|_{\mathrm F}=(\sum_{i,j}|X_{i,j}|^2)^{1/2}$ or $\|X\|_{\mathrm{tr}}=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}$. The estimator is chosen before $E$, and the error requirement is simultaneous over all injections $w$. No conditions on the frame matrices ensure that the displayed record weights are probabilities, and no sign or range restrictions are imposed on $\varepsilon,\delta$. All of $n,k,N$ may be zero; for $N=0$ the unique empty record has weight $1$, and for $k>n$ there are no injections $w$, so the record condition is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P66.ancillaReconstruction

For every natural number $n$, including $0$, let $Q_n=\{0,1\}^n$, let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary matrices $P_{a,b}$ on $Q_n$, and let $E$ be any function from complex matrices on $Q_n$ to themselves. Identify $Q_{2n}$ with $Q_n\times Q_n$, define $(J_E)_{(u,v),(u',v')}=2^{-n}(E(e_{u,u'}))_{v,v'}$, where $e_{u,u'}$ is the corresponding matrix unit, and write $A\otimes B$ for the matrix whose entry at $((u,v),(u',v'))$ is $A_{u,u'}B_{v,v'}$. Set $\mathcal C_F(X)=|\mathcal B|^{-1}\sum_{a,b}\operatorname{tr}(P_{a,b}X)P_{a,b}$ and let $\mathcal I_F=\mathcal C_F^{-1}$ when this map is injective, or the zero map otherwise. The defined reconstruction is

$$\frac1{|\mathcal B|^2} \sum_{a,c\in\mathcal B}\sum_{b,d\in Q_n} \operatorname{Re}\operatorname{tr}\!\bigl((P_{a,b}\otimes P_{c,d})J_E\bigr) \bigl(\mathcal I_F(P_{a,b})\otimes\mathcal I_F(P_{c,d})\bigr),$$

where real coefficients act as complex scalars. No channel assumption on $E$ or projector conditions on the frame matrices are imposed, and the result is zero if $\mathcal C_F$ is not injective.

QAlgorithms.Papers.Independent.Intakethird100.P66.appendMatrixTensor

For all natural numbers $a,b$, including zero, and arbitrary complex matrices $A$ and $B$ indexed respectively by $a$-bit and $b$-bit strings, this defines a complex matrix on $(a+b)$-bit strings. Writing $x=u\mathbin{\|}v$ and $y=u'\mathbin{\|}v'$ for concatenations with first blocks of length $a$ and second blocks of length $b$, its entries are

$$(A\otimes_{\mathrm{append}}B)_{x,y}=A_{u,u'}B_{v,v'}.$$

No conditions on $A$ or $B$ are required. A zero-length block has exactly one bit string, so its matrix is a scalar factor.

QAlgorithms.Papers.Independent.Intakethird100.P66.basisBornWeight

For every natural number $m$, including $0$, let $Q_m=\{0,1\}^m$, and let $F$ consist of a finite nonempty type $\mathcal B$ and matrices $P_{a,b}\in\mathbb C^{Q_m\times Q_m}$ for every $a\in\mathcal B$ and $b\in Q_m$. For every matrix $\rho\in\mathbb C^{Q_m\times Q_m}$ and pair $s=(a,b)\in\mathcal B\times Q_m$, this definition assigns the real number

$$w_F(\rho;(a,b))=\frac{\operatorname{Re}\operatorname{tr}(P_{a,b}\rho)}{|\mathcal B|}.$$

The data defining $F$ impose no projector, positivity, or completeness conditions on the matrices $P_{a,b}$, and $\rho$ is arbitrary, so these numbers need not be nonnegative or sum to $1$. When $m=0$, $Q_m$ contains the single empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P66.basisMeasurementChannel

For every natural number $m$, including $0$, let $Q_m=\{0,1\}^m$ and let $F$ consist of a finite nonempty type $\mathcal B$ and arbitrary matrices $P_{a,b}\in\mathbb C^{Q_m\times Q_m}$. This definition constructs the complex-linear map $\mathcal C_F:\mathbb C^{Q_m\times Q_m}\to\mathbb C^{Q_m\times Q_m}$ given, for every matrix $X$ and every $i,j\in Q_m$, by

$$\bigl(\mathcal C_F(X)\bigr)_{i,j} =\sum_{k,l\in Q_m} \left(\frac1{|\mathcal B|} \sum_{a\in\mathcal B}\sum_{b\in Q_m} (P_{a,b})_{l,k}(P_{a,b})_{i,j}\right)X_{k,l} =\frac1{|\mathcal B|}\sum_{a,b}\operatorname{tr}(P_{a,b}X)\,(P_{a,b})_{i,j}.$$

The displayed products contain no complex conjugation. The frame data impose no further conditions ensuring positivity, trace preservation, or injectivity of this map.

QAlgorithms.Papers.Independent.Intakethird100.P66.centeredVariance

For every natural number $m$, write $\mathcal B_m=\{0,1\}^m$, and let $P$ consist of a probability measure $\mu$ on unitary matrices indexed by $\mathcal B_m$, with the requirement that the linear map

$$\mathcal C_\mu(X)=\int\sum_{b\in\mathcal B_m}(UXU^\dagger)_{bb}\, U^\dagger|b\rangle\langle b|U\,d\mu(U)$$

is injective; its inverse is therefore defined on all matrices of this size. For every complex matrix $O$ indexed by $\mathcal B_m$, this defines $\operatorname{centeredVariance}(P,O)=0$ if $O$ is not Hermitian. If $O$ is Hermitian, put $O_0=O-\operatorname{Tr}(O)I/2^m$; the value is

$$\left( \sqrt{\sup_{\substack{\sigma\succeq0\\\operatorname{Tr}\sigma=1}} \int\sum_{b\in\mathcal B_m} \operatorname{Re}(U\sigma U^\dagger)_{bb}\, \left[\operatorname{Re}\!\left(U\mathcal C_\mu^{-1}(O_0)U^\dagger\right)_{bb}\right]^2 \,d\mu(U)} \right)^2.$$

The supremum and square root are the total real operations used in the definition. The case $m=0$ is included, with $\mathcal B_0$ consisting of the unique empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P66.choiSnapshot

For every natural number $n$, including $0$, let $Q_{2n}=\{0,1\}^{2n}$, and let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary matrices $P_{a,b}\in\mathbb C^{Q_{2n}\times Q_{2n}}$. Define

$$\mathcal C_F(X)=\frac1{|\mathcal B|}\sum_{a\in\mathcal B}\sum_{b\in Q_{2n}} \operatorname{tr}(P_{a,b}X)\,P_{a,b}.$$

For every $s=(a,b)\in\mathcal B\times Q_{2n}$, this definition assigns the matrix $2^n\mathcal C_F^{-1}(P_{a,b})$ if $\mathcal C_F$ is injective, and the zero matrix otherwise. The inverse is the inverse complex-linear endomorphism, and $2^n$ is regarded as a complex scalar. At $n=0$, the scaling factor is $1$ and the matrices have one row and one column.

QAlgorithms.Papers.Independent.Intakethird100.P66.embedProcessObservable

For all natural numbers $n,k$, an injection $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$, and an arbitrary complex matrix $O$ on $2k$-bit strings, this defines a matrix $\widetilde O$ on $2n$-bit strings. For $n$-bit strings $u,v,u',v'$, its entries are

$$\widetilde O_{u\mathbin{\|}v,\;u'\mathbin{\|}v'} = \begin{cases} O_{(u\circ w)\mathbin{\|}(v\circ w),\; (u'\circ w)\mathbin{\|}(v'\circ w)}, &\text{if }u_j=u'_j\text{ and }v_j=v'_j \text{ for every }j\notin\operatorname{im}w,\\ 0,&\text{otherwise}. \end{cases}$$

Here concatenation joins the indicated bit strings, and the injection entails $k\le n$. There is no Hermiticity assumption on $O$. If $k=0$, the result is the sole entry of $O$ times the identity; if $w$ covers every position, the condition outside its image is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P66.finiteMax

For every type $A$ equipped with a finite enumeration and every function $f:A\to\mathbb R$, this defines $\operatorname{finiteMax}(f)$ to be $\max_{a\in A}f(a)$ when $A$ is nonempty, and zero when $A$ is empty. In the nonempty case the maximum may be negative; zero is only the specified value for the empty case.

QAlgorithms.Papers.Independent.Intakethird100.P66.frameInverse

For every natural number $m$, including $0$, let $Q_m=\{0,1\}^m$, and let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary complex matrices $P_{a,b}$ indexed by $a\in\mathcal B$ and $b\in Q_m$. Define the complex-linear map

$$\mathcal C_F(X)=\frac1{|\mathcal B|}\sum_{a\in\mathcal B}\sum_{b\in Q_m} \operatorname{tr}(P_{a,b}X)\,P_{a,b}.$$

This definition assigns a complex-linear map $\mathcal I_F$ on the same matrix space: if $\mathcal C_F$ is injective, then $\mathcal I_F=\mathcal C_F^{-1}$, using the fact that an injective linear endomorphism of this finite-dimensional space is bijective; otherwise $\mathcal I_F$ is the zero map. Injectivity is tested in the definition and is not assumed of $F$.

QAlgorithms.Papers.Independent.Intakethird100.P66.frameSnapshot

For every natural number $m$, including $0$, let $Q_m=\{0,1\}^m$, and let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary matrices $P_{a,b}\in\mathbb C^{Q_m\times Q_m}$. Form the complex-linear map

$$\mathcal C_F(X)=\frac1{|\mathcal B|}\sum_{a\in\mathcal B}\sum_{b\in Q_m} \operatorname{tr}(P_{a,b}X)\,P_{a,b}.$$

For every pair $s=(a,b)\in\mathcal B\times Q_m$, the defined snapshot is $\mathcal C_F^{-1}(P_{a,b})$ if $\mathcal C_F$ is injective, and is the zero matrix otherwise; the inverse exists in the injective case because the domain and codomain are the same finite-dimensional complex vector space. No projector or normalization conditions on $P_{a,b}$ are assumed.

QAlgorithms.Papers.Independent.Intakethird100.P66.globalFrame

For every natural number $m$, assuming a specified finite enumeration of the projective group described below, this defines a frame with that group as its basis-choice set. Start with the subgroup of unitary matrices on $m$-bit strings generated by all matrices $i^c\bigotimes_j P_j$, where $c\in\{0,1,2,3\}$ and each $P_j$ is one of the usual matrices $I,X,Y,Z$; take its normalizer in the full unitary group, and identify two normalizer elements $U,V$ exactly when $UXU^\dagger=VXV^\dagger$ for every complex matrix $X$. The resulting quotient is the basis-choice set, which is nonempty because it contains the identity class. For a class $a$, choose its designated quotient representative $U_a$; for every outcome $m$-bit string $b$, the assigned matrix is

$$P_{a,b}(x,y)=\overline{(U_a)_{b,x}}\,(U_a)_{b,y}.$$

The definition includes $m=0$, where the outcome and matrix index sets each contain one empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P66.matrixError

For every natural number $m$, including $0$, every complex matrix $X$ indexed by the bit strings $Q_m=\{0,1\}^m$, and either choice frobenius or trace, this definition returns respectively

$$\left(\sum_{u,v\in Q_m}|X_{u,v}|^2\right)^{1/2} \quad\text{or}\quad \operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X},$$

where $X^\dagger$ is the conjugate transpose and the square root is the positive semidefinite square root supplied by continuous functional calculus. No Hermitian or positivity assumption on $X$ is required. When $m=0$, $X$ is a one-by-one matrix.

QAlgorithms.Papers.Independent.Intakethird100.P66.meanChoiSnapshot

For every natural number $n$, including $0$, write $Q_n=\{0,1\}^n$ and identify a $2n$-bit string with its ordered pair of $n$-bit halves. Let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary matrices $P_{a,b}$ on $Q_{2n}$, and let $E$ be any function from complex matrices on $Q_n$ to complex matrices on $Q_n$, without a linearity or channel assumption. Define the matrix $J_E$ by

$$(J_E)_{(u,v),(u',v')}=2^{-n}\bigl(E(e_{u,u'})\bigr)_{v,v'},$$

where $e_{u,u'}$ has entry $1$ at $(u,u')$ and $0$ elsewhere. Also set $\mathcal C_F(X)=|\mathcal B|^{-1}\sum_{a,b}\operatorname{tr}(P_{a,b}X)P_{a,b}$, and let $\mathcal I_F=\mathcal C_F^{-1}$ if $\mathcal C_F$ is injective and $\mathcal I_F=0$ otherwise. This definition assigns

$$\frac{2^n}{|\mathcal B|} \sum_{a\in\mathcal B}\sum_{b\in Q_{2n}} \operatorname{Re}\operatorname{tr}(P_{a,b}J_E)\,\mathcal I_F(P_{a,b}),$$

with the real coefficients regarded as complex scalars. The expression is zero when $\mathcal C_F$ is not injective; its coefficients are not assumed to form a probability distribution.

QAlgorithms.Papers.Independent.Intakethird100.P66.overlapObservable

For every natural number $n$ and arbitrary complex matrices $\rho,\sigma$ indexed by $\{0,1\}^n$, this defines a complex matrix indexed by $2n$-bit strings through

$$\operatorname{overlapObservable}(\rho,\sigma)_{a\,\Vert\,b,\;a'\,\Vert\,b'} =\rho_{a',a}\,\sigma_{b,b'},$$

where $a,a',b,b'\in\{0,1\}^n$ and $\Vert$ denotes concatenation. Equivalently, it is $\rho^{\mathsf T}\otimes\sigma$ expressed in concatenated-bit coordinates; the transpose does not conjugate entries. Neither input is required to be a density matrix or Hermitian, and $n=0$ is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P66.pauliFrame

For every natural number $m$, this defines a frame whose finite, nonempty basis-choice set consists of all functions $a:\{0,\ldots,m-1\}\to\{X,Y,Z\}\times\{\mathrm{false},\mathrm{true}\}$, with the constant choice $(Z,\mathrm{true})$ witnessing nonemptiness. For an outcome bit string $b$, write $a_j=(A_j,t_j)$ and let $s_j=1$ if $t_j\ne b_j$, and $s_j=-1$ otherwise. The assigned matrix is

$$P_{a,b}(y,z)= \prod_{j=0}^{m-1} \left[\frac{I+s_j\sigma_{A_j}}2\right]_{y_j,z_j}, \qquad \sigma_X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad \sigma_Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad \sigma_Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},$$

with rows and columns ordered as false, true. This expands the factor $3^m$ multiplying the defined Pauli measurement matrix, whose factor is $3^{-m}$. When $m=0$, both the choice set and the outcome set are singletons, and the empty product gives the one-entry matrix $[1]$.

QAlgorithms.Papers.Independent.Intakethird100.P66.pauliNormEnvelope

For every natural number $k$, this defines

$$\operatorname{pauliNormEnvelope}(k)= \max_{p\in\{I,X,Y,Z\}^{2k}}\|Q_p\|_{\mathrm{op}}^2, \qquad (Q_p)_{y,z}=\prod_{j=0}^{2k-1}(p_j)_{y_j,z_j}, \quad y,z\in\{0,1\}^{2k},$$

where $\|\cdot\|_{\mathrm{op}}$ is the operator norm for Euclidean norms, and the four matrices, in bit order $0,1$, are

$$I=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.$$

The maximum uses zero as its default for an empty indexing type, although this particular indexing type is always nonempty. When $k=0$, it contains the unique empty assignment, and its empty product is the $1\times1$ identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P66.primitiveRecordLaw

For every natural number $m$, write $\mathcal B_m=\{0,1\}^m$, and let $P$ specify a probability measure $\mu$ on unitary matrices indexed by $\mathcal B_m$ for which the map $X\mapsto\int\sum_b(UXU^\dagger)_{bb}U^\dagger|b\rangle\langle b|U\,d\mu(U)$ is injective. For every complex matrix $\rho$ indexed by $\mathcal B_m$ and every natural number $N$, this defines the product measure $\nu_{P,\rho}^{\otimes N}$ on records $(U_j,b_j)_{j=0}^{N-1}$, where

$$\nu_{P,\rho} =\sum_{b\in\mathcal B_m}(U\mapsto(U,b))_* \left(\max\{\operatorname{Re}(U\rho U^\dagger)_{bb},0\}\,\mu(dU)\right).$$

There are no density-matrix assumptions on $\rho$. When $N=0$, the record space consists of the unique empty record and the product measure assigns it mass one.

QAlgorithms.Papers.Independent.Intakethird100.P66.primitiveShotLaw

For every natural number $m$, let $\mathcal B_m=\{0,1\}^m$, and let $P$ specify a probability measure $\mu$ on unitary matrices indexed by $\mathcal B_m$ such that

$$X\longmapsto\int\sum_{b\in\mathcal B_m}(UXU^\dagger)_{bb}\, U^\dagger|b\rangle\langle b|U\,d\mu(U)$$

is injective. For any complex matrix $\rho$ indexed by $\mathcal B_m$, this defines a measure on pairs $(U,b)$ by

$$\nu_{P,\rho} =\sum_{b\in\mathcal B_m} (U\mapsto(U,b))_* \left(\max\{\operatorname{Re}(U\rho U^\dagger)_{bb},0\}\,\mu(dU)\right).$$

Thus each summand weights $\mu$ by the nonnegative part of the indicated real diagonal entry and then attaches the fixed outcome $b$. No assumption says that $\rho$ is Hermitian, positive semidefinite, or trace one, so the definition does not require this measure to be a probability measure. The case $m=0$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P66.processChoi

For every natural number $n$, including zero, and every function $E$ from complex matrices on $n$-bit strings to complex matrices on $n$-bit strings, this defines a matrix $J_E$ on $2n$-bit strings by

$$(J_E)_{u\mathbin{\|}v,\;u'\mathbin{\|}v'}=\bigl(E(e_{u,u'})\bigr)_{v,v'},$$

where $u,u',v,v'$ are $n$-bit strings and $e_{u,u'}$ is the matrix whose only nonzero entry is $1$ at row $u$, column $u'$. There is no assumption that $E$ is linear or is a channel. When $n=0$, the sole entry is the sole entry of $E([1])$.

QAlgorithms.Papers.Independent.Intakethird100.P66.processChoiState

For every natural number $n$, including zero, and arbitrary function $E$ from complex matrices on $n$-bit strings to themselves, this defines the matrix with entries

$$(J_E^{\mathrm{scaled}})_{u\mathbin{\|}v,\;u'\mathbin{\|}v'}=2^{-n}\bigl(E(e_{u,u'})\bigr)_{v,v'},$$

where concatenation places the first $n$-bit string before the second, and $e_{u,u'}$ has entry $1$ at $(u,u')$ and zero elsewhere. No linearity, positivity, or trace condition is imposed on $E$ or the resulting matrix. For $n=0$, the scaling factor is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P66.processMarginal

For all natural numbers $n,k$, an arbitrary complex matrix $\rho$ on $2n$-bit strings, and an injection $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$, this defines a matrix on $2k$-bit strings as follows. For an $n$-bit string $a$ and a $k$-bit string $u$, let $a[w\leftarrow u]$ have value $u_i$ at position $w(i)$ and value $a_j$ at every position outside the image of $w$. Then

$$\rho^{\,w}_{u\mathbin{\|}v,\;u'\mathbin{\|}v'} = \sum_{\substack{a,b\in\{0,1\}^n\\ a_{w(i)}=b_{w(i)}=0\ \text{for every }i}} \rho_{\,a[w\leftarrow u]\mathbin{\|}b[w\leftarrow v],\; a[w\leftarrow u']\mathbin{\|}b[w\leftarrow v']}.$$

The injection entails $k\le n$. No density-matrix assumption is imposed on $\rho$. For $k=0$, this is the one-entry matrix containing $\operatorname{tr}\rho$; when $w$ covers all positions, only the all-zero choices of $a,b$ contribute.

QAlgorithms.Papers.Independent.Intakethird100.P66.recordProbability

For every pair of natural numbers $m,N$, let $Q_m=\{0,1\}^m$, let $F$ consist of a finite nonempty type $\mathcal B$ and arbitrary complex matrices $P_{a,b}$ indexed by $a\in\mathcal B$ and $b\in Q_m$, and let $\rho$ be any complex matrix indexed by $Q_m$. For every predicate $\mathcal E$ on records $r:\{0,\ldots,N-1\}\to\mathcal B\times Q_m$, this definition assigns

$$\sum_{\substack{r:\{0,\ldots,N-1\}\to\mathcal B\times Q_m\\ \mathcal E(r)}} \ \prod_{j=0}^{N-1} \frac{\operatorname{Re}\operatorname{tr}(P_{a_j,b_j}\rho)}{|\mathcal B|}, \qquad r(j)=(a_j,b_j).$$

No assumptions ensure that this expression is a probability. For $N=0$, there is one empty record and its product is $1$, so the result is $1$ if that record satisfies $\mathcal E$ and $0$ otherwise; $m=0$ is also allowed.

QAlgorithms.Papers.Independent.Intakethird100.P66.reducedLog

For all natural numbers $n,k$ and every real number $\delta$, this defines

$$\operatorname{reducedLog}(n,k,\delta) =\log\!\left(\frac{2(8n)^{2k}}{\delta}\right).$$

Here the real logarithm is total: $\log0=0$, and for a negative argument it equals the logarithm of its absolute value; division by zero gives zero. Consequently $\delta=0$ gives zero. The exponent is zero when $k=0$, including when $n=0$, so that case gives $\log(2/\delta)$; when $n=0$ and $k>0$, the result is zero. There are no positivity assumptions on $n,k,\delta$.

QAlgorithms.Papers.Independent.Intakethird100.P66.reducedVariance

For every natural number $n$, let $\mathcal B_j=\{0,1\}^j$, and let $P$ specify a probability measure $\mu$ on unitary matrices indexed by $\mathcal B_{2n}$ with injective linear map

$$\mathcal C_\mu(X)=\int\sum_{b\in\mathcal B_{2n}} (UXU^\dagger)_{bb}U^\dagger|b\rangle\langle b|U\,d\mu(U).$$

For each natural number $k$, this defines the maximum of the following quantity over all injections $w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}$ and all choices $p_0,\ldots,p_{2k-1}\in\{I,X,Y,Z\}$. Here

$$I=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},$$

and $Q_p$ is the matrix with entries $(Q_p)_{s,t}=\prod_{j=0}^{2k-1}(p_j)_{s_j,t_j}$. Define $O_{w,p}$, indexed by pairs of $n$-bit strings, by

$$(O_{w,p})_{(a,b),(a',b')}= \begin{cases} (Q_p)_{(a\circ w,b\circ w),(a'\circ w,b'\circ w)}, & a_j=a'_j\ \text{and }b_j=b'_j\text{ for every }j\notin\operatorname{range}(w),\\ 0,&\text{otherwise}. \end{cases}$$

For any matrix $O$, the quantity being maximized is zero if $O$ is not Hermitian; otherwise, with $O_0=O-\operatorname{Tr}(O)I/2^{2n}$, it is

$$\left( \sqrt{\sup_{\substack{\sigma\succeq0\\\operatorname{Tr}\sigma=1}} \int\sum_{b\in\mathcal B_{2n}} \operatorname{Re}(U\sigma U^\dagger)_{bb} \left[\operatorname{Re}\!\left(U\mathcal C_\mu^{-1}(O_0)U^\dagger\right)_{bb}\right]^2 \,d\mu(U)} \right)^2,$$

evaluated at $O=O_{w,p}$. If the indexing set is empty, the value is defined to be zero; in particular this happens when $k>n$. The case $k=0$ includes the unique empty injection and empty Pauli assignment, whose matrix product is the scalar identity.

QAlgorithms.Papers.Independent.Intakethird100.P66.sampleCount

For every natural number $k$ and real number $B$, this defines the natural number

$$\operatorname{sampleCount}(k,B)= \begin{cases} 0,&k=0,\\ \max\{0,\lceil B\rceil\},&k\ne0. \end{cases}$$

Thus $k=0$ gives zero regardless of $B$, and $B\le0$ gives zero for every $k$.

QAlgorithms.Papers.Independent.Intakethird100.P66.singleCliffordFrame

Assuming a specified finite enumeration of the one-qubit projective group, this recursively defines a frame for every natural number $m$. This projective group is obtained by taking the normalizer, within the one-qubit unitary group, of the subgroup generated by $i^cP$ for $c\in\{0,1,2,3\}$ and $P\in\{I,X,Y,Z\}$, and identifying $U,V$ when $UXU^\dagger=VXV^\dagger$ for every complex $2\times2$ matrix $X$. The zero-bit frame has a singleton choice set and assigned matrix $[1]$. At each successor, its choice set is the previous choice set times this projective group, and its matrices are the appended tensor products of the previous matrices with $\bigl(\overline{(U_a)_{b,x}}(U_a)_{b,y}\bigr)_{x,y}$, where $U_a$ is the designated representative of the new class and $b$ is the new outcome bit. Thus, identifying choices with $m$ successive classes $a_0,\ldots,a_{m-1}$, the assigned matrix for outcome $b$ has entries

$$P_{a,b}(x,y)=\prod_{j=0}^{m-1} \overline{(U_{a_j})_{b_j,x_j}}\,(U_{a_j})_{b_j,y_j}.$$

At $m=0$, the product is empty and equals $1$.

QAlgorithms.Papers.Independent.Intakethird100.P66.tensorFrame

For all natural numbers $a,b$ and arbitrary frames $F$ and $G$ on respectively $a$ and $b$ bits, this defines a frame on $a+b$ bits. A frame here supplies a finite, nonempty choice set and an arbitrary complex matrix for each choice and outcome bit string. The new choice set is the Cartesian product of the two supplied choice sets, with its induced finite enumeration and nonemptiness. For choices $f,g$, outcome $x=u\mathbin{\|}v$, and matrix indices $y=r\mathbin{\|}s$ and $z=r'\mathbin{\|}s'$, the assigned matrix has entry

$$P_{(f,g),\,u\mathbin{\|}v}(y,z) =(F_{f,u})_{r,r'}(G_{g,v})_{s,s'}.$$

No additional matrix conditions are assumed. Either block length may be zero, in which case that block contributes its one-entry matrix as a scalar factor.

QAlgorithms.Papers.Independent.Intakethird100.P66.traceSampleLog

For all natural numbers $n,k$ and every real number $\delta$, this defines

$$\operatorname{traceSampleLog}(n,k,\delta) =\log\!\left(\frac{(24n)^{2k}}{\delta}\right).$$

The real logarithm is total, with $\log0=0$ and $\log x=\log|x|$ for $x\ne0$, and division by zero gives zero. Thus $\delta=0$ gives zero; $k=0$, including $n=k=0$, gives $\log(1/\delta)$; and $n=0$ with $k>0$ gives zero. No positivity assumptions are imposed.

QAlgorithms.Papers.Independent.Intakethird100.P66.twoSidedReconstruction

For every natural number $n$, including $0$, let $Q_n=\{0,1\}^n$, let $0_n$ be its all-false string, let $F$ supply a finite nonempty type $\mathcal B$ and arbitrary complex matrices $P_{a,b}$ on $Q_n$, and let $E$ be any function from complex matrices on $Q_n$ to themselves. Define $\mathcal C_F(X)=|\mathcal B|^{-1}\sum_{a,b}\operatorname{tr}(P_{a,b}X)P_{a,b}$ and let $\mathcal I_F$ be its inverse complex-linear map if it is injective, or the zero map otherwise. With $A\otimes B$ represented on concatenated bit strings by $(A\otimes B)_{(u,v),(u',v')}=A_{u,u'}B_{v,v'}$, this definition assigns

$$\frac1{|\mathcal B|^2} \sum_{a,c\in\mathcal B}\sum_{d\in Q_n} \operatorname{Re}\operatorname{tr}\!\bigl(P_{c,d}\,E(P_{a,0_n})\bigr) \left(\mathcal I_F(P_{a,0_n}^{\mathsf T})\otimes \mathcal I_F(P_{c,d})\right).$$

Here ${}^{\mathsf T}$ denotes ordinary transpose without conjugation, and the real coefficients act as complex scalars. Only the outcome $0_n$ is used for the first frame matrix. No channel assumption on $E$ or projector conditions on the frame are imposed; if $\mathcal C_F$ is not injective, the result is zero.