Quantum Divide-and-Conquer Anchoring

Abstract

Among matrix decomposition methods, the two factorized matrices obtained by Non-negative matrix factorization (NMF) generally yield a more natural and interpretable representations. It is computationally expensive to find the two factorized matrices W and H with a fixed rank r from a non-negative matrix X∈Rn⇥m by minimizing ||X-WH^Τ ||^2. Even if the proposed separability assumption enables polynomial separable NMF (SNMF) algorithms, the computational cost is not affordable for the continuously growing big data. As a powerful technique to deal with high dimensional data, quantum computing possesses quantum advantages for solving machine learning problems, at which the quantum advantages include both an exponential speedup and a more efficient learning ability with respect to the classical counterparts. In this research, based on the divide-and-conquer anchoring (DCA) scheme, quantum DCA (QDCA) is devised to solve SNMF problems. Benefiting from the linear algebraic nature of quantum mechanics and the convenience that statistical distribution is natively available in quantum mechanics with a superset, QDCA achieves an exponential speedup with respect to the classical counterpart. The runtime complexity is O(poly log(n + m)), where n x m is the size of the input matrix. In addition, the proposed QDCA can naturally generalize to solve near-separable NMF under a polynomial logarithmic runtime. Specifically, the time consuming divide step can be completed by a quantum algorithm for linear operations with an exponential speedup. In the conquer step, considering that reading out quantum data into classical forms is exponential expensive and attributing to that anchors can be sampled with a high probability from a probability distribution in the resulting quantum states, the proposed heuristic post-selection method enables QDCA to extract information from quantum states efficiently, which also maintains the quantum speedup after measurements. Under a plausible assumption, QDCA performs efficiently, achieves the exponential speedup, and is beneficial for high dimensional problems. The QDCA is a hybrid quantum and classical algorithm that maintains the quantum speedup after measurements, which provides a new way to develop quantum machine learning algorithms.