Speaker
Description
Quadratic unconstrained binary optimization (QUBO) problems, including MAX-CUT as a special case, are important hard problems of mathematical optimization. Recently they have attracted much attention because they are the very problems that quantum annealers can address directly: QUBO problems are equivalent to the Ising model, a central and extensively studied problems in physics.
Even though the usefulness and efficiency of quantum annealers are subjects of many debates, their development is steadily going on. And the equivalence of QUBO and Ising models bridges between two different, well-developed approaches and insights to the problem: that of mathematicians and physicists. The former is based mainly on semidefinite relaxations or advanced cuts, whereas the latter offers a physical insight and includes DMRG/tensor network algorithms, classical and quantum annealing, or simulated bifurcation.
In the present talk we introduce the first railway application of quantum annealers that had been proposed partly by some of us. The railway dispatching / conflict management problem is addressed, which is equivalent to a job-shop scheduling with blocking and no-wait constraints. It is a computationally hard problem and the calculations have to conclude in a very limited time. We present
our proof of concept demonstration, described also by Domino et al. (Entropy vol. 25, 191 (2023)) based purely on quantum annealing, but calculated alternatively also on classical computers with tensor network algorithms (c.f. Rams et al., Phys. Rev. E vol. 104, 025308 (2021)). and with brute-force method on GPUs (Jałowiecki et al., arXiv:1904.03621v2 (2019)). We also present our ongoing work where we show that hybrid quantum-classical heuristics are valid and practically useful options in dealing with such a problem. We describe modeling strategies, benefits and limitations of quantum annealing approaches.
To illustrate one of the limitations of quantum annealers in detail, we discuss deeper the problem that that as most heuristics they do not necessarily find the optimum. We briefly present a probabilistic discriminator based on statistical physical ideas that can indicate whether the optimum was found (c.f. Domino et al., Quantum Information Processing vol21, 288 (2022)) . We also consider the standard (Fortet) linearization of a QUBO, and, as a mathematical approach, discuss the possibility of using MILP duality for the purpose of deciding whether an optimum was found. The latter approach is a general one, not specific to quantum annealing.
Finally discuss the perspectives of hybrid (HPC+quantum) solvers, and the potential benefits from using physics-motivated algorithms for solving QUBOs in general.
