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) [Phys. Rev. A 94, 042311 (2016)] with time complexity OϱZϱZ+ϱX2polylogNϵ based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal. Mach. Intell. 7, 583 (2015)], where ϱXZ is the condition number of the data matrix XZ, N is the dimension of the original sample patch, and ϵ is the desired accuracy of the output state. To get a further speedup, we propose a new QVT with time complexity OϱZ1+ϱXpolylogNϵ based on the algorithm of Henriques et al. Our algorithm achieves a quadratic speedup on the condition number ϱX(Z) compared to the algorithm of Yu et al. Also, it shows exponential speedups on N over the classical counterpart when ϱX(Z) and ϵ are OpolylogN. Finally, we extend it to the nonlinear two-dimensional multi-channel case.