News and Events
Coming Events
Past Events

Coming Events

back to listing

Time Complexity of Quantum Algorithm is Physical


Speaker:Prof. Biao Wu
Affiliation:International Center for Quantum Materials, Peking University
Date:January 25, 2018 (Thursday)
Time:4:30 p.m.
Venue:Room 522, 5/F, Chong Yuet Ming Physics Building, HKU

Abstract
 

There are two paradigms of quantum algorithm: one is quantum circuit algorithm (QCA) and the other is quantum adiabatic algorithm (QAA). We show that these two different types of quantum algorithms are exactly equivalent to each other in terms of time complexity. Our result shows that how fast you can solve a problem on quantum computer is essentially a physics problem. Our proof also implies a new way to generalize QAA. We show that this generalization of QAA can lead to faster quantum algorithm.

Reference: Hongye Yu, Yuliang Huang and Biao Wu, arXiv 1706.07646 (2017) 

Coffee and tea will be served 20 minutes prior to the seminar.

Anyone interested is welcome to attend.