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.
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.