Theorem: Sharp two-state classical bound

Every admitted wholly classical cut with $K\le 2$ satisfies

The bound allows stochastic encoding, storage, decoding, and input-independent shared randomness. It is attained by a sequential one-bit encoder.

Proof. It suffices to consider deterministic tables. For memory value $m$, let

An input $x$ encoded as $m$ has average success $1-d_{\mathrm{H}}(x,c_m)/2$. The best encoder for fixed answer words chooses a closest word, giving

There are four input words and at most two distinct answer words. At least two input words are not answer words and each has distance at least one. The distance sum is therefore at least two.

For attainment, store $X_1$ when it arrives, ignore the later $X_2$, answer query 1 correctly, and use a fixed answer for query 2. The score is