  It is NP-complete to find non-negative factors $W$ and $H$ with fixed rank
$r$ from a non-negative matrix $X$ by minimizing $\|X-WH^\top\|_F^2$. Although
the separability assumption (all data points are in the conical hull of the
extreme rows) enables polynomial-time algorithms, the computational cost is not
affordable for big data. This paper investigates how the power of quantum
computation can be capitalized to solve the non-negative matrix factorization
with the separability assumption (SNMF) by devising a quantum algorithm based
on the divide-and-conquer anchoring (DCA) scheme. The design of quantum DCA
(QDCA) is challenging. In the divide step, the random projections in DCA is
completed by a quantum algorithm for linear operations, which achieves the
exponential speedup. We then devise a heuristic post-selection procedure which
extracts the information of anchors stored in the quantum states efficiently.
Under a plausible assumption, QDCA performs efficiently, achieves the quantum
speedup, and is beneficial for high dimensional problems.
