New quantum algorithm for visual tracking

Visual tracking, which trains a classifier to distinguish the target from the surrounding environment given an initial sample patch containing the target, plays an important role in computer vision. Yu et al. proposed a quantum algorithm for visual tracking (QVT) (rho Z( ) l11 rho Z+rho 2poly log N X [Phys. Rev. A 94, 042311 (2016)] with time complexity o epsilon based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal. Mach. Intell. 7, 583 (2015)], where rho X(Z) is the condition number of the data matrix X (Z), N is the dimension of the original sample patch, and epsilon is the desired accuracy of the output state. To get a (rho Z (1+rho X )poly log N ) further speedup, we propose a new QVT with time complexity o epsilon based on the algorithm of Henriques et al. Our algorithm achieves a quadratic speedup on the condition number rho X(Z) compared to the algorithm of Yu et al. Also, it shows exponential speedups on N over the classical counterpart when rho X(Z) and epsilon are o (poly log N). Finally, we extend it to the nonlinear two-dimensional multi-channel case.(c) 2023 Elsevier B.V. All rights reserved.