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.
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.
Quantum singular value transformation (QSVT) is a powerful quantum algorithm that can effectively perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. This article extends QSVT to perform a polynomial transformation of the amplitudes of a quantum state. This article presents an algorithm that can convert quantum state∑i=0N−1xi∣i⟩to quantum state∑i=0N−1∣f(xi)∣21∑i=0N−1f(xi)∣⟩and demonstrates the application of the algorithm in the quantum state small amplitude extraction.
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 generatenFourier coefficients with 0 (poly log (n)) gates compared to prior approaches with linear cost.
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.
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 O(κlog(κ/ε)) with condition number κ and uniform error ε. However, the \emph{optimal} polynomial with lowest degree for fixed error ε 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(κ/ε), 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.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because 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 superposition 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 [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
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.