(October 2, 2025 16:00) Additional IMI Colloquium in October 2025
Prof. Dr. Thorsten Koch from Zuse Institute Berlin/Technische Universität Berlin will be giving a special lecture.
Zuse Institute Berlin is also one of the cooperative institutions of the GPMI. We warmly invite you to attend!
Please register to participate, either in person or online! -> Registration Form
| Date & Time | Thursday, ２, October 2025 16:00-17:00 |
| Place | IMI Conference Room (W1-D-414) and Live streaming with Zoom |
| Speaker | Prof. Dr. Thorsten Koch, Zuse Institute Berlin/Technische Universität Berlin |
| Title | Quantum Optimization Benchmarking Library: The Intractable Decathlon |
| Abstract | New hardware approaches are emerging, with quantum computers at the forefront, along with other systems such as data-flow machines, mem-computing, and bifurcation chips. All have in common their claim to “solve” challenging, i.e., NP-hard, combinatorial optimization problems more effectively than traditional methods. NP-hard problems are referred to as “intractable”, and, therefore, considered challenging. However, this characterizes the theoretical worst-case complexity for the entire class of problems. The assertion that finding a solution is exceedingly difficult pertains to the decision problem. In contrast, identifying some feasible solution to the optimization version of the problem is often straightforward. For instance, any permutation of cities constitutes a valid tour for the Traveling Salesperson Problem (TSP). The challenge lies in discovering the optimal tour and proving its optimality. The new approaches primarily can provide “good” solutions but fall short of proving optimality. The theoretical debate extends to whether and to what extent these problems can be approximated in polynomial time. However, the assurance an approximation algorithm offers is merely a lower bound on the solution’s quality. Numerous questions remain unanswered, and ultimately, the only method to evaluate the practical performance of heuristic algorithms is to benchmark them against relevant instances. We selected model-independent instances from a diverse set of ten different problem classes where classic exact and heuristic methods are known to have a difficult time. We will present our insights and performance results from classical, quantum, and other new systems. |
| 💻 Participate via Zoom 💻 | ||
| https://us06web.zoom.us/j/86497201637?pwd=sHBmysF5ac9mJGue3vAVlMoEbS7saI.1 | ||
| Meeting ID ： | 864 9720 1637 | *We recommend that participants install the Zoom app in advance. (Download-> https://zoom.us) |
| Passcode ： | 138145 | |
・The account name should be “Full name” in case of the faculty members, or “Student ID number (Last name)” (e.g.：1SC○○○○○A (Last name) in case of students.
・Please understand the host will mute the audience’s sound and camera.
・When you have a question, please use the “Raise hand function” or the “Chat function”. Then, the host will unmute.
IKEMATSU, Yasuhiko <ikematsu@imi.kyushu-u.ac.jp>
KURATA, Sumito <kurata@imi.kyushu-u.ac.jp>
TAGAMI, Daisuke <tagami@imi.kyushu-u.ac.jp>