Decomposition Algorithm of an Arbitrary Pauli Exponential through a Quantum Circuit

Maximilian Balthasar Mansky, Victor Ramos Puigvert, Santiago Londoño Castillo, Claudia Linnhoff‐Popien

Abstract

We review the staircase algorithm to decompose the exponential of a generalized Pauli matrix and propose two alternative recursive methods offering more efficient quantum circuits. The inverted staircase algorithm improves one-qubit gate counts by $n/2$. The second method introduces fermionic SWAP (fSWAP) gates, which simplify CNOT gate counts by approximately $n/2$ for large systems. We also discuss how interference effects prevent the simple substitution of fermionic gates for non-fermionic ones without altering circuit outcomes.

The Challenge of NISQ-Era Simulations

In quantum computing, simulating physical systems requires calculating the exponential of a Hamiltonian, $e^{-iHt}$. These Hamiltonians are typically represented as sums of Pauli strings (combinations of $X, Y, Z$, and $I$ operators). Converting these mathematical expressions into executable quantum circuits is a foundational task.

The traditional approach is the staircase algorithm, which uses a sequence of CNOT gates to compute the parity of the involved qubits, followed by a central rotation and a mirrored set of CNOTs to uncompute the parity. However, in the Noisy Intermediate-Scale Quantum (NISQ) era, every gate introduces noise. Reducing the gate count is essential for maintaining fidelity.

Proposed Algorithmic Improvements

1. The Inverted Staircase Algorithm

The standard staircase algorithm often requires many single-qubit basis-change gates (like Hadamards or $Y$-rotations) to align the Pauli string with the $Z$-axis for rotation.

Comparison of staircase circuit implementations. (a) represents a standard staircase approach for $Z$-type strings, while (b) shows the additional basis transformations required for other Pauli operators.

The proposed inverted staircase algorithm uses an $R_x$ rotation and "inverted" CNOT gates. By applying a "Rule of Majority"—choosing between the standard and inverted versions based on whether the Pauli string contains more $Z$ operators or more $X/Y$ operators—researchers can eliminate a significant number of these basis-change gates. This leads to a polynomial improvement of $n/2$ in the number of one-qubit gates.

2. Fermionic SWAP (fSWAP) Networks

The second major contribution is the systematic use of fermionic SWAP gates. Unlike standard SWAP gates, an fSWAP introduces a phase shift (a minus sign) when exchanging two occupied states, reflecting the antisymmetric nature of fermions.

Definition and decomposition of the fermionic SWAP gate, denoted by the tilde symbol.

By using these gates to move information across the circuit, the algorithm can bypass the long chains of CNOTs required to link distant qubits in a standard staircase. This reduces the CNOT gate count by roughly $n/2$ for large qubit counts.

Key Insights and Results

  • Efficiency Gains: The inverted staircase reduces single-qubit gates from $3n/2$ to $n$. CNOT counts are similarly reduced via fSWAP networks.
  • The Interference Trap: The authors demonstrate that fermionic gates are not merely a mathematical convenience. Due to interference effects in complex circuits, substituting fSWAPs for standard SWAPs without careful consideration will alter the final probability outcomes of the circuit.
  • Hybrid Optimization: For complex Hamiltonians (e.g., $XX + YY + ZZ$), a hybrid approach that selects the optimal decomposition for each term yields the most efficient overall circuit.

Conclusion

These algorithms provide a practical path toward more efficient quantum simulations on current hardware. While the reliance on fSWAPs may require hardware-specific native gate support to be fully realized, the theoretical reductions in both single-qubit and CNOT gates represent a significant step forward for NISQ-era algorithm design.

Summary updated

Abstract

We review the staircase algorithm to decompose the exponential of a generalized Pauli matrix and we propose two alternative recursive methods which offer more efficient quantum circuits. The first algorithm we propose, defined as the inverted staircase algorithm, is more efficient in comparison to the standard staircase algorithm in the number of one-qubit gates, giving a polynomial improvement of n/2. For our second algorithm, we introduce fermionic SWAP quantum gates and a systematic way of generalizing these. Such fermionic gates offer a simplification of the number of quantum gates, in particular of CNOT gates, in most quantum circuits. Regarding the staircase algorithm, fermionic quantum gates reduce the number of CNOT gates in roughly n/2 for a large number of qubits. In the end, we discuss the difference between the probability outcomes of fermionic and non-fermionic gates and show that, in general, due to interference, one cannot substitute fermionic gates through non-fermionic gates without altering the outcome of the circuit.
BibTeX
@inproceedings{mansky2023decomposition,
  author = {Maximilian Balthasar Mansky and Victor Ramos Puigvert and Santiago Londoño Castillo and Claudia Linnhoff‐Popien},
  title = {{Decomposition Algorithm of an Arbitrary Pauli Exponential through a Quantum Circuit}},
  booktitle = {QCE},
  year = {2023},
  doi = {10.1109/qce57702.2023.00056},
}
Figure