© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2411.00526 · Physica Scripta

Fast generation of Pauli transfer matrices utilizing tensor product structure

Lukas Hantzko, Lennart Binkowski, Sabhyata Gupta

Published Jun 26, 2025• 4 citations

Abstract

Abstract Analysis of quantum processes, especially in the context of noise, errors, and decoherence is essential for the improvement of quantum devices. An intuitive representation of those processes modeled by quantum channels are Pauli transfer matrices. They display the action of a linear map in the n-qubit Pauli basis in a way, that is more intuitive, since Pauli strings are more tangible objects than the standard basis matrices. We set out to investigate classical algorithms that convert the various representations into Pauli transfer matrices. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis. They convert a quantum channel in a given representation (Chi or process matrix, Choi matrix, superoperator, or Kraus operators) to the corresponding Pauli transfer matrix. Moreover, the underlying principle can also be used to calculate the Pauli transfer matrix of other linear operations over n-qubit matrices such as left-, right-, and sandwich multiplication as well as forming the (anti-)commutator with a given operator. Finally, we investigate the runtime of these algorithms, derive their asymptotic scaling and demonstrate improved performance using instances with up to seven qubits.

DOI: 10.1088/1402-4896/ade8b3

Related papers

Efficiently manipulating Pauli strings with PauliArray

Maxime Dion, Tania Belabbas, Nolan Bastien

Pauli matrices and Pauli strings are widely used in quantum computing. These mathematical objects are useful to describe or manipulate the quantum state of qubits. They offer a convenient basis to express operators and observables used in different problem instances such as molecular simulation and combinatorial optimization. Therefore, it is important to have a well-rounded, versatile and efficient tool to handle a large number of Pauli strings and operators expressed in this basis. This is the objective behind the development of the PauliArray library presented in this work. This library introduces data structures to represent arrays of Pauli strings and operators as well as various methods to modify and combine them. Built using NumPy, PauliArray offers fast operations and the ability to use broadcasting to easily carry out otherwise cumbersome manipulations. Applications to the fermion-to-qubit mapping, to the estimation of expectation values and to the computation of commutators are considered to illustrate how PauliArray can simplify some relevant tasks and accomplish them faster than current libraries.

arXiv:2405.19287•May 29, 2024•0 citations

Tensorized Pauli decomposition algorithm

Lukas Hantzko, Lennart Binkowski, Sabhyata Gupta

Abstract This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm’s potential significance in the realm of quantum computing and quantum chemistry simulations.

Physica Scripta•Jul 17, 2024•27 citations

Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator

Daniel Gunlycke, Mark C. Palenik, Alex R. Emmert +1 more

Several linear algebra routines for quantum computing use a basis of tensor products of identity and Pauli operators to describe linear operators, and obtaining the coordinates for any given linear operator from its matrix representation requires a basis transformation, which for an $\mathrm N\times\mathrm N$ matrix generally involves $\mathcal O(\mathrm N^4)$ arithmetic operations. Herein, we present an efficient algorithm that for our particular basis transformation only involves $\mathcal O(\mathrm N^2\log_2\mathrm N)$ operations. Because this algorithm requires fewer than $\mathcal O(\mathrm N^3)$ operations, for large $\mathrm N$, it could be used as a preprocessing step for quantum computing algorithms for certain applications. As a demonstration, we apply our algorithm to a Hamiltonian describing a system of relativistic interacting spin-zero bosons and calculate the ground-state energy using the variational quantum eigensolver algorithm on a quantum computer.

arXiv:2011.08942•Nov 17, 2020•7 citations

An efficient Pauli decomposition algorithm for structured matrices

Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = \mathsf{poly}(n)$ Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in $n$. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least $1 - δ$, for any $δ$. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in $n$, $k$, and $\log(1/δ)$. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.

quant-pharXiv:2606.31952•Jul 1, 2026•0 citations

Tensorized Pauli decomposition algorithm

Lukas Hantzko, Lennart Binkowski, Sabhyata Gupta

This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm's potential significance in the realm of quantum computing and quantum chemistry simulations.

arXiv:2310.13421•Oct 20, 2023•0 citations

PauliComposer: compute tensor products of Pauli matrices efficiently

Sebastián V. Romero, Juan Santos-Suárez

Abstract We introduce a simple algorithm that efficiently computes tensor products of Pauli matrices. This is done by tailoring the calculations to this specific case, which allows to avoid unnecessary calculations. The strength of this strategy is benchmarked against state-of-the-art techniques, showing a remarkable acceleration. As a side product, we provide an optimized method for one key calculus in quantum simulations: the Pauli basis decomposition of Hamiltonians.

arXiv:2301.00560•Quantum Information Processing•Dec 15, 2023•13 citations

Abstract Analysis of quantum processes, especially in the context of noise, errors, and decoherence is essential for the improvement of quantum devices. An intuitive representation of those processes modeled by quantum channels are Pauli transfer matrices. They display the action of a linear map in the n-qubit Pauli basis in a way, that is more intuitive, since Pauli strings are more tangible objects than the standard basis matrices. We set out to investigate classical algorithms that convert the various representations into Pauli transfer matrices. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis. They convert a quantum channel in a given representation (Chi or process matrix, Choi matrix, superoperator, or Kraus operators) to the corresponding Pauli transfer matrix. Moreover, the underlying principle can also be used to calculate the Pauli transfer matrix of other linear operations over n-qubit matrices such as left-, right-, and sandwich multiplication as well as forming the (anti-)commutator with a given operator. Finally, we investigate the runtime of these algorithms, derive their asymptotic scaling and demonstrate improved performance using instances with up to seven qubits.

Pauli matrices and Pauli strings are widely used in quantum computing. These mathematical objects are useful to describe or manipulate the quantum state of qubits. They offer a convenient basis to express operators and observables used in different problem instances such as molecular simulation and combinatorial optimization. Therefore, it is important to have a well-rounded, versatile and efficient tool to handle a large number of Pauli strings and operators expressed in this basis. This is the objective behind the development of the PauliArray library presented in this work. This library introduces data structures to represent arrays of Pauli strings and operators as well as various methods to modify and combine them. Built using NumPy, PauliArray offers fast operations and the ability to use broadcasting to easily carry out otherwise cumbersome manipulations. Applications to the fermion-to-qubit mapping, to the estimation of expectation values and to the computation of commutators are considered to illustrate how PauliArray can simplify some relevant tasks and accomplish them faster than current libraries.

Abstract This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm’s potential significance in the realm of quantum computing and quantum chemistry simulations.

Several linear algebra routines for quantum computing use a basis of tensor products of identity and Pauli operators to describe linear operators, and obtaining the coordinates for any given linear operator from its matrix representation requires a basis transformation, which for an

\mathrm N\times\mathrm N

matrix generally involves

\mathcal O(\mathrm N^4)

arithmetic operations. Herein, we present an efficient algorithm that for our particular basis transformation only involves

\mathcal O(\mathrm N^2\log_2\mathrm N)

operations. Because this algorithm requires fewer than

\mathcal O(\mathrm N^3)

operations, for large

\mathrm N

, it could be used as a preprocessing step for quantum computing algorithms for certain applications. As a demonstration, we apply our algorithm to a Hamiltonian describing a system of relativistic interacting spin-zero bosons and calculate the ground-state energy using the variational quantum eigensolver algorithm on a quantum computer.

Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only

k = \mathsf{poly}(n)

Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in

n

. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least

1 - δ

, for any

δ

. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in

n

,

k

, and

\log(1/δ)

. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.

This paper introduces a novel general-purpose algorithm for Pauli decomposition that employs matrix slicing and addition rather than expensive matrix multiplication, significantly accelerating the decomposition of multi-qubit matrices. In a detailed complexity analysis, we show that the algorithm admits the best known worst-case scaling and more favorable runtimes for many practical examples. Numerical experiments are provided to validate the asymptotic speed-up already for small instance sizes, underscoring the algorithm's potential significance in the realm of quantum computing and quantum chemistry simulations.