论文标题
通过量子退火凸出非负基质分解
Convex Non-negative Matrix Factorization Through Quantum Annealing
论文作者
论文摘要
在本文中，我们通过使用D-Wave量子式退火器提供了凸非阴性矩阵分解算法（convex-nmf）的量子版本。更确切地说，我们使用D-Wave 2000Q通过两个非负矩阵因子W和G找到固定实价x的低等级近似值，以使差异X-XWG的Frobenius Norm最小化。为了解决这个优化问题，我们将分两个步骤进行。在第一步中，我们根据W，G分别将全局实际优化问题转化为两个二次无约束的二进制优化问题（QUBO），分别取决于W和G。在第二步中，我们使用与W和G相对应的两个QUBO问题之间的替代策略来找到全局解决方案。 D-Wave 2000Q上这两个Qubo问题的运行需要使用嵌入到D-Wave 2000Q的Chimera图中，此嵌入受D-Wave 2000Q的量子数量的限制。我们对D-Wave 2000Q上的方法使用的最大数量实际数据进行了研究。拟议的研究基于用于表示每个实际变量的量子位数。我们还使用了几个随机生成的数据集测试了D-Wave 2000Q上的方法，以证明我们的方法比经典方法快，并且还证明它获得了最佳结果。
In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrix X by the product of two non-negative matrices factors W and G such that the Frobenius norm of the difference X-XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending on W,G into two quadratic unconstrained binary optimization problems (QUBO) depending on W and G respectively. In the second step we use an alternative strategy between the two QUBO problems corresponding to W and G to find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach on D-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.
