2:50 p.m.
Dear friends,
Tomorrow at 15.30 in D0.02 Lorenzo will give a talk on some very recent ideas he's had
about lower bounding the multivariate QSP protocol. Title and abstract below.
Join us in person or online at https://meet.jit.si/CQISeminarTalks
Oh, and don't miss Gilles Brassard's talk earlier in the day at 11 in D1.14!
Warmly,
Will
Title: An adversary bound for multivariate quantum signal processing
Abstract: Quantum signal processing (QSP) is a recent technique in the context of
algorithmic design, which consists of realising polynomial transformations of a variable
(the signal) embedded in a unitary operator (the signal operator). It can be shown that a
QSP ansatz can achieve nearly any polynomial, up to clear and mild conditions. These
techniques allow to unify a variety of known problems (including fixed-point amplitude
amplification, phase estimation, and optimal Hamiltonian simulation), by simply defining a
suitable polynomial transformation for the eigenvalues or singular values of a given
matrix that is block-encoded in a quantum circuit. While the class of implementable
polynomials is well-understood when the signal is a single variable, the case of
multivariate signals is still open. In this work, we borrow tools from quantum query
complexity (namely adversary method and gamma norms), to give a lower bound on the number
of steps needed to implement a given multivariate polynomial.