Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization
Authors: Yuxuan Du, Tongliang Liu, Yinan Li, Runyao Duan, Dacheng Tao
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 [Zhou et al., 2013]. 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. |
| Researcher Affiliation | Collaboration | Yuxuan Du1 , Tongliang Liu1 , Yinan Li2 , Runyao Duan2,3 , Dacheng Tao1 1 UBTECH Sydney AI Centre, SIT, FEIT, University of Sydney, Australia 2 Centre for Quantum Software and Information, University of Technology Sydney 3 Institute for Quantum Computing, Baidu Inc., Beijing 100193, China |
| Pseudocode | Yes | Algorithm 1 summarizes the proposed QDCA algorithm. |
| Open Source Code | No | The paper does not provide any information about open-source code availability, such as a link to a repository or a statement of code release. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity. It does not conduct experiments on specific datasets, so there is no mention of dataset access or public availability. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with data. Therefore, it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design for quantum computing and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and describes an algorithm. It does not provide details on specific software dependencies or version numbers. |
| Experiment Setup | No | The paper discusses a theoretical quantum algorithm and its complexity. It does not provide details on an experimental setup, such as hyperparameters or system-level training settings. |