Adiabatic Quantum Computing for Multi Object Tracking

Multi-Object Tracking (MOT) is an NP-hard problem in computer vision. A recent paper published on arXiv.org proposes a quantum computing formulation of MOT.

The problem is mapped to a quantum mechanical system, whose energy is equivalent to the cost of the optimization problem. An adiabatic quantum computer (AQS), which implements a quantum mechanical system made from qubits which can be described by the Ising model, is used to measure the lowest energy state of the system.

Researchers propose a reformulation of MOT solvable by real quantum computers, which have a limited number of qubits. In the suggested formulation, the number of required qubits formulation grows linearly in the number of detections, tracks, and timesteps. It is demonstrated that current AQCs can solve small real-world tracking problems and that the proposed approach closely matches state-of-the-art MOT methods.

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.

Research paper: Zaech, J.-N., Liniger, A., Danelljan, M., Dai, D., and Van Gool, L., “Adiabatic Quantum Computing for Multi Object Tracking”, 2022. Link: https://arxiv.org/abs/2202.08837