|
|
| (Seminar) Quantum Annealing of NP-hard problems, and constructing concrete "hard instances" |
| 2018-06-19
Text Size:
A A A |
|
CAS Key Laboratory of Theoretical Physics |
|
Institute of Theoretical Physics |
|
Chinese Academy of Sciences |
|
Seminar |
|
Title
题目 |
Quantum Annealing of NP-hard problems, and constructing concrete "hard instances" |
|
Speaker
报告人 |
Dr. Jun Takahashi |
|
Affiliation
所在单位 |
IOP/CAS |
|
Date
日期 |
2018年6月19日，上午10:00-11:00 |
|
Venue
地点 |
Conference Room 6420, ITP new Building |
|
Abstract
摘要 |
Quantum Annealing (QA) [1] is a physical protocol using quantum spins to solve combinatorial optimization problems. Since the necessary time for the protocol (i.e. the "computation time") is inverse proportional to the square minimum excitation energy gap of the quantum spin system, it naturally connects the two fields of statistical physics and computational complexity. In this study, we start from the computational complexity theoretic conjecture of "NP \nsubset BQP" and argue that it actually implies a physical conjecture as well, of an existence of a phase transition for some quantum spin-glass-like systems. We numerically investigate the nature of this expected phase transition and find a novel quantum phase which no conventional order parameters exist [2]. As we investigate the physical consequences of the computational complexity conjecture, we face difficulty coming from the fact that computational complexity theory is most of the time a framework of "worst-case" analysis. This also has been a stumbling block for past statistical-mechanics analysis on optimization problems (e.g. [3]) such that we can make predictions only in the form of "for most of the instances (with probability ~1)". In the second half of the talk, I will focus on a recent work where we construct a provable "hard instance" of the maximum independent set problem [4]. This problem is NP-complete and had been under intensive statistical-mechanics analysis. [1] E. Farhi et al. Science 292.5516, 472 (2001). [2] J. Takahashi and K. Hukushima, arXiv:1612.08554 (2016). [3] L. Zdeborova and M. Mezard, Phys. Rev. Lett. 101, 078702 (2008). [4] N. Shiraishi and J. Takahashi, to appear on arXiv soon. |
|
Contact person
所内联系人 |
张潘 |
 |
 |
|
|
