CQI Seminar: Lorenzo Laneve
by William Schober
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.
7 months, 1 week
Fw: Informatics Seminar on Wednesday, May 22, Gilles Brassard
by William Schober
________________________________
From: decanato.inf(a)usi.ch <noreply.newsletter(a)usi.ch>
Sent: Tuesday, May 14, 2024 11:56 AM
To: Schober William <william.schober(a)usi.ch>
Subject: Informatics Seminar on Wednesday, May 22, Gilles Brassard
Università
della
Svizzera
italiana
INF
[usi] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fusi.ch&h=mBP0qzw6Uzt1c2...>
[usi]
Informatics Seminar
Browser version<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fpub...> [arrow] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fpub...>
[arrow]
[main_banner]
On computable numbers, with an application to the Druckproblem
Host: Prof. Stefan Wolf
Wednesday
22.05
USI East Campus, Room D1.14
11:00 - 12:00
Gilles Brassard
Université de Montréal, Canada
[news_img]
Abstract: In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name “printable” to real numbers that Turing originally called “computable”, we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the “computable” description of a real number to its “printable” description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective.
Biography: Professor of computer science at the Université de Montréal since 1979, Gilles Brassard laid the foundations of quantum cryptography at a time when nobody could have predicted that the quantum information revolution would usher in a multi-billion dollar industry. He is also among the inventors of quantum teleportation, which is one of the most fundamental pillars of the theory of quantum information. Fellow of the Royal Society of London and the International Association for Cryptologic Research, International Member of the National Academy of Sciences of the United States, and Officer of the Orders of Canada and Québec, his many accolades include the Wolf Prize in Physics, the Micius Quantum Prize, the BBVA Foundation Frontiers of Knowledge Award in Basic Sciences and the Breakthrough Prize in Fundamental Physics. He has been granted honorary doctorates from ETH Zürich, the University of Ottawa and Università della Svizzera italiana in Lugano.<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.inf.usi.ch%2Fit%2Ff...>
Università
della
Svizzera
italiana
Quicklinks:
INF Website<https://newsletter.usi.ch/email/n?l=http%3A%2F%2Fwww.inf.usi.ch%2F%3Futm_...>
INF Newsletter Archive<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fns_...>
Campus Lugano<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.desk.usi.ch%2Fen%2F...>
Follow us:
[https://uikit.usi.ch/assets/base/img/icons/twitter_white.png] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Ftwitter.com%2FUSI_inf&h...>
[https://uikit.usi.ch/assets/base/img/icons/twitter_black.png]
[https://uikit.usi.ch/assets/base/img/icons/facebook_white.png] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.facebook.com%2Fusiu...>
[https://uikit.usi.ch/assets/base/img/icons/facebook_black.png]
[https://uikit.usi.ch/assets/base/img/icons/linkedin_white.png] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.linkedin.com%2Fscho...>
[https://uikit.usi.ch/assets/base/img/icons/linkedin_black.png]
[https://uikit.usi.ch/assets/base/img/icons/youtube_white.png] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.youtube.com%2Fusiun...>
[https://uikit.usi.ch/assets/base/img/icons/youtube_black.png]
[https://uikit.usi.ch/assets/base/img/icons/instagram_white.png] <https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.instagram.com%2Fusi...>
[https://uikit.usi.ch/assets/base/img/icons/instagram_black.png]
Unsubscribe here<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Funs...>
Reports decanato.inf(a)usi.ch<https://newsletter.usi.ch/email/n?l=mailto%3Adecanato.inf%40usi.ch&h=mBP0...>
7 months, 1 week
