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 an 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 O ( N 2 log N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.
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 an 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 O ( N 2 log N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.
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=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.
Pauli decomposition of an n-qubit operator is expensive if each of the 4n Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space (Z2)n makes them displacement operators X⊗xZ⊗z on the computational space: shifts by~x and multiplications by characters Z⊗z in the computational basis. That labeling organizes the operator into 2n fibers of length 2n, one per shift~x, each collecting the computational-basis amplitudes that hop by~x. Expanding each fiber function in the character basis of (Z2)n --- a length-2n Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost O(n⋅4n). The same fiber / shift--character picture extends to (Zp)n (Heisenberg--Weyl qudits). \texttt{paulikit} is a memory-bounded realization for qubits: for matrix-sparse inputs, peak memory need not densify to a full 2n×2n operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.
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.
The Pauli matrices are 2-by-2 matrices that are very useful in quantum computing. They can be used as elementary gates in quantum circuits but also to decompose any matrix ofC2n×2nas a linear combination of tensor products of the Pauli matrices. However, the computational cost of this decomposition is potentially very expensive since it can be exponential inn. In this paper, we propose an algorithm with a parallel implementation that optimizes this decomposition using a tree approach to avoid redundancy in the computation while using a limited memory footprint. We also explain how some particular matrix structures can be exploited to reduce the number of operations. We provide numerical experiments to evaluate the sequential and parallel performance of our decomposition algorithm and we illustrate how this algorithm can be applied to encode matrices in a quantum memory.
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.
Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.