The Exercise

Of $2n$ qubits, some have suffered an error. Half of them, $n$ qubits chosen uniformly at random, are checked for errors, and the other half are kept. The exercise bounds the probability that the check finds few errors while the kept qubits hold many, by a quantity that falls exponentially in $n$ .

Random Checks

Label the $2n$ qubits by a set $S$ and let $E \subseteq S$ be the set of those in error. A check $C$ is a subset of $S$ with $n$ elements, and all $\binom{2n}{n}$ checks are equally likely. The check finds the $|C \cap E|$ errors inside it and leaves the $|E \setminus C|$ errors of the kept qubits unseen. For natural numbers $s$ and $t$ , the probability $p$ that it finds fewer than $s$ errors while more than $t$ go unseen is the fraction of checks with both properties, $p = \frac{\bigl|\{\, C \subseteq S : |C| = n,\ |C \cap E| < s,\ |E \setminus C| > t \,\}\bigr|} {\binom{2n}{n}}.$ (1)

The Claim

Theorem 1. Let $S$ be a set of $2n$ elements and $E$ a subset of $S$ . Let $s \ge 1$ and $t$ be natural numbers and $\varepsilon \ge 0$ a real number with $\varepsilon n \le |E| - 2(s-1)$ . Then the probability $p$ of (1) satisfies $p \le (2n+1)\, 2^{-\varepsilon^2 n/4}.$ (2)^✦

What Is Checked

The claim is stated over finite sets alone: the set $S$ , its subset $E$ , and the subsets of $S$ with $n$ elements that (1) counts.

What holds of them is the bound (2); the threshold $t$ enters the event and not the bound.