  Visual tracking (VT) is the process of locating a moving object of interest
in a video. It is a fundamental problem in computer vision, with various
applications in human-computer interaction, security and surveillance, robot
perception, traffic control, etc. In this paper, we address this problem for
the first time in the quantum setting, and present a quantum algorithm for VT
based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal.
Mach. Intell., 7, 583 (2015)]. Our algorithm comprises two phases: training and
detection. In the training phase, in order to discriminate the object and
background, the algorithm trains a ridge regression classifier in the quantum
state form where the optimal fitting parameters of ridge regression are encoded
in the amplitudes. In the detection phase, the classifier is then employed to
generate a quantum state whose amplitudes encode the responses of all the
candidate image patches. The algorithm is shown to be polylogarithmic in
scaling, when the image data matrices have low condition numbers, and therefore
may achieve exponential speedup over the best classical counterpart. However,
only quadratic speedup can be achieved when the algorithm is applied to
implement the ultimate task of Henriques's framework, i.e., detecting the
object position. We also discuss two other important applications related to
VT: (1) object disappearance detection and (2) motion behavior matching, where
much more significant speedup over the classical methods can be achieved. This
work demonstrates the power of quantum computing in solving computer vision
problems.
