BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Dominik Hangleiter (Institute of Theoretical Physics\, Free Univer sity of Berlin\, Germany) DTSTART:20200910T070000Z DTEND:20200910T080000Z DTSTAMP:20260423T041751Z UID:UTSQSI/17 DESCRIPTION:Title: Quantum vs Classical Learnability of Discrete Distributions\nby Domini k Hangleiter (Institute of Theoretical Physics\, Free University of Berlin \, Germany) as part of Centre for Quantum Software and Information Seminar Series\n\n\nAbstract\nQuantum machine learning has been hailed as one of the promising near-term applications of small quantum computers and much r esearch is focused on devising quantum heuristics that might yield an adva ntage over classical learning algorithms.\nIn this talk\, we will take a s tep back and ask: Can we hope for a provable quantum advantage in machine learning? To this end we focus on the following learning task: Given sampl es from some unknown discrete probability distribution\, output an efficie nt algorithm for generating new samples from that distribution.\nIndeed\, many machine learning tasks can be reduced to such generative learning of discrete distributions. But it is not at all clear whether or not discrete distributions admit a structure that can be exploited by quantum computer s. Our main result is a positive answer to the above question: We explicit ly construct a class of discrete distributions which\, under the decisiona l Diffie-Hellman assumption\, is provably not efficiently learnable by a c lassical generative modelling algorithm\, but for which we construct an ef ficient quantum learner.\nFrom a bird's eye perspective\, our proof levera ges the power of quantum computers to solve the hidden subgroup problem to a distribution learning setting. But we will also take on the mole's pers pective and work through an intricate cryptographic argument that proves t he (conditional) learning separation.\n\nHosted by Márika Kieferová\, UT S Centre for Quantum Software and Information\n LOCATION:https://researchseminars.org/talk/UTSQSI/17/ END:VEVENT END:VCALENDAR