Quantum Signal Processing (QSP) has emerged as a unifying framework for quantum algorithms, providing a systematic approach to implementing polynomial transformations of linear operators. This research integrates randomized compiling with QSP to create Stochastic Quantum Signal Processing, achieving significant error reduction with minimal overhead.
The innovation lies in strategically implementing a probabilistic mixture of polynomials that converge to a target function while suppressing errors quadratically (transforming ϵ to O(ϵ²)). This advancement is particularly impactful because most QSP-based algorithms have query complexities scaling with √(1/ϵ), meaning this error suppression asymptotically reduces query complexity by nearly half.
Classical randomness has long been valuable in quantum computing, from randomized benchmarking and noise twirling in current experimental setups to random circuit sampling for quantum supremacy demonstrations. Randomized compiling specifically transforms unitary gates into quantum channels composed of probabilistic mixtures of unitaries, effectively suppressing gate errors without increasing circuit synthesis costs.
Previous applications of randomized compiling were limited to Trotterized Hamiltonian simulation and phase estimation. This research extends these benefits across the quantum algorithm landscape by using QSP as the implementation medium. This approach is particularly powerful because QSP underlies diverse quantum algorithms including Hamiltonian simulation, quantum search, matrix inversion, and integer factoring.
The theoretical foundation for this improvement comes from approximation theory for smooth functions. The researchers demonstrate both theoretically and empirically that the query complexity for nearly all QSP-based algorithms scales as √(1/ϵ). With the quadratic error suppression of Stochastic QSP, this translates to an asymptotic reduction in algorithmic cost by a factor approaching 1/2 compared to deterministic counterparts.
The researchers benchmark this approach across multiple applications, demonstrating performance improvements in real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion algorithms. By combining QSP’s structural advantages with randomization techniques, this work establishes a more efficient paradigm for implementing quantum algorithms with potential impacts across the field of quantum computing.
Reference: Martyn, J.M., Rall, P. Halving the cost of quantum algorithms with randomization. npj Quantum Inf 11, 47 (2025) ; doi:10.1038/s41534-025-01003-2
