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) - 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) - Robust 1-bit Compressive Sensing with Partial Gaussian Circulant
Matrices and Generative Priors [54.936314353063494]
We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing.
We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
arXiv Detail & Related papers (2021-08-08T05:28:06Z) - 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.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.