Pauli Decomposition via the Fast Walsh-Hadamard Transform

Autor:	Georges, Timothy N., Berntson, Bjorn K., Sünderhauf, Christoph, Ivanov, Aleksei V.
Rok vydání:	2024
Předmět:	Quantum Physics Physics - Computational Physics
Druh dokumentu:	Working Paper
Popis:	The decomposition of a square matrix into a sum of Pauli strings is a classical pre-processing step required to realize many quantum algorithms. Such a decomposition requires significant computational resources for large matrices. We present a new exact and explicit formula for the Pauli string coefficients which inspires an efficient algorithm to compute them. More specifically, we show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. This allows one to use the Fast Walsh-Hadamard transform and calculate all Pauli decomposition coefficients in $\mathcal{O}(N^2\log N)$ time and using $\mathcal{O}(1)$ additional memory, for an $N\times N$ matrix. A numerical implementation of our equation outperforms currently available solutions. Comment: added more references to previous works, and one new comparison, added script to produce results to zenodo
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.06206 Zobrazit plný text záznamu View this record from Arxiv