Part 4 Quantum Fourier transform–beyond Shor’s algorithm | András Gilyén (Alfréd Rényi Inst)

Lecture 4–Quantum Fourier transform beyond Shor’s algorithm Lecture notes http://gilyen.hu/teaching/PCMI_2023_QFT_prez_day_1.pdf Problem set1 http://gilyen.hu/teaching/PCMI_2023_ExerciseSheet_1.pdf Problem set2 https://www.ias.edu/sites/default/files/PCMI_2023_ExerciseSheet_2.pdf Problem set4 https://nextcloud.renyi.hu/index.php/s/K9aXgEC8aaW6dmQ The efficiency of Quantum Fourier transform (QFT) is the key ingredient in the exponential speed-up provided by Shor's algorithm and its generalization -- the hidden subgroup problem. In recent years several new applications of QFT were found that do not hinge upon uncovering some hidden algebraic structure, and we will explore those directions. Jordan's gradient computation algorithm, which is a common generalization of phase estimation an the Bernstein-Vazirani algorithm, is behind many such new applications, ranging from convex optimization to distribution learning and quantum tomography. We will also explore recent improvements over vanilla phase estimation, such as the removal of "bias" and a coherent way of boosting, which are important for some of the new applications. Finally, we will look at QFT in the Heisenberg picture, discuss operator Fourier transform, and its relevance to quantum computing. --- The 2023 Program: Quantum Computation Organizers: David Gosset, University of Waterloo; Aram Harrow, MIT; Stacey Jeffery, CWI and QuSoft; Ryan O'Donnell, Carnegie Mellon University; and Thomas Vidick, Caltech Very recently we have seen experiments at the boundary of the "quantum computing advantage", where quantum computers can massively outperform classical ones at certain tasks.  These advances highlight the need for further mathematical understanding of the computational power of near-term quantum devices.  The goal of the 2023 GSS is to dive deeply into the mathematics relevant for building near-term quantum computers, analyzing their power, and putting them to use.  Minicourses will include: overviews of quantum learning, information theory, and linear-algebraic algorithms; recent advances in quantum error-correcting codes; and, the complexity theory of random circuits and Hamiltonians. Structure: The Graduate Summer School at PCMI consists of a series of several interwoven minicourses on different aspects of the main research theme of that summer.  These courses are taught by leading experts in the field, chosen not only for their stature in the field but their pedagogical abilities. Each minicourse comprises three to five lectures. Each course is accompanied by a daily problem session, structured to help students develop facility with the material. 2023 Schedule Week 1   Andras: Quantum Fourier transform beyond Shor's algorithm   Omar: Quantum information theory   Srinivasan: Overview of quantum learning theory Week 2   Ewin: Quantum and quantum-inspired linear algebra   Nicolas: Quantum LDPC codes   Yassine: Quantum query complexity Week 3   Bill: Computational complexity of near-term quantum experiments   Jeongwan: Topological aspects of quantum codes   Sandy: Quantum Hamiltonian complexity — The GSS takes place within the broader structure of PCMI, so there are many researchers at all levels in the field in attendance, as well as participants in the other PCMI programs. ias.edu/PCMI