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

Digest - IEEE Antennas and Propagation Society. International Symposium

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

Noora Al-Sultani, Su Yan

Published Jul 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/ap-s/usnc-ursi60190.2026.11675125

Related papers

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

Tillman Philo, Caglar Oskay

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.

quant-pharXiv:2606.11478•Computer Methods in Applied Mechanics and Engineering•Jun 11, 2026•1 citation

Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression

Kun Tang, Jun Lai

While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches.

quant-pharXiv:2602.09745•Feb 11, 2026•0 citations

Pauli-structured preconditioning for quantum linear system solvers

Hantao Nie, Zhijian Lai, Dong An

Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.

quant-pharXiv:2606.01733•Jun 2, 2026•1 citation

Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra

Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd

Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function k(x,x′) , have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast multipole method performs matrix multiplication on kernel matrices of dimension N in time almost linear in N by using the linear algebraic framework of hierarchical matrices. In light of this success, we propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. When applied to many physical kernel matrices, our method can improve the runtime of solving quantum linear systems of dimension N to O(κpolylog⁡(Nε)) , where κ and ε are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of N , exponentially improves over prior quantum linear systems algorithms in the case of dense and full-rank kernel matrices. We discuss possible applications of our methodology in solving integral equations and accelerating computations in N-body problems.

arXiv:2201.11329•Quantum•Dec 13, 2022•25 citations

Efficient and scalable wave function compression using corner hierarchical matrices

Kenneth O. Berard, Hongji Gao, Alexander Teplukhin +2 more

The exponential scaling of complete active space and full configuration interaction (CI) calculations limits the ability of quantum chemists to simulate the electronic structures of strongly correlated systems. Herein, we present corner hierarchically approximated CI (CHACI), an approach to wave function compression based on corner hierarchical matrices (CH-matrices)-a new variant of hierarchical matrices based on block-wise low-rank decomposition. By application to dodecacene, a strongly correlated molecule, we demonstrate that CH matrix compression provides superior compression compared to truncated global singular value decomposition. The compression ratio is shown to improve with increasing active space size. By comparison of several alternative schemes, we demonstrate that superior compression is achieved by (a) using a blocking approach that emphasizes the upper-left corner of the CI vector, (b) sorting the CI vector prior to compression, and (c) optimizing the rank of each block to maximize information density.

arXiv:2407.21134•The Journal of Chemical Physics•Nov 25, 2024•2 citations

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
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.
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.
While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches.
Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.
Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function k(x,x′) , have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast multipole method performs matrix multiplication on kernel matrices of dimension N in time almost linear in N by using the linear algebraic framework of hierarchical matrices. In light of this success, we propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. When applied to many physical kernel matrices, our method can improve the runtime of solving quantum linear systems of dimension N to O(κpolylog⁡(Nε)) , where κ and ε are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of N , exponentially improves over prior quantum linear systems algorithms in the case of dense and full-rank kernel matrices. We discuss possible applications of our methodology in solving integral equations and accelerating computations in N-body problems.
The exponential scaling of complete active space and full configuration interaction (CI) calculations limits the ability of quantum chemists to simulate the electronic structures of strongly correlated systems. Herein, we present corner hierarchically approximated CI (CHACI), an approach to wave function compression based on corner hierarchical matrices (CH-matrices)-a new variant of hierarchical matrices based on block-wise low-rank decomposition. By application to dodecacene, a strongly correlated molecule, we demonstrate that CH matrix compression provides superior compression compared to truncated global singular value decomposition. The compression ratio is shown to improve with increasing active space size. By comparison of several alternative schemes, we demonstrate that superior compression is achieved by (a) using a blocking approach that emphasizes the upper-left corner of the CI vector, (b) sorting the CI vector prior to compression, and (c) optimizing the rank of each block to maximize information density.
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.