Grover Optimization for Lock Scheduling Problems

Kurzfassung

There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption.

In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators.

[1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996).

[2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).