Related papers: Pauli Decomposition via the Fast Walsh-Hadamard Transform

Pauli Decomposition via the Fast Walsh-Hadamard Transform

URL: http://arxiv.org/abs/2408.06206v2
Date: Mon, 30 Sep 2024 12:39:24 GMT
Title: Pauli Decomposition via the Fast Walsh-Hadamard Transform
Authors: Timothy N. Georges, Bjorn K. Berntson, Christoph Sünderhauf, Aleksei V. Ivanov,
Abstract summary: We present a new exact and explicit formula for the Pauli string coefficients. 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. A numerical implementation of our equation outperforms currently available solutions.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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.

Related papers

Pauli Transfer Matrices [0.0]
Pauli transfer matrices show the action of a linear map in the $n$-qubit Pauli basis. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis.
arXiv Detail & Related papers (2024-11-01T11:52:51Z)
A tree-approach Pauli decomposition algorithm with application to quantum computing [0.0]
We propose an algorithm with a parallel implementation that optimize this decomposition using a tree approach. We also explain how some particular matrix structures can be exploited to reduce the number of operations.
arXiv Detail & Related papers (2024-03-18T10:38:06Z)
Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it. Each row of the matrix is encoded as a pure state of some quantum system. The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z)
Decomposing dense matrices into dense Pauli tensors [0.0]
We derive a fixed-memory, branchless algorithm to compute the inner product between a 2N-by-2N complex matrix and an N-term Pauli tensor in O(2N) time. Our scheme permits the embarrassingly parallel decomposition of a matrix into a weighted sum of Pauli strings in O(8N) time.
arXiv Detail & Related papers (2024-01-29T18:18:11Z)
Tridiagonal matrix decomposition for Hamiltonian simulation on a quantum computer [0.0]
This work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis. It allows one to construct a Hamiltonian evolution circuit without the use of oracles.
arXiv Detail & Related papers (2023-09-29T20:27:05Z)
Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z)
Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z)
A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
arXiv Detail & Related papers (2021-12-05T15:42:32Z)
Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
arXiv Detail & Related papers (2021-06-16T04:07:48Z)
Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z)
Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
arXiv Detail & Related papers (2020-02-23T03:07:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.