We present a hybrid quantum-classical framework for simulating generic matrix functions more amenable to early fault-tolerant quantum hardware than standard quantum singular-value transformations. The method is based on randomization over the Chebyshev approximation of the target function while keeping the matrix oracle quantum, and is assisted by a variant of the Hadamard test that removes the need for post-selection. The resulting statistical overhead is similar to the fully quantum case and does not incur any circuit depth degradation. On the contrary, the average circuit depth is shown to get smaller, yielding equivalent reductions in noise sensitivity, as explicitly shown for depolarizing noise and coherent errors. We apply our technique to partition-function estimation, linear system solvers, and ground-state energy estimation. For these cases, we prove advantages on average depths, including quadratic speed-ups on costly parameters and even the removal of the approximation-error dependence.
We present a hybrid quantum-classical framework for simulating generic matrix functions more amenable to early fault-tolerant quantum hardware than standard quantum singular-value transformations. The method is based on randomization over the Chebyshev approximation of the target function while keeping the matrix oracle quantum, and is assisted by a variant of the Hadamard test that removes the need for post-selection. The resulting statistical overhead is similar to the fully quantum case and does not incur any circuit depth degradation. On the contrary, the average circuit depth is shown to get smaller, yielding equivalent reductions in noise sensitivity, as explicitly shown for depolarizing noise and coherent errors. We apply our technique to partition-function estimation, linear system solvers, and ground-state energy estimation. For these cases, we prove advantages on average depths, including quadratic speed-ups on costly parameters and even the removal of the approximation-error dependence.
Despite rapid advances in quantum hardware, noise remains a central obstacle to deploying quantum algorithms on near-term devices. In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source. We introduce a noise-resilient framework for Quantum Signal Processing (QSP) that mitigates such coherent errors without increasing circuit depth or ancillary qubit requirements. Our approach uses ensembles of noisy QSP circuits combined with measurement-level averaging to suppress random phase errors in Z rotations. Building on this framework, we develop robust QSP algorithms for implementing polynomial functions of Hermitian matrices and for estimating observables, with applications to Hamiltonian simulation, quantum linear systems, and ground-state preparation. We analyze the trade-off between approximation error and hardware noise, which is essential for practical implementation under the stringent depth and coherence constraints of current quantum hardware. Our results establish a practical pathway for integrating error mitigation seamlessly into algorithmic design, advancing the development of robust quantum computing, and enabling the discovery of scientific applications with near- and mid-term quantum devices.
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.
Abstract Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling , a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., ϵ → O ( ϵ 2 )) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing . Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as O(log(1/ϵ)) O ( log ( 1 / ϵ ) ) —stemming from a result in functional analysis—this error suppression reduces their query complexity by a factor that asymptotically approaches 1/2. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.
Randomized protocols are procedures that incorporate probabilistic choices during their execution and they play a central role in quantum algorithms, spanning Hamiltonian simulation, noise mitigation, and measurement tasks. In practical implementations, the dominant cost of such protocols typically arises from circuit execution and measurement, and depends on hardware-specific resources such as gate counts, circuit depth, runtime, or dissipated energy. We introduce a general framework for applying classical importance sampling to randomized quantum protocols. Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit that jointly captures the computational expense per circuit and the estimator variance. We further extend the framework to scenarios where the quantum computation is subject to errors arising either from algorithmic approximations or from physical noise, proving that importance sampling preserves estimator bias despite altering the sampling distribution, and to settings with error-detection schemes, where we characterize the resulting changes in the optimal sampling strategy and achievable net-cost reduction. Representative applications include the Qdrift protocol, dephasing channels, mixed-states simulation, composite observables estimation, classical shadows, and probabilistic error cancellation. Overall, our results establish a principled approach for reducing the computational resources required by randomized quantum protocols through classical sampling optimization.
We present a quantum-classical hybrid random power method that approximates a ground state of a Hamiltonian. The quantum part of our method computes a fixed number of elements of a Hamiltonian-matrix polynomial via quantum polynomial filtering techniques with either Hamiltonian simulation or block encoding. The use of the techniques provides a computational advantage that may not be achieved classically in terms of the degree of the polynomial. The classical part of our method is a randomized iterative algorithm that takes as input the matrix elements computed from the quantum part and outputs an approximation of ground state of the Hamiltonian. We prove that with probability one, our method converges to an approximation of a ground state of the Hamiltonian, requiring a constant scaling of the per-iteration classical complexity. The required quantum circuit depth is independent of the initial overlap and has no or a square-root dependence on the spectral gap. The iteration complexity scales linearly as the dimension of the Hilbert space when the quantum polynomial filtering corresponds to a sparse matrix. We numerically validate this sparsity condition for well-known model Hamiltonians. We also present a lower bound of the fidelity, which depends on the magnitude of noise occurring from quantum computation regardless of its charateristics, if it is smaller than a critical value. Several numerical experiments demonstrate that our method provides a good approximation of ground state in the presence of systematic and/or sampling noise.
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(logL) ancilla overhead and circuit depth O(Ldλ) for polynomial transformations of a Hamiltonian H=∑k=1LHk, where d is the polynomial degree and λ=∑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)), without requiring any complicated multi-qubit controlled gates. Moreover, λ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.