- back to listing
Past Events
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.