Hybrid quantum-classical algorithm accelerates dynamic mode decomposition for high-dimensional time series analysis

Seeking to reduce the computing power needed for the widely used dynamic mode decomposition algorithm, a team of researchers in China led by Guo-Ping Guo developed a quantum-classical hybrid algorithm. They tested their algorithm in three application scenarios: data denoising, scene background extraction, and fluid dynamics analysis. They determined that it can operate with only a small number of samples and has a quantum advantage in the analysis of high-dimensional time series. Their research was published 28 July in Intelligent Computing, a Science Partner Journal.

The quantum dynamic mode decomposition algorithm was developed and tested for accelerating high-dimensional time series analysis. It accomplishes exponential acceleration by decreasing the complexity of the operations performed on the time series data. In its current form, it can also be used to accelerate the analysis of certain other kinds of data sets as well. Moreover, the researchers plan to create new variants of their algorithm that are specialized for other dynamic mode decomposition applications, such as Koopman analysis.

The main limitation of the quantum algorithm is that the number of samples must be kept small, otherwise the complexity of the algorithm will not be reduced and the quantum advantage will be lost. The researchers were fully aware of this when designing the algorithm, and thus state an upper limit on the number of samples to ensure strong performance. However, researcher Cheng Xue of the Institute of Artificial Intelligence at the Hefei Comprehensive National Science Center explained, “Through numerical tests, we found that the number of samples required to analyze specific time series is lower than the bound we derived, which further illustrates the acceleration performance of our algorithm.”

To test the effect of changing the number of samples, the researchers explored applications of their quantum algorithm in different fields. The first, data denoising, is a process similar to removing noise from an image. The second, scene background extraction, is a common task in computer vision. It is a kind of image processing in which foreground items are removed by comparing a sequence of images of the same scene. The third, fluid dynamics analysis, is for predicting the movement of gas or liquid. The algorithm performed these tasks successfully.

Among many possible applications, fluid dynamics is particularly relevant. “Dynamic mode decomposition was originally used for flow field data analysis,” Xue explained. “The study of fluid dynamics often produces high-dimensional flow field data, with data dimensions reaching the scale of billions. Extracting meaningful flow field features from such data poses a challenging problem.”

The dynamic mode decomposition algorithm is a popular factorization and dimensionality reduction method in time series analysis. Time series analysis is the process of performing mathematical or statistical operations on a time series to discover important information.

A time series is a set of data collected as a series of samples spaced apart evenly in time, such as the value of a stock index at the end of each market day for one month, or the average daily temperature in a city over the course of a year. High-dimensional time series are composed of many pieces of information at each sampling time rather than only one, thus the processing and analysis of high-dimensional time series is more computationally intensive. Time series analysis is used in economics, finance and a wide variety of science and engineering fields.

Since quantum computers are still under development and relatively inaccessible, Xue’s work on quantum algorithms consists of “theoretical derivation plus numerical simulation,” but he says quantum chip technology is developing rapidly in a “synergistic” relationship with quantum algorithms, which promise “revolutionary breakthroughs” in the “near future.”  Quantum computers derive their power from two unintuitive characteristics, superposition and entanglement, which allow them to perform many computations in parallel. However, as Xue reminds us, quantum computing “can only speed up specific problems, and cannot replace classical computers.”