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:2508.04689 · Physical Review Applied

Probabilistic quantum algorithm for Lyapunov equations and matrix inversion

Marcello Benedetti, Ansis Rosmanis, Matthias Rosenkranz

Published Mar 9, 2026• 3 citations
arXivHTMLPDF

Abstract

We present a probabilistic quantum algorithm for preparing mixed states which, in expectation, are proportional to the solutions of Lyapunov equations—linear matrix equations ubiquitous in the analysis of classical and quantum dynamical systems. Building on previous results by Zhang , , at each step the algorithm can (i) return the current state, (ii) apply a trace nonincreasing completely positive map, or (iii) restart. We introduce a deterministic stopping rule, which leads to an efficient algorithm with a bounded expected number of calls to oracles representing the two input matrices of the Lyapunov equations. We also consider preparing a mixed state that approximates the normalized inverse of a positive definite matrix A . In its most general form, the algorithm generates mixed states, which approximate matrix-valued weighted sums and integrals. It can be shown that block encodings and states yield two incomparable computational resources even when they represent the same piece of data. While block encodings of functions have received much attention in the literature, our work takes a step toward the less explored problem of encoding functions into mixed states.

DOI
10.1103/mprk-9vx3

Related papers

Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

Yanqiao Wang, Jin-Peng Liu

We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix $M$ is chosen so that the target operator is a block of $\text{sign}(M)$ or is recovered from blocks of $(I-\text{sign}(M))/2$. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.

quant-pharXiv:2604.25333•Apr 29, 2026•10 citations

Efficient Quantum Algorithm for Mixed-State Quantum Geometry

Chenyang Wang, Qi Zhao, Xiao Yuan +1 more

Mixed-state quantum geometry plays a fundamental role in quantum metrology, multiparameter estimation, and the characterization of quantum many-body systems. Yet, unlike its pure-state counterpart, accessing mixed-state geometry requires solving an ill-conditioned Lyapunov equation for the symmetric logarithmic derivative (SLD), posing a major challenge for resource-efficient quantum computation. Here we address the challenge and develop a novel quantum algorithmic framework for efficiently accessing the quantum Fisher information matrix (QFIM) and quantum geometric tensor (QGT) of mixed states. Our key insight is to uncover a previously unexplored connection between the positive semidefinite structure of density matrices and exponentially convergent Gauss-Laguerre quadrature, enabling an efficient integral-based construction of the SLD. A rigorous complexity analysis further establishes the resource efficiency of our algorithm, demonstrating logarithmic precision dependence and double-logarithmic ancillary-qubit overhead at fixed conditioning. Building on this construction, we achieve near-Heisenberg precision scaling for diagonal QFI estimation without quantum phase estimation and construct unified block encodings of the full QFIM and QGT under a bounded spectral-gap assumption. A complementary regularized algorithm extends efficient diagonal estimation to exponentially small spectral gaps under a bounded-response condition. Our results establish a resource-efficient route to coherent mixed-state quantum geometry, enabling its direct integration into quantum linear-algebra algorithms without classical reconstruction and opening new possibilities for quantum-enhanced multiparameter metrology.

quant-pharXiv:2610.24686•Oct 20, 2026•0 citations

Quantum algorithms for matrix operations and linear systems of equations

Wentao Qi, Alexander Ivanovich Zenchuk, Asutosh Kumar +1 more

Abstract Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations. Using the ‘sender-receiver’ model, we propose quantum algorithms for matrix operations such as matrix-vector product, matrix-matrix product, the sum of two matrices, and the calculation of determinant and inverse matrix. We encode the matrix entries into the probability amplitudes of the pure initial states of senders. After applying proper unitary transformation to the complete quantum system, the desired result can be found in certain blocks of the receiver’s density matrix. These quantum protocols can be used as subroutines in other quantum schemes. Furthermore, we present an alternative quantum algorithm for solving linear systems of equations.

arXiv:2202.04888•Communications in Theoretical Physics•Jan 29, 2024•15 citations

Schrödingerization for quantum linear systems problems with near-optimal dependence on matrix queries

Yin Ping Yang, Yue Yu, Long Zhang

We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.

arXiv:2508.13510•Aug 19, 2025•3 citations

Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals

Souichi Takahira, A. Ohashi, Tomohiro Sogabe +1 more

he matrix functions can be defined by Cauchy's integral formula and can be approximated by the linear combination of inverses of shifted matrices using a quadrature formula. In this paper, we propose a quantum algorithm for matrix functions based on a procedure to implement the linear combination of the inverses on quantum computers. Compared with the previous study [S. Takahira, A. Ohashi, T. Sogabe, and T.S. Usuda, Quant. Inf. Comput., \textbf{20}, 1\&2, 14--36, (Feb. 2020)] that proposed a quantum algorithm to compute a quantum state for the matrix function based on the circular contour centered at the origin, the quantum algorithm in the present paper can be applied to a more general contour. Moreover, the algorithm is described by the block-encoding framework. Similarly to the previous study, the algorithm can be applied even if the input matrix is not a Hermitian or normal matrix. This is an advantage compared with quantum singular value transformation.

arXiv:2106.08076•Quantum Information and Computation•Aug 1, 2022•25 citations

Multivariate Quantum Signal Processing

Guang Hao Low

We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under $H=\sum_j H_j$ with weighted quasinorm cost $\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))$ for block-encoding normalizations $\vecλ$ and costs $\vec C$; (2) sparse simulation with optimal time--norm $Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)$ and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost $t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}$ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.

quant-pharXiv:2610.01125•Oct 2, 2026•2 citations
We present a probabilistic quantum algorithm for preparing mixed states which, in expectation, are proportional to the solutions of Lyapunov equations—linear matrix equations ubiquitous in the analysis of classical and quantum dynamical systems. Building on previous results by Zhang , , at each step the algorithm can (i) return the current state, (ii) apply a trace nonincreasing completely positive map, or (iii) restart. We introduce a deterministic stopping rule, which leads to an efficient algorithm with a bounded expected number of calls to oracles representing the two input matrices of the Lyapunov equations. We also consider preparing a mixed state that approximates the normalized inverse of a positive definite matrix A . In its most general form, the algorithm generates mixed states, which approximate matrix-valued weighted sums and integrals. It can be shown that block encodings and states yield two incomparable computational resources even when they represent the same piece of data. While block encodings of functions have received much attention in the literature, our work takes a step toward the less explored problem of encoding functions into mixed states.
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix MMM is chosen so that the target operator is a block of sign(M)\text{sign}(M)sign(M) or is recovered from blocks of (I−sign(M))/2(I-\text{sign}(M))/2(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.
Mixed-state quantum geometry plays a fundamental role in quantum metrology, multiparameter estimation, and the characterization of quantum many-body systems. Yet, unlike its pure-state counterpart, accessing mixed-state geometry requires solving an ill-conditioned Lyapunov equation for the symmetric logarithmic derivative (SLD), posing a major challenge for resource-efficient quantum computation. Here we address the challenge and develop a novel quantum algorithmic framework for efficiently accessing the quantum Fisher information matrix (QFIM) and quantum geometric tensor (QGT) of mixed states. Our key insight is to uncover a previously unexplored connection between the positive semidefinite structure of density matrices and exponentially convergent Gauss-Laguerre quadrature, enabling an efficient integral-based construction of the SLD. A rigorous complexity analysis further establishes the resource efficiency of our algorithm, demonstrating logarithmic precision dependence and double-logarithmic ancillary-qubit overhead at fixed conditioning. Building on this construction, we achieve near-Heisenberg precision scaling for diagonal QFI estimation without quantum phase estimation and construct unified block encodings of the full QFIM and QGT under a bounded spectral-gap assumption. A complementary regularized algorithm extends efficient diagonal estimation to exponentially small spectral gaps under a bounded-response condition. Our results establish a resource-efficient route to coherent mixed-state quantum geometry, enabling its direct integration into quantum linear-algebra algorithms without classical reconstruction and opening new possibilities for quantum-enhanced multiparameter metrology.
Abstract Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations. Using the ‘sender-receiver’ model, we propose quantum algorithms for matrix operations such as matrix-vector product, matrix-matrix product, the sum of two matrices, and the calculation of determinant and inverse matrix. We encode the matrix entries into the probability amplitudes of the pure initial states of senders. After applying proper unitary transformation to the complete quantum system, the desired result can be found in certain blocks of the receiver’s density matrix. These quantum protocols can be used as subroutines in other quantum schemes. Furthermore, we present an alternative quantum algorithm for solving linear systems of equations.
We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.
he matrix functions can be defined by Cauchy's integral formula and can be approximated by the linear combination of inverses of shifted matrices using a quadrature formula. In this paper, we propose a quantum algorithm for matrix functions based on a procedure to implement the linear combination of the inverses on quantum computers. Compared with the previous study [S. Takahira, A. Ohashi, T. Sogabe, and T.S. Usuda, Quant. Inf. Comput., \textbf{20}, 1\&2, 14--36, (Feb. 2020)] that proposed a quantum algorithm to compute a quantum state for the matrix function based on the circular contour centered at the origin, the quantum algorithm in the present paper can be applied to a more general contour. Moreover, the algorithm is described by the block-encoding framework. Similarly to the previous study, the algorithm can be applied even if the input matrix is not a Hermitian or normal matrix. This is an advantage compared with quantum singular value transformation.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHjH=\sum_j H_jH=∑j​Hj​ with weighted quasinorm cost ≈t⟨λ⃗,C⃗⟩1/2+O(∥C⃗∥1log⁡(1/ε))\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))≈t⟨λ,C⟩1/2​+O(∥C∥1​log(1/ε)) for block-encoding normalizations λ⃗\vecλλ and costs C⃗\vec CC; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t)Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)Θ(d​∥H∥1→2​t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λ⃗eff,C⃗eff⟩1/2t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}t⟨λeff​,Ceff​⟩1/2​ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.