Succinct Fermion Data Structures

There has been a line of work on second-quantized fermion encodings for saving space when the number of fermions is fixed. Bravyi et al. give a scheme for utilizing symmetries in particle preserving Hamiltonians to remove degrees of freedom, using parity symmetries to achieve $M-O(1)$ qubits generically and LDPC codes for few fermion systems to achieve $M-O(M/F)$ qubits [6], but with gate overhead $O(M^3)$ in the worst case¹¹1Gate complexity here refers to the complexity of performing a single $\exp \left(-i\theta K\right)$, for some angle $\theta$ and number-preserving product of $O(1)$ many creation/annihilation operators $K$. For our discussions, we will not consider geometric locality.. Steudtner and Wehner give a scheme based on segmenting the space of fermions which again achieves $M-O(M/F)$ qubits, though allows more efficient $O(F^2)$ gate overhead [25, 24]. The same work also proposed a binary addressing code which shares some similarities with the encodings described here, but did not provide circuits for fermion operations nor bound the resource costs in the general case. The work of Babbush et al. [2] describes a way to store and manipulate few fermion systems using a sparse oracle, but do not provide explicit circuits for particle preserving rotations generated by creation-annihilation operators.

The work of Kirby et al. [19] describes a second quantized fermion encoding achieving $O(F^2{\log }^{4}M)$ space complexity and $O(F^2{\log }^{5}M)$ gate complexity, subject to a certain conjecture about Hermite interpolation. Additionally, the work of Harrison et al. [14] and Shee et al. [23] give methods for achieving exactly $ℐ$ qubit usage in second quantization, but at the cost of an exponential $M^{O(F)}$ gate complexity.

There are also first-quantized representations of fermion systems [26, 18, 1], where a list of occupied fermion modes is anti-symmetrized. This can save significant space when $F$ is much smaller than $M$. However, such encodings allow for a different class of operations²²2In particular, first-quantized operations. See [26] for examples of usage of these encodings in quantum simulation. to be performed efficiently as compared to second quantized encodings, making circuit complexity results within these two paradigms not directly comparable. Other works consider utilizing more than $M$ qubits and restricting to an entangled subspace, allowing certain sets of $k$-local fermion operations to be extremely efficient (see e.g. [29, 30, 11, 7]). These encodings are most relevant for geometrically local systems, and in fact increase space beyond the standard Jordan-Wigner encoding – we therefore omit them from comparisons.

We describe a quantum data structure which naturally captures the problem of encoding (second quantized) fermion systems in qubits. This structure represents bitstrings of length $M$ and Hamming weight $F$, which naturally correspond to fermionic Fock states. We consider the (quantum circuit) gate/depth complexity of a sgn-rank (“sign rank”) operator, which applies a phase conditioned on how many ones exist in some prefix of the bitstring, as well as a bit-flip operator which flips one of the bits. These operators allow us to straightforwardly express the fermionic operations which are relevant to quantum simulation, as we show in Section 3.

Within this framework, the Jordan-Wigner encoding can be seen as a data structure which encodes bitstring $b\in {\{0,1\}}^M$ by the quantum state $|b⟩$, e.g. the trivial encoding. The sign rank operation is then simply a contiguous string of $Z$ operators on some prefix, and the bit flip operator is a single $X$ operator. Our encodings employ a different representation of bitstrings which is more efficient when $F$ is small, requiring different quantum circuits.

We begin in Section 3 by developing a data structure which naturally captures fermion to qubit mappings of number preserving systems. This definition is not fully general, but provides a framework for thinking about such mappings. We then instantiate this data structure in two ways.

A system of fermions with $M$ modes can be defined by the algebra of creation ($a_i^{†}$ for $i\in [M]$) and annihilation ($a_i$ for $i\in [M]$) operators – this formalism is referred to as second quantization. These operators are determined by the anti-commutation relations

Let ${|00\mathrm{\dots }0⟩}_f$ denote the vacuum state, the unique state which is not annihilated by any of the $a_i^{†}$. We will primarily work with the Fock states, which are of the form

We denote the span of these states ${\mathscr{H}}^{(fock)}$. Note that the $M$-mode Fock states are in natural correspondence with $M$-bit strings – this observation underlies the famous Jordan Wigner encoding [17], and will similarly underlie our data structures. It will be convenient for us to work in the Majorana basis determined by ${\gamma }_j$ for $j\in [2m]$. These operators are defined as follows:

The action of Majorana operators on the Fock states can now be written as follows, where $\neg b$ is the negation of bit $b$,

In particular, these operators flip the occupation of a certain mode and apply a phase depending on the occupation of all preceding modes.

A fermion to qubit mapping can be defined by a linear mapping ${ℰ}_s$ from Fock states to qubit states, as well as a mapping ${ℰ}_o$ from Majorana operators to qubit operators. The qubit states/operators should be isomorphic to Fock states and Majorana operators, i.e. satisfy Equations 4, 5. Though some encodings do not fit into this paradigm (discussed in Section 1.1), this definition suffices for the encodings relevant to this paper. In particular, to define a mapping of an $M$ mode system it suffices to construct $2M$ mutually anti-commuting qubit operators which each square to the identity.

We note that it is not always necessary to encode every possible Fock state, e.g. when simulating a system that does not explore every state. Particularly relevant for us will be particle preserving systems, which live in the subspace of Fock states with exactly $F$ many fermions.

A well known example of a fermion-to-qubit mapping is the Jordan-Wigner encoding [17], which defines $M$-qubit operators as follows (where $P_i$ denotes a Pauli $P$ on the $i$-th qubit, acting trivially on the rest)

The mapped qubit operators in this encoding act on $M$ qubits, which means $M$ qubits are used to store fermionic states. Additionally, the circuit complexity of the mapped operators is $\mathrm{\Omega }(M)$, as some mapped operators act non-trivially on all qubits.

The main use case for fermion to qubit mappings is in the simulation of interacting fermions. In many such applications the dynamics are governed by a Hamiltonian $H$ which is both $k$-local and term-wise number preserving (i.e. each term commutes with ${\sum }_i{a}_i^{†}{a}_i$). If we wish to simulate such a system with $M$ modes, the most general Hamiltonian is

where the indices run over the $M$ modes and $h.c.$ denotes the hermitian conjugate of the preceding term. This type of system is ubiquitous in quantum chemistry and physics. To simulate a fermionic system, one requires a mapping from fermion states/operators to qubit states/operators, as discussed in Section 2.2. Almost all second quantized algorithms for approximating evolution $\exp \left(-iHt\right)$ involve performing rotations generated by terms in $H$ [9, 10, 4, 3, 20, 5, 21], so it is better for these rotations to require few gates and act on few qubits. Let $V$ be a product of $k$ Majorana operators, where $k$ is even. Our encodings give efficient circuits for rotations of the form $\exp \left(-i\theta V\right)$ ($k$ a multiple of $4$) or $\exp \left(-\theta V\right)$ ($k$ not a multiple of $4$)⁵⁵5Actually, in most places we give circuits for the operator $V$ up to a global phase. In the full version, we discuss how to generically implement the aforementioned rotations in the same complexity. Further, whether $k$ is a multiple of $4$ dictates whether $\exp \left(-i\theta V\right)$ or $\exp \left(-\theta V\right)$ is unitary; we implement the unitary one.. This is sufficient to implement any rotation generated by the product of $O(1)$ creation/annihilation operators and its hermitian conjugate. For an illustrative example, consider a hopping term $a_j^{†}{a}_k+h.c.$ for $j\ne k$,

from which it is clear that it suffices to implement two Majorana rotations. Note that although each Majorana operator itself need not preserve particle number, it changes the occupation number by at most $k$ (in this case at most two). Further, the whole operator does preserve particle number. Therefore, so long as our encoding has enough “space” to fit the intermediate states, we will remain in the proper subspace after implementing the full operator $\exp \left(-i\theta (a_j^{†}{a}_k+a_k^{†}{a}_j)\right)$. We refer the reader to the full version for a more general discussion of this procedure.

We first define two useful combinatorial operations, $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}$ and $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$. These are analogous to rank and bit flip queries respectively, which are well-studied in succinct classical data structures for bit-vectors [15, 22]⁶⁶6Note that the differing models of complexity (RAM programs/cell probe versus quantum circuits) prevent most of these classical results from being directly applicable to our problems.. These operators act on a bit string $𝐛=(b_1,\mathrm{\dots },b_M)\in {\{0,1\}}^M$ and depend on an index $j\in [M]$, and are combinatorial operations with no direct relation to fermions. However, they both show up naturally when writing down the action of fermionic creation-annihilation operators on Fock states: one can notice the similarities between Definitions 3, 4 and the action of Majorana operators in Equation 5.

With these two operations in hand, we can now describe the relevant type of (quantum) data structure for encoding fermionic states. Intuitively, we would like to represent a bit string $𝐛\in {\{0,1\}}^M$ in such a way that both $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}$ and $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$ queries can be implemented efficiently. Furthermore, in the settings we will care about we will be promised that the Hamming weight of $𝐛$ (the number of $1$’s) will never exceed $F+k$ or subceed $F-k$, for some and constant $k=O(1)$ (see the full version for more discussion). We use the notation ${\mathscr{H}}_{M,F,k}^{(fock)}$ to denote the Fock space of an $M$-mode system of fermions, restricted to states with occupation between $F-k$ and $F+k$: we call this range the capacity. We use the notation ${\mathscr{H}}_n^{(qubit)}$ to denote the Hilbert space of $n$ qubits.

The gate/depth complexity of the above structure is the max gate count/depth, respectively, of the $F_j,R_j$ over all $j\in [M]$. The space complexity is $n$ – note that ancillas used in $F_j$, $R_j$ are counted in this complexity, as they are circuits acting on exactly $n$ qubits.

We remark that we consider quantum circuit complexity as the relevant cost measure, which prevents us from using many standard data structures results. Classical results often use the cell probe model [12], which is based on a RAM machine that allows random access to data. This model may not capture complexity in a real world quantum computer [16]. This necessitates new data structures and new ideas, which will be the focus of this paper.

We first observe a subtlety in Definition 5: the operation of $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$ is only required to be “correct” so long as the capacity is not exceeded. When one is interested in simulating a $k$-local Hamiltonian on a system with exactly $F$ Fermions, then it often suffices to instantiate a Fermion data structure with capacity $F,k$⁷⁷7Note that this does incur some space overhead, but it is only an additive $O(1)$ (if $F=\mathrm{\Theta }(M)$) or $O(\log M)$ (if $F=O(M/\log M)$). In particular, it is straightforward to show that such a data structure can be used to instantiate a Trotterization scheme, or any simulation algorithm which relies on applying $k$-local particle-preserving rotations generated by products of $k$ creation/annihilation operators. Intuitively, so long as we can “fit” the intermediate states necessary while performing these rotations, we will be able to perform any arbitrary sequence of rotations.

We formally define the state encoding function ${ℰ}_s^{(1)}$ and give the algebraic properties it satisfies. Let $e_i\in {\{0,1\}}^M$ be a binary string that is all $0$’s, except for a single $1$ at position $i$ (using $1$-based indexing). Consider strings of the form

with $f\le F$. Define ${ℰ}^{(1)}:𝒟\to {\{0,1\}}^{F\lceil \log \left(M+1\right)\rceil }$, where $𝒟\subset {\{0,1\}}^M$ is the set of strings of Hamming weight at most $F$, as

where $\mathrm{\infty }$ is a placeholder for “no fermion”, and is the larger of any comparison with a non-$\mathrm{\infty }$. Concretely, we adopt the convention that $\mathrm{\infty }$ is represented by a register of all $1$’s. We can interpret the output as a sorted array of $f$ elements, each element (also referred to as register) of size $\lceil \log \left(M+1\right)\rceil$, and padded out to $F$ entries by $\mathrm{\infty }$’s. We will now describe the action of sign-rank and bit-flip queries on this list.

1. 1.

   A $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}(j,𝐛)$ query should apply a $-1$ phase if there are an odd number of registers having values less than or equal to $j$. Otherwise, it should act like the identity.

2. 2.

   A $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}(j,𝐛)$ should insert a register $|j⟩$ into the list if it is not present, and otherwise delete $|j⟩$. This operation should maintain sorted order, and act as described so long as both input and output states have Hamming weight less or equal to $F$.

Observe that both of the aforementioned operations are reversible. This suffices to define a fermion data structure.

We will utilize comparison circuits between unsigned integers as a black box. As described in Section 4.1, we will assume an upper limit $F$ on the number of pointers we will ever need to store, and therefore only utilize this many registers.

A notable problem with the previously described encoding is the serial nature of the bit flip operator. In particular, the depth of the circuits as described is $O(F\log M)$, primarily due to sequentially “bubbling” a targeted register to the end of the list when implementing a $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}(p,𝐛)$ operation. In this section, we describe a modification using $O(F\log M)$ ancillas that allows exponentially smaller depth, $O(\log F+\log \log M)$. Further, the buffer register idea developed here will prove useful when lowering depth in our succinct construction.

To achieve $O(\log F+\log \log M)$ depth, we will pad the encoded state with an $|\mathrm{\infty }⟩$ between registers and on either end. We will refer to these as buffer registers, in contrast with logical registers representing pointers. We will also pad the start with a $|-\mathrm{\infty }⟩$ and the end with $|\mathrm{\infty }⟩$ logical registers for convenience. Formally, consider strings of the form

where . Define ${ℰ}^{(2)}:{\{0,1\}}^M\to {\{0,1\}}^{O(F\log M)}$ as

where every other register is a buffer (coloured blue, but this is purely conceptual; the same data is stored in each). This leaves $O(F\log M)$ qubits, as the buffer registers are just a constant factor overhead. The correct action of $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}$ and $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$ exactly mirrors that of Section 4 on the logical registers (excluding the initial padded $-\mathrm{\infty }$), except now we must also leave the buffer registers invariant after the computation is finished.

We formally state the main theorem of this section below.

Such an encoding is constructed in the remainder of this section, with Lemma 15 and Lemma 16 demonstrating that it satisfies the requisite efficiencies. Similar to Corollary 8, this implies a fermion to qubit mapping with the same complexities.

To reduce the number of necessary qubits, the key insight is noting that the most significant $G:=\lceil \log F\rceil$ qubits in each register of the encoding in Section 4.1 are not pulling their weight. They use $F\cdot G=\mathrm{\Omega }(F\log F)$ qubits to encode $F$ integers in the range $1$ to $F$, but they are in sorted order, reducing the number of possible sequences – see Figure 1 for an illustration. We can instead store the same data (the most significant bits) in $O(F)$ space as a bit string where $2^G-1=O(F)$ zeroes delimit $2^G$ bins, and $F$ ones correspond to $F$ fermions. The $i$-th bin is the space from the $i$-th zero (or the start of the bit string) to the $i+1$-st zero (or the end of the bit string), and the number of ones in that range indicate elements with most significant bits $i$. This idea is commonly referred to as the stars and bars method.

The remaining least-significant bits can be stored in the usual way, where the order depends on the value determined by both least significant and most significant parts. So long as this order is maintained, the least-significant bits can be paired with the corresponding most-significant bits by the order in which they appear. This saves $F\lceil \log F\rceil$ qubits and adds $O(F)$ many, so the total qubit usage is

To define the encoding formally, for strings of the form

for , let $i_m$ denote the $G$ most significant bits of $i$, and $i_l$ denote the remaining least significant bits. Let $r_j$ be the number of pointers having most significant bits equal to $j$, i.e. the number of values of $k$ such that $i_m^{(k)}=j$. Now define ${ℰ}^{(3)}:{\{0,1\}}^M\to {\{0,1\}}^{ℐ+O(F)}$ as

Where $||$ is a conceptual divider between information about the most and least significant bits, and $1^n$ denotes $n$ many $1$’s. The bits to the left of $||$ store the least significant bits of each pointer, and are referred to as $l$ or LSBs, and $i$-th register in this section is $l_i$. The bits to the right of $||$ are referred to as $m$ or MSBs and store the most significant bits of each pointer. Define ${ℰ}_s^{(3)}:{\mathscr{H}}_{2^M}\to {\mathscr{H}}_{2^{ℐ+O(F)}}$ as the unique linear extension of ${ℰ}^{(3)}$. A simple example of this encoding is shown in Figure 2.

For correctness, it suffices if encoded $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$ and $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}$ operators satisfy the rules described in Section 4.1, on the list implicitly represented by our succinct string. In particular, the encoded $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}(p,𝐛)$ operator should unitarily insert/delete $p$ from the sorted list defined by the information stored in the MSBs and LSBs, and update this data accordingly. The $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}(p,𝐛)$ operator should apply a minus phase if and only if there are an odd number of elements less or equal to $p$ in the sorted list.

We now turn to constructing efficient circuits for the necessary operations on this succinct encoding. We note that retaining our space complexity advantage limits the number of ancillas that can be used to perform our operations to be $O(F)$ (and, naturally, we require these ancillas to be uncomputed by the end of each operation).

Randomized product formulas like the qDRIFT algorithm [9] are strong candidates where our encoding will be useful, as the complexity of such algorithms depend heavily on the fermion encoding used. The qDRIFT algorithm requires $O({(\lambda t)}^2/ϵ)$ fermionic rotation operators to evolve for time $t$ within error $ϵ$, where $\lambda$ is the sum of the magnitude of Hamiltonian coefficients when written in a second quantized basis. The scaling with $\lambda$ is preferable to scaling with $M$ when the magnitude of coefficients varies drastically, as is often the case for quantum chemistry Hamiltonians.

This theorem follows straightforwardly from using the qDRIFT algorithm [9] with our Footnote 3 In the regime discussed above, the space complexity of this algorithm is

with gate complexity

and circuit depth

We now compare these complexities against those achieved by other second-quantized encodings in our parameter regime.

In the context of post-Trotter methods, our encoding method can be relevant not only for saving space but also for saving gates. We illustrate this by giving a provably optimal implementation of the SELECT subroutine, a key component in the linear combination of unitaries algorithm for Hamiltonian simulation [10]. This algorithm involves expressing the Hamiltonian as a linear combination of unitaries

then block encoding the Hamiltonian using a PREPARE oracle that creates a superposition over every number in $j\in [q]$, weighted by amplitude ${\alpha }_j$, in conjunction with as a so-called SELECT oracle. The SELECT oracle has a control wire indicating a number $j\in [q]$, and conditioned on $j$ performs the unitary $U_j$ on the physical state – this oracle is the only part whose implementation is dependent on the fermion encoding used. One way to split a $k$-local second quantized fermionic Hamiltonian into a linear combination of unitaries is to split every $a_j$ into Majoranas $a_j={\gamma }_{2j-1}+i{\gamma }_{2j}$. The ${\gamma }_j$ operators are unitary, meaning the full Hamiltonian is now a linear combination of unitaries. Using our encoding, we can perform a SELECT oracle in the optimal complexity. Specifically, we show how to perform an $k$-local product of Majorana operators, given $k$ index wires denoting which Majoranas appear in the product. This translates to a sequence of $O(k)$ many $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}$ and $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}$ operations, so in particular it suffices to do a single $\mathrm{𝗌𝗀𝗇}\text{-}\mathrm{𝗋𝖺𝗇𝗄}(j,𝐛)$ or $\mathrm{𝖻𝗂𝗍}\text{-}\mathrm{𝖿𝗅𝗂𝗉}(j,𝐛)$ operator controlled on an index wire $|j⟩$.

First quantized algorithms maintain a list of pointers representing fermion positions similar to the encoding described in Section 4, but antisymmetrize the state over all possible permutations. The fermion phases then arise from the exchange statistics of the registers, allowing for a different class of efficient operations. Comparisons against first quantization are subtle, as algorithms within these two paradigms can have drastically different complexities for simulating similar systems. In general one would expect first quantized algorithms to outperform second quantized algorithms when $F$ is extremely small compared to $M$, but there is evidence that second quantized algorithms can remain advantageous when $F$ is polynomially smaller than $M$ [27]. This motivates the parameter regime we consider here.