Decomposing dense matrices into dense Pauli tensors
- URL: http://arxiv.org/abs/2401.16378v2
- Date: Tue, 30 Jan 2024 13:12:08 GMT
- Title: Decomposing dense matrices into dense Pauli tensors
- Authors: Tyson Jones
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decomposing a matrix into a weighted sum of Pauli strings is a common chore
of the quantum computer scientist, whom is not easily discouraged by
exponential scaling. But beware, a naive decomposition can be cubically more
expensive than necessary! In this manuscript, we derive a fixed-memory,
branchless algorithm to compute the inner product between a 2^N-by-2^N complex
matrix and an N-term Pauli tensor in O(2^N) time, by leveraging the Gray code.
Our scheme permits the embarrassingly parallel decomposition of a matrix into a
weighted sum of Pauli strings in O(8^N) time. We implement our algorithm in
Python, hosted open-source on Github, and benchmark against a recent
state-of-the-art method called the "PauliComposer" which has an exponentially
growing memory overhead, achieving speedups in the range of 1.5x to 5x for N <
8. Note that our scheme does not leverage sparsity, diagonality, Hermitivity or
other properties of the input matrix which might otherwise enable optimised
treatment in other methods. As such, our algorithm is well-suited to
decomposition of dense, arbitrary, complex matrices which are expected dense in
the Pauli basis, or for which the decomposed Pauli tensors are a priori
unknown.
Related papers
- 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) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix.
This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup.
We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
arXiv Detail & Related papers (2023-11-07T22:52:56Z) - 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) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions.
Our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures.
arXiv Detail & Related papers (2023-02-03T17:22:49Z) - PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently [0.0]
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.
As a side product, we provide an optimized method for one key calculus in quantum simulations: the Pauli basis decomposition of Hamiltonians.
arXiv Detail & Related papers (2023-01-02T08:48:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root.
For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA)
A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
arXiv Detail & Related papers (2022-01-29T10:00:35Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
We propose two more efficient variants to compute the differentiable matrix square root.
For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP)
The other method is to use Matrix Pad'e Approximants (MPA)
arXiv Detail & Related papers (2022-01-21T12:18:06Z) - 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)
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.