**Fermionic Quantum Computation **
Alexi Kitaev

We define a model of quantum computation with local fermionic modes (LFMs) instead of qubits. (An LFM is a site which can be either empty or occupied by a fermion). Despite the obvious correspondence between the Foch basis for fermions and the standard basis for qubits, the notion of a local gate is different in the two models. A universal set of fermionic gates is found. If the Foch space om $m$ LFMs is identified with the Hilbert space of $m$ qubits in the standard way, each fermionic gate can be simulated by qubit gates and vice vera, at cost $O(m)$. With different encodings, the cost factor can be reduced to $O(\log m)$ and a constant, respectively. Nearest-neighbors fermionic gates on a graph of bounded degree can be simulated at a constant cost. We also find a universal gate set for Majorana fermions which are basically halves of LFMs.

*created Thu Mar 2 11:35:21 PST 2000
*