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.01733

Pauli-structured preconditioning for quantum linear system solvers

Hantao Nie, Zhijian Lai, Dong An

quant-phmath-phmath.NASubmitted Jun 1, 2026• Announced Jun 2, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
15 pages

Related papers

Preconditioned block encodings for quantum linear systems

Leigh B. Lapworth, Christoph Sünderhauf

Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.

arXiv:2502.20908•Quantum Science and Technology•Oct 3, 2025•1 citation

Quantum Domain Decomposition for Preconditioning the Finite Element Method

Elise Fressart, Michel Nowak, Nicole Spillane

Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system $A x = b$ by premultiplying it by a matrix $H$ in such a way that the condition number of $HA$ is significantly smaller than the condition number of $A$. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.

math.NACross-listedarXiv:2605.26090•May 26, 2026•0 citations

Preconditioning for a Variational Quantum Linear Solver

Aruto Hosaka, Koichi Yanagisawa, Shota Koshikawa +3 more

We apply preconditioning, which is widely used in classical solvers for linear systems $A\textbf{x}=\textbf{b}$, to the variational quantum linear solver. By utilizing incomplete LU factorization as a preconditioner for linear equations formed by $128\times128$ random sparse matrices, we numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. This reduction in circuit depth is crucial to improving the efficiency and accuracy of Noisy Intermediate-Scale Quantum (NISQ) algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.

arXiv:2312.15657•Dec 25, 2023•4 citations

On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

Davide Orsucci, Vedran Dunjko

Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is κ , the condition number of the coefficient matrix A , as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in κ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as κ , a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in κ also when A is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in κ : the first is based on efficiently implementing a matrix-block-encoding of A−1 , the second constructs a decomposition of the form A=LL† to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.

arXiv:2101.11868•Quantum•Nov 8, 2021•17 citations

Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schrödingerization

Shi Jin, Nana Liu, Chuwen Ma +1 more

We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix $A_S = S^\top A S$, where $A$ is the stiffness matrix and $S$ encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of $A_S$ with normalization $\mathcal{O}(d^2(L+1))$, where $d$ is the spatial dimension and $L$ is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of $\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)$ for estimating linear functionals of the solution to a given tolerance $\varepsilon$.

arXiv:2505.06866•May 11, 2025•0 citations

Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

Samson Wang, Sam McArdle, Mario Berta

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N × N Hermitian matrices, the space cost is log  ( N ) + 1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O ( N 2 ) , when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems. Published by the American Physical Society 2024

PRX Quantum•Apr 30, 2024•20 citations
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.
Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.
Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system Ax=bA x = bAx=b by premultiplying it by a matrix HHH in such a way that the condition number of HAHAHA is significantly smaller than the condition number of AAA. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.
We apply preconditioning, which is widely used in classical solvers for linear systems Ax=bA\textbf{x}=\textbf{b}Ax=b, to the variational quantum linear solver. By utilizing incomplete LU factorization as a preconditioner for linear equations formed by 128×128128\times128128×128 random sparse matrices, we numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. This reduction in circuit depth is crucial to improving the efficiency and accuracy of Noisy Intermediate-Scale Quantum (NISQ) algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.
Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is κ , the condition number of the coefficient matrix A , as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in κ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as κ , a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in κ also when A is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in κ : the first is based on efficiently implementing a matrix-block-encoding of A−1 , the second constructs a decomposition of the form A=LL† to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.
We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix AS=S⊤ASA_S = S^\top A SAS​=S⊤AS, where AAA is the stiffness matrix and SSS encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of ASA_SAS​ with normalization O(d2(L+1))\mathcal{O}(d^2(L+1))O(d2(L+1)), where ddd is the spatial dimension and LLL is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of O(poly(d)ε−1polylog(ε−1))\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)O(poly(d)ε−1polylog(ε−1)) for estimating linear functionals of the solution to a given tolerance ε\varepsilonε.
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N × N Hermitian matrices, the space cost is log  ( N ) + 1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O ( N 2 ) , when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems. Published by the American Physical Society 2024