ICS 269, Fall 2022: Theory Seminar
Bren Hall 1427, 1:00 – 1:50

14 October 2022

An Introduction to Quantum Computing Through Amplitude Estimation

Shion Fukuzawa

Abstract: In this talk, I’ll introduce some of the basic concepts in quantum computing and explore how it can provide polynomial speedups for certain problems. Specifically, we will be examining the amplitude estimation problem, which is a frequently used subroutine for many quantum algorithms. One way of formulating this problem is as a counting problem, where one wishes to estimate the number of marked items in a larger set of size N. It was known for a long time that this can be done in approximately sqrt(N) time (ignoring log factors), even without using the quantum Fourier transform (which requires much more sophisticated quantum devices) at the expense of high constant factors [1]. Another line of work showed that these constant factors could be greatly reduced with the addition of an extra log(log()) factor [2]. We recently showed that the best of these two results can be achieved by introducing an asymptotically optimal and numerically competitive algorithm [3].

[1] Aaronson and Rall: Quantum Approximate Counting, Simplified [https://arxiv.org/abs/1908.10846]

[2] Grinko, Gacon, Zoufal, Woerner: Iterative quantum amplitude estimation [https://www.nature.com/articles/s41534-021-00379-1]

[3] Fukuzawa, Ho, Irani, Zion: Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal [https://arxiv.org/abs/2208.14612]