IMI Colloquium

2025年10月臨時 IMI Colloquium

※学外の方でご興味がある方はこちらへご登録ください。登録締切は9月25日（木）です。
https://forms.office.com/r/j4qNG3V9Ap

■日時：　2025年10月2日(木) 16:00 - 17:00
■場所：　IMIオーディトリアム及びZoomによるオンライン
■講師：　Prof. Dr. Thorsten Koch, Zuse Institute Berlin/Technische Universität Berlin
■講演タイトル：Quantum Optimization Benchmarking Library: The Intractable Decathlon
■講演要旨：
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.

IMIコロキウム 世話人
　池松 泰彦
　倉田 澄人
　田上 大助

・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

Additional IMI Colloquium in October 2025

If you are interested in the colloquium, please register here.
https://forms.office.com/r/j4qNG3V9Ap
※Registration deadline for external participants: Thu, Sep 25.

■Date : Thursday, ２, October 2025 16:00-17:00

■Place : IMI Auditorium(W1-D-413) 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.

IMI Colloquium Organizers
　IKEMATSU, Yasuhiko
　KURATA, Sumito
　TAGAMI, Daisuke