QSE Quantum Seminar, "Halving the Cost of Quantum Algorithms with Randomization" - John Martyn

Please join us for the QSE Center Quantum Seminar with John Martyn from Harvard University who will give the talk "Halving the Cost of Quantum Algorithms with Randomization" on Thursday November 13 from 12:30pm to 2:00pm
Location: BS 160

Pizzas will be available between the seminars at 12:00. All PhDs, postdocs, students, group leaders, and PIs are welcome to join us.

TITLE: "Halving the Cost of Quantum Algorithms with Randomization"

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 at little to no overhead. In this talk, we will 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/\epsilon))$---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 will demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.

BIO:
John is a Quantum Initiative Fellow at Harvard University, and a Staff Scientist of Pacific Northwest National Laboratory. In his research, he explores the theoretical side of quantum information, with a focus on developing quantum and classical algorithms for simulating physics and solving hard computational problems. He recently received his PhD in physics from MIT, advised by Isaac Chuang, during which he spent time interning at IBM Quantum and Google X. In the beforetimes, he received a BS in physics from the University of Maryland, and worked as a student researcher at Caltech.