Adiabatic Quantum Computing for Multi Object Tracking

Jan-Nico Zaech, Alexander Liniger, Martin Danelljan, Dengxin Dai, Luc Van Gool

Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. The association step naturally leads to discrete optimization problems. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. Adiabatic quantum computing (AQC) offers a solution for this, as it has the potential to provide a considerable speedup on a range of NP-hard optimization problems in the near future. However, current MOT formulations are unsuitable for quantum computing due to their scaling properties. In this work, we therefore propose the first MOT formulation designed to be solved with AQC. We employ an Ising model that represents the quantum mechanical system implemented on the AQC. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers. Finally, we demonstrate that our MOT problem is already solvable on the current generation of real quantum computers for small examples, and analyze the properties of the measured solutions.

Figure 1. The proposed approach to MOT states the assignment problem between detections and a set of tracks as a quadratic unconstrained binary optimization task. We then represent the optimization problem as a quantum mechanical system that can be implemented on an AQC. Via quantum annealing, a minimum energy state is found that represent the best assignment.

Figure 2. Solution probability and energy levels using simulated annealing for different noise levels and changing λ

Figure.3: Solution probability and energy levels using quantum annealing for different noise levels and changing λ.

Figure 4. Solution probability and energy levels using simulated annealing and optimized λi for different noise levels over λ off.

Table 1. Results on MOT15. X-val refers to results on the training set using leave-one-out cross validation.

Publication:

Adiabatic Quantum Computing for Multi Object Tracking

Jan-Nico Zaech, Alexander Liniger, Martin Danelljan, Dengxin Dai, Luc Van Gool

CVPR 2022

[Paper][BibTex]