GEORGIA TECH QUANTUM ALLIANCE GUEST LECTURE : Designing algorithms for near-term quantum computers

Omar Shehab - IonQ

Abstract: Noisy-intermediate scale quantum (NISQ) computers are currently being built at a number of places including academia and industry. A NISQ computer, capable of executing first proof-concept and then increasingly expensive quantum algorithms, will pave the way to build fault-tolerant errorcorrected (FTCC) quantum computers. While algorithms designed to practically run on FTCC quantum computers come with rigorously proven advantage over their classical counterparts, the advantage is still not fully clear for the NISQ computers. Nevertheless, strong promises are being made in recent research on NISQ algorithms.

The NISQ algorithms can be classified under broad categories, namely, quantum computational chemistry, quantum operations research, quantum machine learning, and quantum supremacy. The complexity theoretic aspect of these classes of algorithms are not well developed although currently being actively studied. In quantum computational chemistry, promising developments have been made in the last few years, for instance, variational quantum eigensolver algorithm, error mitigation, noise resilient hybrid algorithms, DMERA methods, Hamiltonian reduction methods, etc. Important results are also being reported in quantum operations research which is contributing to the development of a research roadmap for the domain experts. This includes noise resilient quantum approximate optimization algorithms, quantum approximate chaos optimization algorithm, planted solution technique, etc. The field of quantum machine learning has also observed a number of important discoveries in recent years while the major bottleneck, the QRAM problem, is still out of reach.

This talk will review the complexity theory aspect of the quantum supremacy experiments. It will also introduce the hybrid quantum computational chemistry algorithms and explore a number of ways to improve it. Similar review will be conducted for the quantum operations research algorithms and quantum machine learning algorithms. The challenges for developing algorithm for the future NISQ quantum computer will also be discussed. Finally, I will also try to comment on how the academia should prepare for the upcoming quantum revolution.

Bio: Omar Shehab received his PhD in computer science from UMBC in 2016. He joined IonQ, Inc., a University of Maryland based quantum computing startup, in 2017. His research focus is noisy-intermediate scale quantum algorithm, quantum programming language, and near-term hybrid quantum algorithm.