An efficient quantum algorithm for independent component analysis

Abstract

Independent component analysis (ICA) is a fundamental data processing technique to decompose the captured signals into as independent as possible components. Computing the contrast function, which serves as a measure of the independence of signals, is vital and costs major computing resources in ICA. This paper presents a quantum algorithm that focuses on computing a specified contrast function on a quantum computer. Using the quantum acceleration in matrix operations, we efficiently deal with Gram matrices and estimate the contrast function with the complexity of $O(\epsilon_1^{-2}\mbox{poly}\log(N/\epsilon_1))$ . This estimation subprogram, combined with the classical optimization framework, builds up our ICA algorithm, which exponentially reduces the complexity dependence on the data scale compared with algorithms using only classical computers. The outperformance is further supported by numerical experiments, while our algorithm is then applied for the separation of a transcriptomic dataset and for financial time series forecasting, to predict the Nikkei 225 opening index to show its potential application prospect.

Keywords

• quantum algorithms
• signal separation
• financial time series forecasting
• independent component analysis