Succinct Fermion Data Structures

Many applications of quantum simulation require qubit representations of a fixed number of fermions (F) in a larger number of possible modes (M). Representing such states is possible with I := ⌈log(M choose F)⌉ qubits, but existing constructions achieving this level of compactness result in fermion operators with gate complexity exponential in I. We show that a small amount of redundancy enables efficiency, presenting a second quantized fermion encoding using I + O( F ) qubits such that fermion operators can be implemented in depth O( log M ) and gate complexity O(I). This is a polynomial improvement on prior second-quantized encodings, and is more space efficient than first-quantized representations. This encoding is succinct when F = o( M ), in the sense of being within a factor 1 + o(1) of optimal space usage.

Pizza and drinks will be served after the seminar in ATL 2117.