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:2207.14810 · Physical Review A

Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations

Duarte Magano, Miguel Murça

Published Dec 16, 2022• 3 citations
arXivHTMLPDF

Abstract

The problem of phase estimation (or amplitude estimation) admits a quadratic quantum speedup. Wang, Higgott, and Brierley [Wang, Higgott, and Brierley, Phys. Rev. Lett. 122, 140504 (2019)] have shown that there is a continuous tradeoff between quantum speedup and circuit depth [by defining a family of algorithms known as $\ensuremath{\alpha}$-quantum phase estimation $(\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE})$]. In this paper, we show that the scaling of $\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}$ can be naturally and succinctly derived within the framework of quantum singular value transformation (QSVT). From the QSVT perspective, a greater number of coherent oracle calls translates into a better polynomial approximation to the sign function, which is the key routine for solving phase estimation. The better the approximation to the sign function, the fewer samples one needs to determine the sign accurately. With this idea, we simplify the proof of $\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}$, while providing an interpretation of the interpolation parameters, and show that QSVT is a promising framework for reasoning about classical-quantum interpolations.

DOI
10.1103/physreva.106.062419

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

Randomized Quantum Singular Value Transformation

Xinzhao Wang, Yuxin Zhang, Hazra, Soumyabrata +3 more

We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.

arXiv:2510.06851•Oct 8, 2025•0 citations

A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques

Sean Greenaway, William Pol, Sukin Sim

In recent years, quantum algorithms have been proposed which use quantum phase estimation (QPE) coherently as a subroutine without measurement. In order to do this effectively, the routine must be able to distinguish eigenstates with success probability close to unity. In this paper, we provide the first systematic comparison between two approaches towards maximizing this success probability, one using the quantum singular value transform and the other leveraging window functions, which have been previously studied as priors of the phase value distribution. We find that the quantum singular value transform is significantly outclassed by the window function approach, with the latter able to achieve between 3 and 5 orders of magnitude improvement in the success probability with approximately 1/4 the query cost. Our circuit simulation results indicate that QPE is not a domain which benefits from the integration of QSVT and we show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.

arXiv:2404.01396•Apr 1, 2024•4 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

An Improved Classical Singular Value Transformation for Quantum Machine Learning

Ainesh Bakshi, Ewin Tang

The field of quantum machine learning (QML) produces many proposals for attaining quantum speedups for tasks in machine learning and data analysis. Such speedups can only manifest if classical algorithms for these tasks perform significantly slower than quantum ones. We study quantum-classical gaps in QML through the quantum singular value transformation (QSVT) framework. QSVT, introduced by Gilyén, Su, Low and Wiebe [GSLW19], unifies all major types of quantum speedup [MRTC21]; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead.

arXiv:2303.01492•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•14 citations

Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla

Shantanav Chakraborty, Hazra, Soumyabrata, Tongyang Li +3 more

We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic $O(\log L)$ ancilla overhead and circuit depth $\widetilde{O}(L dλ)$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L H_k$, where $d$ is the polynomial degree and $λ=\sum_{k}\|H_k\|$. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of $\widetilde{O}(L(dλ_{\mathrm{comm}})^{1+o(1)})$, without requiring any complicated multi-qubit controlled gates. Moreover, $λ_{\mathrm{comm}}$ depends on the nested commutators of the terms of $H$ and can be substantially smaller than $λ$ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. As applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.

arXiv:2504.02385•Apr 3, 2025•2 citations
The problem of phase estimation (or amplitude estimation) admits a quadratic quantum speedup. Wang, Higgott, and Brierley [Wang, Higgott, and Brierley, Phys. Rev. Lett. 122, 140504 (2019)] have shown that there is a continuous tradeoff between quantum speedup and circuit depth [by defining a family of algorithms known as \ensuremathα\ensuremath{\alpha}\ensuremathα-quantum phase estimation (\ensuremathα\ensuremath-QPE)(\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE})(\ensuremathα\ensuremath-QPE)]. In this paper, we show that the scaling of \ensuremathα\ensuremath-QPE\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}\ensuremathα\ensuremath-QPE can be naturally and succinctly derived within the framework of quantum singular value transformation (QSVT). From the QSVT perspective, a greater number of coherent oracle calls translates into a better polynomial approximation to the sign function, which is the key routine for solving phase estimation. The better the approximation to the sign function, the fewer samples one needs to determine the sign accurately. With this idea, we simplify the proof of \ensuremathα\ensuremath-QPE\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}\ensuremathα\ensuremath-QPE, while providing an interpretation of the interpolation parameters, and show that QSVT is a promising framework for reasoning about classical-quantum interpolations.
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.
We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.
In recent years, quantum algorithms have been proposed which use quantum phase estimation (QPE) coherently as a subroutine without measurement. In order to do this effectively, the routine must be able to distinguish eigenstates with success probability close to unity. In this paper, we provide the first systematic comparison between two approaches towards maximizing this success probability, one using the quantum singular value transform and the other leveraging window functions, which have been previously studied as priors of the phase value distribution. We find that the quantum singular value transform is significantly outclassed by the window function approach, with the latter able to achieve between 3 and 5 orders of magnitude improvement in the success probability with approximately 1/4 the query cost. Our circuit simulation results indicate that QPE is not a domain which benefits from the integration of QSVT and we show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.
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.
The field of quantum machine learning (QML) produces many proposals for attaining quantum speedups for tasks in machine learning and data analysis. Such speedups can only manifest if classical algorithms for these tasks perform significantly slower than quantum ones. We study quantum-classical gaps in QML through the quantum singular value transformation (QSVT) framework. QSVT, introduced by Gilyén, Su, Low and Wiebe [GSLW19], unifies all major types of quantum speedup [MRTC21]; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead.
We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic O(log⁡L)O(\log L)O(logL) ancilla overhead and circuit depth O~(Ldλ)\widetilde{O}(L dλ)O(Ldλ) for polynomial transformations of a Hamiltonian H=∑k=1LHkH=\sum_{k=1}^L H_kH=∑k=1L​Hk​, where ddd is the polynomial degree and λ=∑k∥Hk∥λ=\sum_{k}\|H_k\|λ=∑k​∥Hk​∥. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of O~(L(dλcomm)1+o(1))\widetilde{O}(L(dλ_{\mathrm{comm}})^{1+o(1)})O(L(dλcomm​)1+o(1)), without requiring any complicated multi-qubit controlled gates. Moreover, λcommλ_{\mathrm{comm}}λcomm​ depends on the nested commutators of the terms of HHH and can be substantially smaller than λλλ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. As applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.