An efficient Pauli decomposition algorithm for structured matrices

• URL: http://arxiv.org/abs/2606.31952v1
• Date: Tue, 30 Jun 2026 16:57:07 GMT
• Title: An efficient Pauli decomposition algorithm for structured matrices
• Abstract summary: We consider a promise version of a Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = mathsfpoly(n)$ Pauli strings.<n>We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability of at least $1 - $.
• Score: 0.12744523252873352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 = \mathsf{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.

Related papers

• PHASE: Pauli Hierarchical Assembly on Subdivided Elements for Quantum-Compatible Operator Synthesis [0.0]
  A naive Pauli expansion requires $(8lceil log with N rceil)$ operations, where $N$ denotes the number of degrees of freedom.<n>Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the organization intrinsic to finite element discretizations.
  arXiv  Detail & Related papers  (2026-06-09T22:13:50Z)
• Counting anticommuting Pauli pairs in linear time [5.706918315850497]
  We provide an $O(m)$ algorithm for the bounded locality regime.<n>Our algorithm is particularly useful for processing large collections of Pauli strings within the bounded locality regime.
  arXiv  Detail & Related papers  (2026-05-10T14:41:11Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Pauli Decomposition via the Fast Walsh-Hadamard Transform [0.0]
  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.<n>A numerical implementation of our equation outperforms currently available solutions.
  arXiv  Detail & Related papers  (2024-08-12T14:56:45Z)
• 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)
• 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)
• 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)
• Coherent randomized benchmarking [68.8204255655161]
  We show that superpositions of different random sequences rather than independent samples are used. We show that this leads to a uniform and simple protocol with significant advantages with respect to gates that can be benchmarked.
  arXiv  Detail & Related papers  (2020-10-26T18:00:34Z)

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.