MIT Researchers Introduce Stochastic Quantum Signal Processing (QSP) as a Randomly-Compiled Version of QSP, and Reduce the Cost of QSP-based Algorithms by a Factor of 1/2

Classical randomness has emerged as an important tool in addressing the challenge of designing quantum protocols and algorithms. Current methods for calibrating and evaluating quantum gates, like randomized benchmarking, depend heavily on classical randomness. Many researchers are exploring ways to incorporate classical randomness to reduce the requirements of traditional quantum algorithms due to the progress towards gaining quantum advantage and developing early fault-tolerant quantum hardware. However, these techniques, especially randomized compiling, have been limited to specific areas like Trotterized Hamiltonian simulation and phase estimation, leaving a gap for other quantum algorithms.

The existing methods discussed in this paper include a model of quantum computation that uses a constant-size control register, strongly coupled to many qubits with local connectivity. While this setup supports controlled time evolution using the Trotter approximation, it struggles to implement Hamiltonian simulation with Quantum Signal Processing (QSP) due to the small size of the control register. Other efforts have aimed at optimizing QSP implementation, particularly when dealing with unitary block-encoded operators encoded via controlled-U operations. Although there are ways to remove parity constraints for real polynomials, these methods often introduce an unwanted factor of 1/2.

Researchers from the Center for Theoretical Physics, Massachusetts Institute of Technology, and IBM Quantum, MIT-IBM Watson AI Lab, have proposed an approach called Stochastic QSP to address the limitations in randomized quantum algorithms. This method aims to reduce the error in QSP polynomial approximations of target functions with the help of randomized compiling. Moreover, Stochastic QSP can achieve a query complexity scaling with error ϵ as O(log(1/ϵ)) for almost all QSP-based algorithms. This leads to an asymptotic halving of the cost of QSP-based algorithms compared to their deterministic versions, effectively combining the strengths of QSP and randomization.

The architecture of Stochastic QSP is designed to apply randomized compiling techniques to common polynomials used in quantum algorithms. This method is evaluated on four specific polynomials: 

• The Jacobi-Anger expansions of cosine
• The Jacobi-Anger expansion of an exponential decay
• A smooth approximation of 1/x in a domain away from the origin, where x ∈ [−1, 1].
• An approximation of erf(kx) obtained from integrating the Jacobi-Anger expansion of a Gaussian, where k is a parameter.

Each polynomial includes a cost parameter, that determines the necessary truncation degree for accurate approximation.

The results of applying Stochastic QSP to the selected polynomials demonstrate its effectiveness in reducing query complexity. As the degree d increases, the cost reduction ratio davg/d approaches 1/2, with the discrepancy scaling as O(1/d). This confirms the method’s ability to halve the query complexity of QSP-based algorithms in practical applications. For some functions and cost parameter values, davg/d approaches 1/2 from below, indicating even better performance for smaller d values. This advantage is due to optimizing constants C and q values in the implementation process. Moreover, a pattern in the cost reduction ratio is observed, linked to the ceiling function used when setting the cutoff degree d*.

In this paper, researchers introduced Stochastic QSP to overcome limitations in randomized quantum algorithms. It marks a major step in optimizing quantum algorithms by combining QSP with randomized compiling. It can reduce circuit complexity by a factor of 2 across various quantum algorithms, including real/imaginary time evolution, matrix inversion, phase estimation, and ground state preparation. The results highlight the importance of classical randomness as a resource in quantum computing, bringing quantum algorithms closer to practical use. Future research includes exploration using Stochastic QSP with noisy gates, which may improve practical applications further.

Check out the Paper. All credit for this research goes to the researchers of this project. Also, don’t forget to follow us on Twitter and join our Telegram Channel and LinkedIn Group. If you like our work, you will love our newsletter..

Don’t Forget to join our 50k+ ML SubReddit

⏩ ⏩ FREE AI WEBINAR: ‘SAM 2 for Video: How to Fine-tune On Your Data’ (Wed, Sep 25, 4:00 AM – 4:45 AM EST)