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

arXiv:1907.06814 · Physical Review Research

Quantum-inspired algorithm for general minimum conical hull problems

Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Dacheng Tao

Published Aug 5, 2020• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevresearch.2.033199

Related papers

Quantum Divide-and-Conquer Anchoring

Yuxuan Du

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.

•Feb 28, 2018•0 citations

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•11 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•11 citations

Quantum-Inspired Classical Algorithm for Principal Component Regression

Daniel Chen, Yekun Xu, Betis Baheri +4 more

This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.

arXiv:2010.08626•Oct 16, 2020•4 citations

Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $\mathrm{poly}(\log n)$, our algorithm gives a succinct description and any entry of the solution matrix in time $O(m\cdot\mathrm{poly}(\log n,1/\varepsilon))$ given access to a sample-based low-overhead data structure of the constraint matrices, where $\varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: $\bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},\ldots,A_{\tau}$, we propose a procedure that gives a good approximation of $A=A_{1}+\cdots+A_{\tau}$. $\bullet$ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix $A$. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.

•Jan 10, 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•202 citations
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.
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.
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with mmm constraint matrices, each of dimension nnn and rank poly(log⁡n)\mathrm{poly}(\log n)poly(logn), our algorithm gives a succinct description and any entry of the solution matrix in time O(m⋅poly(log⁡n,1/ε))O(m\cdot\mathrm{poly}(\log n,1/\varepsilon))O(m⋅poly(logn,1/ε)) given access to a sample-based low-overhead data structure of the constraint matrices, where ε\varepsilonε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: ∙\bullet∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,AτA_{1},\ldots,A_{\tau}A1​,…,Aτ​, we propose a procedure that gives a good approximation of A=A1+⋯+AτA=A_{1}+\cdots+A_{\tau}A=A1​+⋯+Aτ​. ∙\bullet∙ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix AAA. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.
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.