YQI Talk - John Martyn - MIT

Event time: 
Thursday, September 5, 2024 - 10:00am to 11:00am
Audience: 
YQI Researchers
Location: 
YQI Seminar Room See map
Event description: 

Halving the Cost of Quantum Algorithms with Randomization

Quantum signal processing (QSP) is a powerful subroutine for implementing polynomial transformations of linear operators and furnishes a unifying framework of nearly all quantum algorithms. In parallel to these developments, recent studies have introduced a new class of randomized quantum algorithms predicated on randomized compiling, which promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., ϵ to O(ϵ2))”, at little to no overhead. Here we integrate randomized compiling into QSP through the introduction of 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 the error achievable by an equivalent deterministic polynomial. Because nearly all QSP-based algorithms exhibit complexities scaling as O(log(1/ϵ)) due to a result in functional analysis, this suppression of error reduces their asymptotic cost by a factor of 1/2. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms: one can halve the cost of a deterministic quantum algorithm by lifting it to its randomized counterpart.

Livestream the event on Zoom (Yale login required)