GottesmanIntro Ch05b: supporting definitions

Gottesman, An introduction to quantum error correction, §5.2: decoding with bad extended

QAlgorithms.GottesmanIntro.exRecSize

For any protocol $P$ and any location kind $\kappa$ among preparation, Hadamard, T, CNOT, measurement, and wait, this is $|P.\mathrm{gadget}(\kappa)|+(\mathrm{lead}(\kappa)+\mathrm{trail}(\kappa))|P.\mathrm{ec}|$, where the size of a location circuit is the total number of listed locations over all its steps. The leading count is $0$ for preparation and otherwise the location arity; the trailing count is $0$ for measurement and otherwise the arity; CNOT has arity $2$ and every other kind has arity $1$. Thus the error-correction size multiplier is $1$ for preparation and measurement, $4$ for CNOT, and $2$ for Hadamard, T, and wait. A protocol contains arbitrary natural parameters $n,t,A$, a complex code subspace on $n$ bits, an encoding matrix from a Boolean index, a matrix-to-matrix decoding function, six gadgets on $\mathrm{arity}(\kappa)(n+A)$ bits, an error-correction circuit on $n+A$ bits, and a Boolean decoder of lists of measurement bits; it carries no correctness hypotheses. Empty gadgets and error-correction circuits are permitted.

QAlgorithms.GottesmanIntro.exRecSubsetMax

For any protocol $P$ with arbitrary natural parameters $n,t,A$, code subspace, encoding matrix, matrix-to-matrix decoding function, six location-circuit gadgets, error-correction location circuit, and Boolean decoder of measurement lists, this is the maximum over the six kinds preparation, Hadamard, T, CNOT, measurement, and wait of $\binom{s_\kappa}{t+1}$, where $s_\kappa$ is the gadget's number of listed locations plus the error-correction circuit's number of listed locations multiplied by $1$ for preparation or measurement, $4$ for CNOT, and $2$ for the other kinds. The fold takes its initial maximum against $0$. The binomial coefficient is $0$ whenever $t+1>s_\kappa$, so the result is $0$ if every size is at most $t$; no protocol correctness assumptions are imposed.

QAlgorithms.GottesmanIntro.levelReducedBound

For any protocol $P$ (arbitrary natural parameters $n,t,A$, code subspace, encoding matrix, decoding function, six gadgets, error-correction circuit, and measurement-list decoder), any natural number $N$, any location circuit $C$ on $N$ wires, any function $p:\mathbb N\times\mathbb N\to\mathbb R$, and any index pair $\ell$, this defines $\sum_{R\subseteq E,\ |R|=t+1}\prod_{j\in R}p(j)$ as a real number. To define $E$, replace each step $s$ of $C$ by gadget layers of depth equal to the maximum of the six gadget depths, concatenating at each layer the corresponding layer of each location's gadget in listed order, and then by all layers of the error-correction circuit on each wire that participates in a nonmeasurement location of that step, with these wires ordered increasingly. Each gadget location has owner equal to the original location pair; each error-correction location has owner $(s,q)$. These lists of layers define physical index pairs (layer number, position in layer). If $\ell$ is not a listed location of $C$, set $E=\varnothing$. Otherwise, writing its step as $s_\ell$ and its wire set as $Q_\ell$, include in $E$ precisely the physical locations owned by its gadget, together with error-correction locations owned by $(s,q)$ where $q\in Q_\ell$ and either its kind is not preparation and $s+1=s_\ell$, or its kind is not measurement and $s=s_\ell$. No trailing location is truncated. If $|E|<t+1$, including an invalid $\ell$, the sum is $0$; $p$ need not be nonnegative or bounded, and no well-formedness or correctness assumption is required for $P$ or $C$.