  Conditional random field (CRF) is an important probabilistic machine learning
model for labeling sequential data, which is widely utilized in natural
language processing, bioinformatics and computer vision. However, training the
CRF model is computationally intractable when large scale training samples are
processed. Since little work has been done for labeling sequential data in the
quantum settings, we in this paper construct a quantum CRF (QCRF) model by
introducing well-defined Hamiltonians and measurements, and present a quantum
algorithm to train this model. It is shown that the algorithm achieves an
exponential speed-up over its classical counterpart. Furthermore, we also
demonstrate that the QCRF model possesses higher Vapnik Chervonenkis dimension
than the classical CRF model, which means QCRF is equipped with a higher
learning ability.
