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:2507.15537

Matrix inversion polynomials for the quantum singular value transformation

Christoph Sünderhauf, Németh, Zalán, Adnaan Walayat, Patterson, Andrew, Bjorn K. Berntson

Published Jul 21, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum matrix inversion with the quantum singular value transformation (QSVT) requires a polynomial approximation to $1/x$. Several methods from the literature construct polynomials that achieve the known degree complexity $\mathcal{O}(κ\log(κ/\varepsilon))$ with condition number $κ$ and uniform error $\varepsilon$. However, the \emph{optimal} polynomial with lowest degree for fixed error $\varepsilon$ can only be approximated numerically with the resource-intensive Remez method, leading to impractical preprocessing runtimes. Here, we derive an analytic shortcut to the optimal polynomial. Comparisons with other polynomials from the literature, based on Taylor expansion, Chebyshev iteration, and convex optimization, confirm that our result is optimal. Furthermore, for large $κ\log(κ/\varepsilon)$, our polynomial has the smallest maximum value on $[-1,1]$ of all approaches considered, leading to reduced circuit depth due to the normalization condition of QSVT. With the Python code provided, this paper will also be useful for practitioners in the field.

Related papers

Spectrally Corrected Polynomial Approximation for Quantum Singular Value Transformation

Krishnan Suresh

Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth $O(d\cdot\mathrm{polylog}(N))$, where $d$ is the polynomial degree of the $1/x$ approximation and $N$ is the size of $\bA$. Current polynomial approximation methods are over the continuous interval $[a,1]$, giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$. We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all $N$ eigenvalues are known exactly, a pure spectral polynomial $p_{S}$ can interpolate $1/x$ at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of $K$ eigenvalues of $\bA$. Given any base polynomial $p_0$, such as Remez, of degree $d_0$, a $K\times K$ linear system enforces exact interpolation of $1/x$ only at these $K$ eigenvalues without increasing $d_0$. The spectrally corrected polynomial $p_{SC}$ preserves the continuous error profile between eigenvalues and inherits the parity of $p_0$. QSVT experiments on the 1D Poisson equation demonstrate up to a $5\times$ reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to $10\%$ relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above $0.999$.

quant-pharXiv:2603.03998•Mar 5, 2026•0 citations

An Optimal Linear-combination-of-unitaries-based Quantum Linear System Solver

Sander Gribling, Iordanis Kerenidis, Dániel Szilágyi

Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).

ACM Transactions on Quantum Computing•Feb 24, 2024•3 citations

Nearly optimal polynomial approximations for the quantum singular value transform

Evan Rule

We introduce polynomial approximations of the even and odd step functions on the interval $[-1,1]$ with simple Chebyshev coefficients, making their numerical implementation straightforward. We derive rigorous error bounds and demonstrate that these polynomials are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor that grows logarithmically with the polynomial order. From these polynomials, we derive related nearly optimal polynomial approximations that can be used to perform quantum phase estimation, linear amplitude amplification, eigenvalue thresholding, and other quantum algorithms using the quantum singular value transform.

quant-pharXiv:2607.12190•Jul 15, 2026•0 citations

Improved Performance of Quantum Search via Quantum Singular Value Transformation

Zheng Zhang, Minzhong Luo

Quantum singular value transformation (QSVT) is a powerful framework that unifies many quantum algorithms, including Grover’s search, by enabling polynomial transformations of the singular values of linear operators embedded in unitary matrices. We present an improved quantum search algorithm within this framework. Instead of amplifying the target state amplitude, our method suppresses the non-target amplitude using a modified Chebyshev polynomial. This approach achieves the optimal \(\mathcal {O}(\sqrt {N}\log (1/\delta))\) query complexity while requiring lower-degree polynomials. For N = 512, our method reduces the polynomial degree from 71 to 43 compared to prior QSVT-based fixed-point search. We also demonstrate how QSVT enables exact search construction.

International Conference on Computer Information and Big Data Applications (CIBDA)•Mar 20, 2026•0 citations

Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits

Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin +1 more

We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|ψ\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle$ for all $j\in\{1,\dots,m\}$. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of $f(H)$. It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with $H$ and $|ψ\rangle$ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from $H$, $f$, and $|ψ\rangle$ without prior knowledge of the observables or explicit preparation of the target state proportional to $f(H)|ψ\rangle$. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.

quant-pharXiv:2609.40167•Oct 1, 2026•0 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940•Oct 2, 2026•0 citations
Quantum matrix inversion with the quantum singular value transformation (QSVT) requires a polynomial approximation to 1/x1/x1/x. Several methods from the literature construct polynomials that achieve the known degree complexity O(κlog⁡(κ/ε))\mathcal{O}(κ\log(κ/\varepsilon))O(κlog(κ/ε)) with condition number κκκ and uniform error ε\varepsilonε. However, the \emph{optimal} polynomial with lowest degree for fixed error ε\varepsilonε can only be approximated numerically with the resource-intensive Remez method, leading to impractical preprocessing runtimes. Here, we derive an analytic shortcut to the optimal polynomial. Comparisons with other polynomials from the literature, based on Taylor expansion, Chebyshev iteration, and convex optimization, confirm that our result is optimal. Furthermore, for large κlog⁡(κ/ε)κ\log(κ/\varepsilon)κlog(κ/ε), our polynomial has the smallest maximum value on [−1,1][-1,1][−1,1] of all approaches considered, leading to reduced circuit depth due to the normalization condition of QSVT. With the Python code provided, this paper will also be useful for practitioners in the field.
Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth O(d⋅polylog(N))O(d\cdot\mathrm{polylog}(N))O(d⋅polylog(N)), where ddd is the polynomial degree of the 1/x1/x1/x approximation and NNN is the size of $\bA$. Current polynomial approximation methods are over the continuous interval [a,1][a,1][a,1], giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$. We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all NNN eigenvalues are known exactly, a pure spectral polynomial pSp_{S}pS​ can interpolate 1/x1/x1/x at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of KKK eigenvalues of $\bA$. Given any base polynomial p0p_0p0​, such as Remez, of degree d0d_0d0​, a K×KK\times KK×K linear system enforces exact interpolation of 1/x1/x1/x only at these KKK eigenvalues without increasing d0d_0d0​. The spectrally corrected polynomial pSCp_{SC}pSC​ preserves the continuous error profile between eigenvalues and inherits the parity of p0p_0p0​. QSVT experiments on the 1D Poisson equation demonstrate up to a 5×5\times5× reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to 10%10\%10% relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above 0.9990.9990.999.
Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).
We introduce polynomial approximations of the even and odd step functions on the interval [−1,1][-1,1][−1,1] with simple Chebyshev coefficients, making their numerical implementation straightforward. We derive rigorous error bounds and demonstrate that these polynomials are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor that grows logarithmically with the polynomial order. From these polynomials, we derive related nearly optimal polynomial approximations that can be used to perform quantum phase estimation, linear amplitude amplification, eigenvalue thresholding, and other quantum algorithms using the quantum singular value transform.
Quantum singular value transformation (QSVT) is a powerful framework that unifies many quantum algorithms, including Grover’s search, by enabling polynomial transformations of the singular values of linear operators embedded in unitary matrices. We present an improved quantum search algorithm within this framework. Instead of amplifying the target state amplitude, our method suppresses the non-target amplitude using a modified Chebyshev polynomial. This approach achieves the optimal O(Nlog⁡(1/δ))\mathcal {O}(\sqrt {N}\log (1/\delta))O(N​log(1/δ)) query complexity while requiring lower-degree polynomials. For N = 512, our method reduces the polynomial degree from 71 to 43 compared to prior QSVT-based fixed-point search. We also demonstrate how QSVT enables exact search construction.
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state ∣ψ⟩|ψ\rangle∣ψ⟩, a Hermitian matrix HHH, a polynomial fff, and a set of observables {O1,…,Om}\{O_1,\dots,O_m\}{O1​,…,Om​}, the goal is to estimate ⟨ψ∣f(H)†Ojf(H)∣ψ⟩\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle⟨ψ∣f(H)†Oj​f(H)∣ψ⟩ for all j∈{1,…,m}j\in\{1,\dots,m\}j∈{1,…,m}. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of f(H)f(H)f(H). It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with HHH and ∣ψ⟩|ψ\rangle∣ψ⟩ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from HHH, fff, and ∣ψ⟩|ψ\rangle∣ψ⟩ without prior knowledge of the observables or explicit preparation of the target state proportional to f(H)∣ψ⟩f(H)|ψ\ranglef(H)∣ψ⟩. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.