Institute of Network Engineering

SEMINAR

TOPIC：On the Power of Hybrid Classical and Low-depth Quantum Computation

TIME：110/05/05 (Wed.) 3:30-5:00PM

LOCATION：工程四館117室

SPEAKER：Prof. Kai-Min Chung鐘楷閔 教授

【講者簡介】

Research Fellow, Institute of Information Science, Academia Sinica

Kai-Min Chung received a bachelor's degree from National Taiwan University, and a Ph.D. from Harvard University. His advisor was Salil Vadhan. After his Ph.D., he was a postdoctoral researcher at Cornell University for three years and supported by Simons postdoctoral fellowship. He joined the Institute of Information Science, Academia Sinica as an assistant research fellow in Sept., 2013, and became an research fellow in Feb., 2020.  His research interests lie in the field of cryptography and its interplay with complexity and quantum theory. He has published works in these fields at major conferences such as STOC, FOCS, CRYPTO, Eurocrypt, CCC, QIP, and QCrypt. He has served on the program committees of major cryptography conferences such as CRYPTO, Eurocrypt, Asiacrypt, TCC, and QCrypt.  

【講題大綱】

In this talk, Dr. Chung will present oracle separations between BQP and both hybrid models, which proved Aaronson’s conjecture and showed that Jozsa’s conjecture cannot hold relative to oracles. In fact, they prove a stronger statement that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$ in the presence of classical computation. As a side note, the same conclusion is independently proved by Coudron and Menda using a different oracle problem, but they showed a shaper separation that doubling the quantum depth is strictly more powerful for both hybrid models relative to some oracles.