Bravyi–Kitaev mapping

The paper never uses the name. Bravyi and Kitaev define this encoding in §5, Fast simulation procedures, and call it nothing — the text says "encodings of the form" and draws a binary tree. Bravyi–Kitaev transform is what the community later called it. This record uses the common name because that is what a reader will search for, and states here that it is not the paper's own word, because a record that quotes a paper should not put a word in its mouth.

The problem it solves is a bookkeeping cost. Under the standard identification of $m$ fermionic modes with $m$ qubits, an annihilation operator carries the Jordan–Wigner sign $(-1)^{\sum_{s<j} n_s}$, and computing that string touches every qubit below $j$. Storing $y_j = \sum_{s<j} n_s$ instead fixes the read and breaks the write: changing one occupation number then forces an update to every $y_k$ above it. The paper states the trade in exactly those terms and resolves it by storing partial sums.

The encoding. Eq. (19) is

$|n_0,\dots,n_{m-1}\rangle \mapsto |x_0\rangle \otimes \cdots \otimes |x_{m-1}\rangle, \qquad x_j = \sum_{s \preceq j} n_s,$

where $\preceq$ is a partial order on binary strings that makes the index set a binary tree. The inverse is Eq. (20), $n_j = x_j - \sum_{s \in K(j)} x_s$, and the parity sum the sign needs is Eq. (21), $y_j = \sum_{s \in L(j)} x_s$.

Where the logarithm comes from. The paper's own sentence is that each $n_s$ enters only $O(\log m)$ of the $x_j$, and that the sums in Eqs. (20) and (21) each contain $O(\log m)$ terms. Both directions are therefore cheap at once, which is what neither the occupation encoding nor the parity encoding manages alone. The extraction operator is Eq. (22), built from controlled-$X$ and controlled-$Z$ gates over the sets $K(j)$, $L(j)$ and $\{k : k \succeq j\}$, and the paper states it costs $O(\log m)$ operations. The abstract puts the headline the same way: simulating one fermionic gate costs $O(m)$ qubit gates under the standard correspondence, and a different encoding reduces it to $O(\log m)$.

Why this record does not join the map. What it documents is a transformation between representations, and the map draws no process that performs one. The operator it publishes is the output of the mapping, not an object a route holds between two processes — which is what the ingredient shelf's encoding abstention says, and this record is one of the six it says it about.