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).
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate
nFourier coefficients with 0 (poly log (
n)) gates compared to prior approaches with linear cost.
We show that the query complexity of preparing f ( H )| ψ 0 ⟩ is controlled by the optimal L 2 ( μ ) polynomial approximation degree of f , where μ is the spectral measure induced by ( H , | ψ 0 ⟩). Equivalently, the minimal number of queries is bounded below by the smallest Krylov–Favard truncation achieving error ε and bounded above, up to QSVT normalization overhead, by a linear function of that degree. This state-aware formulation sharpens worst-case bounds, unifies orthogonal-polynomial Krylov methods with quantum query complexity, and highlights how input-dependent spectral structure can yield substantial savings over uniform approximation schemes.
Estimating properties of unknown quantum states via quantum singular value transformation (QSVT) often requires high-degree polynomials to handle small eigenvalues of density matrices. Specifically, the existing approaches determine the polynomial degree by relying on overly conservative worst-case bounds based on the minimum non-zero eigenvalue or the rank of the density matrices. In this work, we propose a spectral cutoff method that truncates the negligible eigenvalue tail depending on the task, the target accuracy, and the state, which enables the use of significantly lower-degree polynomials. To implement this, we develop a two-stage algorithm to estimate nonlinear properties, particularly von Neumann entropy and R{é}nyi entropy. In the first stage, we execute a search algorithm to identify the spectral cutoff directly from the unknown quantum state. In the second stage, we estimate the nonlinear properties utilizing QSVT with the degree of polynomial adaptively determined by the cutoff. This two-stage algorithm significantly improves the overall estimation cost compared to known bounds, even without knowing the minimum eigenvalue or the rank.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.
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)), 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
pS 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
p0, such as Remez, of degree
d0, a
K×K linear system enforces exact interpolation of
1/x only at these
K eigenvalues without increasing
d0. The spectrally corrected polynomial
pSC preserves the continuous error profile between eigenvalues and inherits the parity of
p0.
QSVT experiments on the 1D Poisson equation demonstrate up to a
5× 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.