PauliComposer: compute tensor products of Pauli matrices efficiently

Pauli matrices [1] are one of the most important and well-known set of matrices within the field of quantum physics. They are particularly important in both physics and chemistry when used to describe Hamiltonians of many-body spin glasses [2‐7] or for quantum simulations [8‐13]. The vast majority of these systems are out of analytic control so that they are usually simulated through exact diagonalization which requires their Hamiltonians to be written in its matrix form. While this task may be regarded as a trivial matter in a mathematical sense, it involves the calculation of an exponentially growing number of operations. Furthermore, description of quantum systems via Matrix Product States (MPS) [14], Density Matrix Renormalization Group (DMRG) [15] and Projected Entangled Pair States (PEPS) [16] also involves large-scale Hamiltonians, as well as Lanczos method [17], whose formulation has been efficiently encoded on quantum hardware recently [18].

The PC algorithm could be implemented in computational frameworks in which this sort of operations is crucial, such as the Python modules Qiskit [19], PennyLane [20], OpenFermion [21] and Cirq [22]. It can also potentially be used in many other applications, such as the Pauli basis decomposition of the Fock space [23] and conventional computation of Ising model Hamiltonians to solve optimization problems [24‐27], among others.

The rest of the article is organized as follows: in Sect. 2 we describe the algorithm formulation in depth, showing a pseudocode-written routine for its computation. In Sect. 3, a set of tests is performed to show that a remarkable speed-up can be achieved when compared to state-of-the-art techniques. In Sect. 4, we show how this PC algorithm can be used to solve relevant problems. Finally, the conclusions drawn from the presented results are given in Sect. 5. We provide proofs for several statements and details of the algorithm in the appendices.

In this section, we discuss the PC algorithm formulation in detail. Pauli matrices are hermitian, involutory and unitary matrices that together with the identity form the set \(\sigma _{\{0, 1, 2, 3\}} = {\{I,X, Y, Z\}}\). Given an input string \(x = x_{n-1}\dots x_0\in \{0,1,2,3\}^n\), the PC algorithm constructsLet us denote its matrix elements as \(P_{j,k}(x)\) with \(j, k=0,\dots ,2^n-1\). It is important to remark that for each row j, there will be a single column k(j) such that \(P_{j, k(j)} \ne 0\) (see Appendix 1). The solution amounts to a map from the initial Pauli string to the positions and values of the \(2^n\) nonzero elements. This calculation will be done sequentially; hence, the complexity of the algorithm will be bounded from below by this number.

As a first step, it is worth noting that Pauli string matrices are either real (all elements are \(\pm 1\)) or purely imaginary (all are \(\pm i\)). This depends on \(n_Y\), the number of Y operators in P(x). We can redefine \(\tilde{Y}:=iY\), so that \(\smash [t]{\tilde{\sigma }_{\{0,1,2,3\}}=\{I, X, \tilde{Y}, Z\}}\) and \(\smash [t]{\tilde{P}(x):=\tilde{\sigma }_{x_{n-1}}\otimes \dots \otimes \tilde{\sigma }_{x_0}}\). As a result, every entry in \(\smash [t]{\tilde{P}(x)}\) will be \(\pm 1\). This implies that there is no need to compute any multiplication: the problem reduces to locating the nonzero entries in \(\smash [t]{\tilde{P}(x)}\) and tracking sign changes. The original P(x) can be recovered as \(\smash [t]{P(x)=(-i)^{n_Y\text { mod }4}\tilde{P}(x)}\).

We will now present an iterative procedure to compute \(\tilde{P}\) by finding for each row j the nonzero column number k(j) and its corresponding value \(\smash [t]{\tilde{P}_{j,k(j)}}\). For the first row, \(j=0\), the nonzero element \(\smash [t]{\tilde{P}_{0,k(0)}}\), can be found atwhere \([\,\cdot \,]_{10}\) is the decimal representation of a bit string and \(y(x_i)\) tracks the diagonality of \(\sigma _{x_i}\), where \(y(x_i)\) is equal to 0 if \(x_i=\{0,3\}\) (thus \(\sigma _{x_i}\in \{I,Z\}\)) and 1 otherwise (thus \(\sigma _{x_i}\in \{X,Y\}\)). The value of this entry isThe following entries can be computed iteratively. At the end of stage l, with \(l=0, \cdots , n-1\), all nonzero elements in the first \(2^{l+1}\) rows of \(\smash [t]{P_{j,k(j)}}\) will have been computed using the information given by the substring \(x_l \dots x_0\). At the next step, \(l+1\), the following \(2^l\) rows are filled using the ones that had already been computed, where the row–column relation k(j) is given byThe second term of the RHS of this relation takes into account the way that the blocks of zeros returned at stage l affect the new relative location of the nonzero blocks within the new \(2^{l+1}\times 2^{l+1}\) subcomposition. Its corresponding values are obtained from the previous ones, up to a possible change of sign given bywith \(\epsilon _l\) equal to 1 if \(x_l\in \{0,1\}\) and \(-1\) otherwise. This \(\epsilon _l\) is nothing but a parameter that takes into account if \(\sigma _{x_l}\) introduces a sign flip. In Algorithm 1 a pseudocode that summarizes the presented algorithm using (2)-(5), is shown.

For the particular case of diagonal Pauli strings (only I and Z matrices), there is no need to compute the row–column relation k(j), just the sign assignment is enough. Even if this is also the case for anti-diagonal matrices, we focus on the diagonal case due to its relevance in combinatorial problems [24‐27]. See Algorithm 2 for the pseudocode of this case (PDC stands for PauliDiagonalComposer).

The PC algorithm is able to circumvent the calculation of a significant amount of operations. When generic Kronecker product routines (see Appendix 2) are used for the same task, the amount of multiplications needed for computing a Pauli string is \(\mathcal {O}[n2^{2n}]\) and \(\mathcal {O}[n2^n]\) for dense and sparse matrices, respectively. In contrast, the PC algorithm, considering the worst-case scenarios, needsIn all cases, our algorithm can significantly outperform those that are not specifically designed for Pauli matrices.

On top of that, this method is also advantageous for computing weighted Pauli strings. Following (3), \(W:=\omega P\), with arbitrary \(\omega \), can be computed by defining \(W_{0, k(0)}= \omega (-i)^{n_Y\text { mod }4}\) which avoids having to do any extra multiplication. This change is reflected in Algorithm 1 by changing line 6 to \(m(0)\leftarrow \omega (-i)^{n_Y\text { mod }4}\) and line 4 to \(m(0)\leftarrow \omega \) in Algorithm 2. This is specially important as it can be used to compute Hamiltonians written as a weighted sum of Pauli strings, where \(H=\sum _x \omega _xP(x)\).

In this section, we analyze the improvement that the PC strategy introduces against other known algorithms labeled as Naive (regular Kronecker product), Algorithm 993 (Alg993) [28], Mixed and Tree [29, 30]. Further details can be found in Appendix 2. We benchmark these algorithms using MATLAB [31] as it is proficient at operating with matrices (it incorporates optimized routines of the well-known BLAS and LAPACK libraries [32, 33]). The PC avoids matrix operations, and thus, it would not be ideal to implement it using MATLAB. Instead, we use Python [34] since many quantum computing libraries are written in this language [19‐22]. See Table 1 for a full description of the computational resources used.

Concerning memory needs, with this algorithm only \(2^n\) nonzero elements out of \(2^{2n}\) are stored. This is exactly the same as using sparse matrices, thus, no major improvement is to be expected. As for the computational time, we compare how different algorithms behave as the length n of the Pauli string increases. In Fig. 1 execution times for general and diagonal Pauli strings are shown. For the PC methods, we use the PC routine (Algorithm 1) for the general case and the PDC routine (Algorithm 2) for the diagonal one. In accordance to our theoretical analysis, the PC algorithm proves to be the best performing routine.

On a more technical note, when using the PC routine, matrices with complex values (\(n_Y\) odd) take twice as much time as real-valued ones (\(n_Y\) even). Consequently, we compute their execution times separately and then average them. Moreover, it is convenient to choose when to use PC or PDC as the latter can be up to 10 times faster.

The PC algorithm can be used to perform useful calculations in physics. In this section, the Pauli basis decomposition of a Hamiltonian and the construction of a Hamiltonian as a sum of weighted Pauli strings are discussed in detail. Another worth mentioning scenario is the digital implementation of the complex exponential of a Pauli string, i.e., \(e^{-i \theta P(x)}=\cos (\theta )I -i \sin (\theta )P(x)\).

Pauli basis decomposition of a Hamiltonian.—The decomposition of a Hamiltonian written as a \(2^n\times 2^n\) matrix into the Pauli basis is a common problem in quantum computing. Given a general Hamiltonian H, this decomposition can be written as \(H=\sum _x \omega _x P(x)\) with \(x = x_{n-1}\dots x_0\) and P(x) as in (1). The coefficients \(\omega _x\) are obtained from the orthogonal projection asFollowing the discussion in Sect. 2, the double sum collapses to a single one in (6) since there is only one nonzero element per row and column. Each of these weights can be computed independently, which allows for a parallel implementation. Additionally, in some special cases, it can be known in advance if some \(\omega _x\) will vanish:

The operations made by PauliDecomposer (PD) areThis PD algorithm checks if the input matrix satisfies one of the aforementioned cases and computes the coefficients using the PC routine and (6), discarding all vanishing Pauli strings. This workflow considerably enhances our results, especially for diagonal matrices.

In Table 2 and Fig. 2, we tested the most extended methods for decomposing matrices into weighted sums of Pauli strings against PD, using Python [34] to compare their performance. In particular, we used the SparsePauliOp class from Qiskit [19] and the decompose_hamiltonian function from PennyLane [20] (only works with hermitian Hamiltonians). To the best of authors’ knowledge, both routines are based on Naive approach without inspecting the input matrix nature before proceeding.

Four types of random \(2^n\times 2^n\) matrices were generated, namely non-hermitian \(H_\text {NH}\), hermitian \(H_\text {H}\), symmetric \(H_\text {S}\) and diagonal \(H_\text {D}\) matrices. The PD vastly outperforms Qiskit and PennyLane routines, specially for the symmetric and diagonal cases.

Building of a Hamiltonian as a sum of weighted Pauli strings.—Many Hamiltonians are written in terms of weighted Pauli strings. Our method can compute weighted Pauli strings directly without extra computations. In Fig. 3, we show a performance comparison of the presented methods for computing Hamiltonians written as sums of weighted Pauli strings. The Hamiltonian used is similar to the one proposed in [27],being the corresponding weights \(\mathbf {\alpha }\) and \(\mathbf {\beta }\) arbitrary and \(\sigma ^i_3\) as defined in (B2). This Hamiltonian is computed using Algorithm 3, which uses the PDC routine (see Algorithm 2) with two inputs: the string \(x\in \{0,3\}^n\) to compute and the weights to consider. In the PDC case, we use two strategies: compute each weighted term of (7) directly and compute each Pauli string and then multiply it by its corresponding weight (solid and dashed lines in Fig. 3, respectively). This is done by changing lines 6 to \(H\leftarrow H+\alpha _i\texttt {PDC(}str_1\texttt {)}\) and 10 to \(H\leftarrow H+\beta _{ij}{} \texttt {PDC(}str_2\texttt {)}\) in Algorithm 3 for the second one. There is no significant difference between both methods.

The fast and reliable computation of tensor products of Pauli matrices is crucial in the field of quantum mechanics and, in particular, of quantum computing. In this article, we propose a novel algorithm with proven theoretical and experimental enhancements over similar methods of this key yet computationally tedious task. This is achieved by taking advantage of the properties of Pauli matrices and the tensor product definition, which implies that one can avoid trivial operations such as multiplying constants by one and waste time computing elements with value zero that could be known in advance.

Concerning memory resources, it is convenient to store the obtained results as sparse matrices since only \(2^n\) out of \(2^{2n}\) entries will not be zero for a Pauli string of length n, i.e., the density of the resultant matrix will be \(2^{-n}\) (see Appendix 1).

Our benchmark tests suggest that the PauliComposer algorithm and its variants can achieve a remarkable acceleration when compared to the most well-known methods for the same purpose both for single Pauli strings and real use cases. In particular, the most considerable outperformance can be seen in Table 2 for the symmetric and diagonal matrix decomposition over the Pauli basis.

Finally, its simple implementation (Algorithm 1-2) can potentially allow to integrate the PC routines into quantum simulation packages to enhance inner calculations.