All known mappings that encode fermionic modes into a bosonic qubit system are non-local transformations. Either local fermionic operators are mapped to non-local qubit operators (as in the Jordan-Wigner transformation), or uncorrelated fermionic state are mapped to long range entangled qubit states (as in the Bravyi-Kitaev transformation). In this talk I will show that this must necessarily be the case for many choices of the graph representing the locality structure of the system (for example for regular 2d lattices). 

In particular, I show that the minimal amount of non-locality present in the transformation is related to specific properties of the locality graph, such as the number of cycles and the way in which these cycles overlap. A consequence of this, for instance, is that on 2d lattices there exist states that are simple from the fermionic point of view, while in any encoding require a circuit of depth at least proportional to the system size to be prepared, leading to a potential separation in the power of constant depth fermionic and qubit circuits.