Lowering qubit requirements using binary codes
Introduction
Molecular Hamiltonians are known to have certain symmetries that are not taken into account by mappings like the Jordan-Wigner or Bravyi-Kitaev transform. The most notable of such symmetries is the conservation of the total number of particles in the system. Since those symmetries effectively reduce the degrees of freedom of the system, one is able to reduce the number of qubits required for simulation by utilizing binary codes (arXiv:1712.07067).
We can represent the symmetry-reduced Fermion basis by binary vectors of a set $\mathcal{V} \ni \boldsymbol{\nu}$, with $ \boldsymbol{\nu} = (\nu_0, \, \nu_1, \dots, \, \nu_{N-1} ) $, where every component $\nu_i \in \lbrace 0, 1 \rbrace $ and $N$ is the total number of Fermion modes. These binary vectors $ \boldsymbol{\nu}$ are related to the actual basis states by: $$ \left[\prod_{i=0}^{N-1} (a_i^{\dagger})^{\nu_i} \right] \left|{\text{vac}}\right\rangle \, , $$ where $ (a_i^\dagger)^{0}=1$. The qubit basis, on the other hand, can be characterized by length-$n$ binary vectors $\boldsymbol{\omega}=(\omega_0, \, \dots , \, \omega_{n-1})$, that represent an $n$-qubit basis state by: $$ \left|{\omega_0}\right\rangle \otimes \left|\omega_1\right\rangle \otimes \dots \otimes \left|{\omega_{n-1}}\right\rangle \, . $$ Since $\mathcal{V}$ is a mere subset of the $N$-fold binary space, but the set of the vectors $\boldsymbol{\omega}$ spans the entire $n$-fold binary space we can assign every vector $\boldsymbol{\nu}$ to a vector $ \boldsymbol{\omega}$, such that $n<N$. This reduces the amount of qubits required by $(N-n)$. The mapping can be done by a binary code, a classical object that consists of an encoder function $\boldsymbol{e}$ and a decoder function $\boldsymbol{d}$. These functions relate the binary vectors $\boldsymbol{e}(\boldsymbol{\nu})=\boldsymbol{\omega}$, $\boldsymbol{d}(\boldsymbol{\omega})=\boldsymbol{\nu}$, such that $\boldsymbol{d}(\boldsymbol{e}(\boldsymbol{\nu}))=\boldsymbol{\nu}$. In OpenFermion, we, at the moment, allow for non-linear decoders $\boldsymbol{d}$ and linear encoders $\boldsymbol{e}(\boldsymbol{\nu})=A \boldsymbol{\nu}$, where the matrix multiplication with the $(n\times N)$-binary matrix $A$ is $(\text{mod 2})$ in every component.
Symbolic binary functions
The non-linear binary functions for the components of the decoder are here modeled by the $\text{BinaryPolynomial}$ class in openfermion.ops. For initialization we can conveniently use strings ('w0 w1 + w1 +1' for the binary function $\boldsymbol{\omega} \to \omega_0 \omega_1 + \omega_1 + 1 \;\text{mod 2}$), the native data structure or symbolic addition and multiplication.
