Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
• understand and discuss current problems in quantum informatics,
• discuss new quantum computing technologies,
• exchange ideas and research results,
• integrate information across different research teams,
• build a community around quantum informatics.
Venue: Centrum Informatyki (D17) ul. Kawiory 21, 30-055 Kraków, room 1.19
Wednesday, June 12, 2019, 16:00-17:00
Topic: Solving hard problems on quantum computers
Recent advances in quantum computing – both increasing activity in theoretical research, but also hardware implementations that get better and better – motivate us to seek an answer to one important question: When will the quantum supremacy happen? And, though, we do not know the answer to this question yet, it is possible to describe one possible way of achieving it.
This talk will focus on solving NP-complete problems using quantum computers, and to keep it realistic and practical, real problems and results from real computers will be discussed. Some four-letter acronyms will be explained. First, the importance of targeting algorithms and applications to NISQ devices. Second, reduction  of a problem to the QUBO instance, and recent surprising (or not) results obtained from existing quantum annealers. Third, extending QUBO concept to the QAOA  to gain more flexibility. Despite the care of the practicality of the information provided, some nice mathematical derivations and references to fundamentals of physics can not be omitted.
 A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2 (2014): 5.
 E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014).