Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Divide-and-Conquer Anchoring

Yuxuan Du

Published Feb 28, 2018• 0 citations
OpenAlex

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.

Related papers

Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization

Yuxuan Du, Tongliang Liu, Yinan Li +2 more

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^Τ ||^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 [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.

arXiv:1802.07828•International Joint Conference on Artificial Intelligence•Jul 1, 2018•10 citations

A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization

Zhihuai Chen, Yinan Li, Xiaoming Sun +2 more

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.

arXiv:1907.05568•International Joint Conference on Artificial Intelligence•Jul 28, 2019•7 citations

A divide-and-conquer algorithm for quantum state preparation

Israel F. Araujo, Daniel K. Park, Francesco Petruccione +1 more

Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with exponential time advantage using a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.

arXiv:2008.01511•Scientific Reports•Mar 18, 2021•169 citations

Quantum solvability of noisy linear problems by divide-and-conquer strategy

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +5 more

Abstract Noisy linear problems have been studied in various science and engineering disciplines. A class of ‘hard’ noisy linear problems can be formulated as follows: Given a matrix A ^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A ^ x ≈ b + η , where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

arXiv:1908.06229•Quantum Science and Technology•Feb 3, 2022•6 citations

Quantum-inspired algorithm for general minimum conical hull problems

Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu +1 more

A wide range of fundamental machine learning tasks that are addressed by the maximum a posteriori estimation can be reduced to a general minimum conical hull problem.The best-known solution to tackle general minimum conical hull problems is the divide-and-conquer anchoring learning scheme (DCA), whose runtime complexity is polynomial in size.However, big data are pushing these polynomial algorithms to their performance limits.In this paper, we propose a sublinear classical algorithm to tackle general minimum conical hull problems when the input has stored in a sample-based low-overhead data structure.The algorithm's runtime complexity is polynomial in the rank and polylogarithmic in size.The proposed algorithm achieves the exponential speedup over DCA and, therefore, provides advantages for high-dimensional problems.

arXiv:1907.06814•Physical Review Research•Aug 5, 2020•11 citations

Quantum solvability of noisy linear systems of equations by divide-and-conquer strategy.

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +5 more

Noisy linear problems have been studied in various science and engineering disciplines. A class of hard noisy linear problems can be formulated as follows: Given a matrix $\hat{A}$ and a vector $\mathbf{b}$ constructed using a finite set of samples, a hidden vector or structure involved in $\mathbf{b}$ is obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x} \approx \mathbf{b} + \boldsymbol\eta$, where $\boldsymbol\eta$ is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

•Aug 17, 2019•0 citations
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.
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^Τ ||^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 [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.
Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.
Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with exponential time advantage using a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.
Abstract Noisy linear problems have been studied in various science and engineering disciplines. A class of ‘hard’ noisy linear problems can be formulated as follows: Given a matrix A ^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A ^ x ≈ b + η , where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.
A wide range of fundamental machine learning tasks that are addressed by the maximum a posteriori estimation can be reduced to a general minimum conical hull problem.The best-known solution to tackle general minimum conical hull problems is the divide-and-conquer anchoring learning scheme (DCA), whose runtime complexity is polynomial in size.However, big data are pushing these polynomial algorithms to their performance limits.In this paper, we propose a sublinear classical algorithm to tackle general minimum conical hull problems when the input has stored in a sample-based low-overhead data structure.The algorithm's runtime complexity is polynomial in the rank and polylogarithmic in size.The proposed algorithm achieves the exponential speedup over DCA and, therefore, provides advantages for high-dimensional problems.
Noisy linear problems have been studied in various science and engineering disciplines. A class of hard noisy linear problems can be formulated as follows: Given a matrix A^\hat{A}A^ and a vector b\mathbf{b}b constructed using a finite set of samples, a hidden vector or structure involved in b\mathbf{b}b is obtained by solving a noise-corrupted linear equation A^x≈b+η\hat{A}\mathbf{x} \approx \mathbf{b} + \boldsymbol\etaA^x≈b+η, where η\boldsymbol\etaη is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.