Speed up fermionic mappers by means of an intermediate conversion to majorana operators

[diagonal-hamiltonian]

What should we add?

From personal experience, the Qubit mapper is super slow. In my research, I found a way to speed things up for Majorana-string mappings eg: Jordan-Wigner, Bravyi-Kitaev, Ternary-tree, and Parity (see the Bonsai algorithm for more details). Some small background on the solution. Fermionic systems can be represented in the Majorana basis as:

$$\begin{split} \mathcal{H}_f &= \sum_{ij}^{N-1} h_{ij} a_i^{\dagger} {a_j} + \sum_{ijkl}^{N-1} h_{ijkl} a_i^{\dagger} a_j^{\dagger} {a_k} {a_l} \\\ &=\sum_{ij}^{2N-1}\mathrm{i} c_{ij} {m_i} {m_j} + \sum_{ijkl}^{2N-1} c_{ijkl} \, {m_i} {m_j} {m_k} {m_l}. \end{split}$$

where $h_{ij}, h_{ijkl}, c_{ij}$ and $c_{ijkl}$ are real coefficients. The 2N-Majorana operators are given in terms of linear combinations of the ladder operators:

$$\begin{gather} m_{2 j} \coloneqq a_{j}^\dagger + a_{j},\\ m_{2 j+1} \coloneqq \mathrm{i} (a_{j}^\dagger - a_{j}). \end{gather}$$

The solution is as follows:

1. Map the Fermionic Hamiltonian to a Majoranic Hamiltonian
   For each term in the FermionicOp, one should cache the result somehow of coefficients of the Majoranas resulting from ['+', '+', '-', '-'], ['+', '-', '+', '-'], ['+', '-'], ... etc. The Majoranaic Hamiltonian should then be sorted so that terms add like:

$$\{(0,1,2,3):1, (0,3,1,2):2\} \equiv \{(0,1,2,3):3\}$$

where $(0,1,2,3) \equiv m_0m_1m_2m_3$ and we use a dictionary as ${\text{majornana operator:coeff}}$. One must account for the anticommutation relations ${m_i,m_j}=\delta_{ij}$ here so

$$\{(0,1,2,3):1, (0,1,3,2):2\} \equiv \{(0,1,2,3):0\}$$

2. Map the Majoranic Hamiltonian to qubits.
   Mapper objects in qiskit like JordanWignerMapper use a PauliTable object to map mode operators to qubits. The object is structured: $[(P_0,P_1), (P_2,P_3), \ldots, (P_{2N-2},P_{2N-1})]$ where the Pauli strings are associated to Majorana operators as $P_i \ leftrightarrow m_i$. Thus one can map each term in the Majoranic Hamiltonian, resulting in a product of 2- or 4-Pauli strings which can be efficiently computed.

I include a graph of the speed comparison. I can also provide code if requested.

[mrossinek]

Adding a bit of historical context:

Performance of the mappers being sub-par is a known problem. See also #771 and #1289 for related discussions. There is also #1301.

The Bonsai mapper was also discussed before and is briefly referred to by #1289. #1270 is adding a MajoranaOp which will hopefully make an implementation of this mapper fairly straight forward.

That makes this issue/feature request a bit of a duplicate unless you want to rephrase it to explicitly ask for an implementation of the Bonsai mapping algorithm.

[diagonal-hamiltonian]

Thank you for your response. I have gone through the linked discussions but did not find any discussion related to the proposal I am making. I am not suggesting the implementation of the Bonsai mapper. Rather, I am proposing a speed-up that can be achieved after introducing MajoranaOp in #1270.

My request is for the implementation of QubitMapper that uses a MajoranaModeBasedMapper mapping method instead of the ModeBasedMapper. This will enable efficient mapping of Fermionic operators to qubits through intermediate Majorana operators. The reason for this is that it is much quicker to map the FermionicOp-->MajoranicOp-->SparsePauliOp than to map FermionicOp-->SparsePauliOp.

I have observed a significant speedup with my unoptimized python code, which is not parallelized, but could be (for a 28-qubit chemical Hamiltonian with 220288 terms, qiskit takes ~68s while my method takes ~7s)

[mrossinek]

Ah thanks for the clarification! That is indeed an interesting proposal 👍

[grossardt]

@diagonal-hamiltonian Do you have a good idea, why the way via Majorana operators is faster? I am wondering if it is due to the integer tuple implementation being more efficient than the string based SparseLabelOp operators. The MajoranaOp I have implemented is also a SparseLabelOp for compatibility reasons, i.e. it uses string labels instead of tuples of int.

[diagonal-hamiltonian]

@grossardt To be honest, I was quite surprised just how much faster this is as I am not entirely sure why. Initially, I thought the speed-up was from circumventing the Pauli multiplication in SparsePauliOp and reusing the cached coefficients resulting from the fermionic label ['+', '+', '-', '-'], ['+', '-', '+', '-'], ['+', '-'],... products. However, it could likely be from the integer tuple implementation being more efficient than the string based SparseLabelOp operators.