Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.11478 · Computer Methods in Applied Mechanics and Engineering

PHASE: Pauli Hierarchical Assembly on Subdivided Elements for Quantum-Compatible Operator Synthesis

Tillman Philo, Caglar Oskay

quant-phmath.NASubmitted Jun 9, 2026• Announced Jun 11, 2026• 1 citation
arXivHTMLPDF

Abstract

Efficiently decomposing finite element stiffness matrices into the Pauli basis is challenging due to the exponential growth of Pauli strings with problem size. A naive Pauli expansion requires $Θ(8^{\lceil \log_2 N \rceil})$ operations, where $N$ denotes the number of degrees of freedom, rendering direct decomposition infeasible for large systems. Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the geometric organization intrinsic to finite element discretizations, and consequently exhibit poor scaling for stiffness matrices. To address this problem, we introduce PHASE, a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales. PHASE employs a hybrid strategy that combines full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation to assemble global Pauli coefficients efficiently. We show that this approach yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity relative to existing methods, reducing the cost from $2^{2{\lceil \log_2 N \rceil}}$ to $2^{γ_d{\lceil \log_2 N \rceil}}$ with $γ_d < 2$ under standard mesh regularity and balanced partition assumptions. These results substantially improve the feasibility of quantum-compatible operator synthesis for large-scale finite element models.

Related papers

An efficient Pauli decomposition algorithm for structured matrices

Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

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.

quant-pharXiv:2606.31952•Jul 1, 2026•0 citations

Efficient Pauli Operator Generation via Hierarchical Matrix Compression for Quantum-Ready Electromagnetic Solvers

Noora Al-Sultani, Su Yan

Quantum linear solvers require expressing the system matrix as a sum of Pauli operators, a process whose computational cost scales exponentially with problem size. For electromagnetic integral equations discretized by the method of moments (MoM), the resulting dense impedance matrices pose a significant challenge for quantum operator generation. This paper demonstrates that hierarchical matrix$(\mathcal{H}$-matrix) compression provides an effective mechanism for reducing Pauli operator complexity. By restricting Pauli decomposition to low-rank far-field blocks identified through$\mathcal{H}$-matrix partitioning, the number of significant Pauli terms is reduced by over 95% compared to full-matrix decomposition, while maintaining approximation accuracy on the order of 10−5in relative Frobenius norm. Numerical experiments on a spherical scatterer confirm that the proposed block-wise approach offers a practical pathway toward quantum-compatible formulations of large-scale electromagnetic problems.

Digest - IEEE Antennas and Propagation Society. International Symposium•Jul 1, 2026•0 citations

Decomposing dense matrices into dense Pauli tensors

Tyson Jones

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.

arXiv:2401.16378•Jan 29, 2024•17 citations

Pauli decomposition via the fast Walsh-Hadamard transform

Timothy N. Georges, Bjorn K. Berntson, Christoph Sünderhauf +1 more

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.

arXiv:2408.06206•New Journal of Physics•Feb 10, 2025•19 citations

Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori +1 more

Pauli decomposition of an $n$-qubit operator is expensive if each of the $4^n$ Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space $(\mathbb{Z}_2)^n$ makes them displacement operators $X^{\otimes x}Z^{\otimes z}$ on the computational space: shifts by~$x$ and multiplications by characters $Z^{\otimes z}$ in the computational basis. That labeling organizes the operator into $2^n$ fibers of length $2^n$, one per shift~$x$, each collecting the computational-basis amplitudes that hop by~$x$. Expanding each fiber function in the character basis of $(\mathbb{Z}_2)^n$ --- a length-$2^n$ Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost $O(n\cdot4^n)$. The same fiber / shift--character picture extends to $(\mathbb{Z}_p)^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 $2^n\times2^n$ operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.

quant-pharXiv:2610.08299•Oct 7, 2026•0 citations

Efficient quantum access model for sparse structured matrices using linear combination of “things”

Abeynaya Gnanasekaran, Amit Surana

We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.

arXiv:2507.03714•Physical Review A•Jan 16, 2026•5 citations
Efficiently decomposing finite element stiffness matrices into the Pauli basis is challenging due to the exponential growth of Pauli strings with problem size. A naive Pauli expansion requires Θ(8⌈log⁡2N⌉)Θ(8^{\lceil \log_2 N \rceil})Θ(8⌈log2​N⌉) operations, where NNN denotes the number of degrees of freedom, rendering direct decomposition infeasible for large systems. Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the geometric organization intrinsic to finite element discretizations, and consequently exhibit poor scaling for stiffness matrices. To address this problem, we introduce PHASE, a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales. PHASE employs a hybrid strategy that combines full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation to assemble global Pauli coefficients efficiently. We show that this approach yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity relative to existing methods, reducing the cost from 22⌈log⁡2N⌉2^{2{\lceil \log_2 N \rceil}}22⌈log2​N⌉ to 2γd⌈log⁡2N⌉2^{γ_d{\lceil \log_2 N \rceil}}2γd​⌈log2​N⌉ with γd<2γ_d < 2γd​<2 under standard mesh regularity and balanced partition assumptions. These results substantially improve the feasibility of quantum-compatible operator synthesis for large-scale finite element models.
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)k = \mathsf{poly}(n)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 nnn. 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−δ1 - δ1−δ, for any δδδ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in nnn, kkk, and log⁡(1/δ)\log(1/δ)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.
Quantum linear solvers require expressing the system matrix as a sum of Pauli operators, a process whose computational cost scales exponentially with problem size. For electromagnetic integral equations discretized by the method of moments (MoM), the resulting dense impedance matrices pose a significant challenge for quantum operator generation. This paper demonstrates that hierarchical matrix(H(\mathcal{H}(H-matrix) compression provides an effective mechanism for reducing Pauli operator complexity. By restricting Pauli decomposition to low-rank far-field blocks identified throughH\mathcal{H}H-matrix partitioning, the number of significant Pauli terms is reduced by over 95% compared to full-matrix decomposition, while maintaining approximation accuracy on the order of 10−5in relative Frobenius norm. Numerical experiments on a spherical scatterer confirm that the proposed block-wise approach offers a practical pathway toward quantum-compatible formulations of large-scale electromagnetic problems.
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.
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.
Pauli decomposition of an nnn-qubit operator is expensive if each of the 4n4^n4n Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space (Z2)n(\mathbb{Z}_2)^n(Z2​)n makes them displacement operators X⊗xZ⊗zX^{\otimes x}Z^{\otimes z}X⊗xZ⊗z on the computational space: shifts by~xxx and multiplications by characters Z⊗zZ^{\otimes z}Z⊗z in the computational basis. That labeling organizes the operator into 2n2^n2n fibers of length 2n2^n2n, one per shift~xxx, each collecting the computational-basis amplitudes that hop by~xxx. Expanding each fiber function in the character basis of (Z2)n(\mathbb{Z}_2)^n(Z2​)n --- a length-2n2^n2n Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost O(n⋅4n)O(n\cdot4^n)O(n⋅4n). The same fiber / shift--character picture extends to (Zp)n(\mathbb{Z}_p)^n(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×2n2^n\times2^n2n×2n operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.
We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.