The proposed research described in the .rst bullet above will substan- tially extend our current understanding of the information-theoretic capabilities and limitations of quantum learning algorithms.The proposed research described in the second bullet will extend our understanding of what can be learned by computationally e .cient quantum algorithms.
Broader Impact This research plan is closely integrated with a plan to achieve broader impact through education which involves training students and broadly disseminating research results.Highlights of the plan to achieve broader impacts include:(a)developing advanced courses in computational learning theory at Columbia University (these courses will be largely project-oriented,and the PI will encourate students to pursue projects at the intersection of learning theory and quantum computation);(b)advising and guiding graduate students in their development as researchers and educators,and actively working with advanced Ph.D.students to perform the proposed research;(c) widely disseminating the results of the PI 's research through a range of di .erent mediums,including talks,conference and journal publications,and survey articles on quantum computational learning.
