New quantum linear system algorithm could speed up machine learning
Researchers at the Centre for Quantum Technologies (CQT) in Singapore have proposed a new algorithm for solving systems of linear equations that is faster than both the classical and the previous quantum versions, and without restrictions on the kind of data it works for.
Systems of linear equations are involved in problems ranging from commodities pricing to social networks and chemical structures.
A linear system algorithm works on a large matrix of data. For example, for a trader trying to predict the future price of goods, the matrix may capture historical price movement data, as well as data about features that could be influencing those prices, such as currency exchange rates. The algorithm calculates how strongly each feature is correlated with another by ‘inverting’ the matrix. This information can then be used to extrapolate into the future.
The analysis of the matrix involves significant computation. It becomes hard for classical computers, once the size goes beyond say 10,000 by 10,000, because the number of computational steps goes up rapidly with the number of elements in the matrix. Each doubling of the matrix size increases the length of the calculation eight-fold.
The first quantum linear system algorithm was proposed in 2009 by a different group of researchers and it kick-started research into quantum forms of machine learning, or artificial intelligence. As this article from Nature explains, a quantum computer can compress the information and perform calculations on select features extracted from the data and mapped onto quantum bits, or qubits, as opposed to the tedious number crunching required in classical computing. According to the article: “Quantum machine learning takes the results of algebraic manipulations and puts them to good use. Data can be split into groups — a task that is at the core of handwriting- and speech-recognition software — or can be searched for patterns. Massive amounts of information could therefore be manipulated with a relatively small number of qubits.”
The 2009 algorithm could handle bigger matrices better, offering an exponential advantage over the best classical algorithms, but only if the data in them is what’s known as ‘sparse’, as in most of the elements in the matrix are zero. In these cases, there are limited relationships among the elements, which is often not true of real-world data.
The new algorithm is faster and does not have restrictions on the type of data. As a rough guide, for a 10,000 square matrix, the classical algorithm would take on the order of a trillion computational steps, the first quantum algorithm some 10,000s of steps and the new quantum algorithm just 100s of steps. The algorithm relies on a technique known as quantum singular value estimation.
CQT's Jansen (Zhikuan) Zhao, Anupam Prakash and their collaborator, Leonard Wossnig, published their proposed ‘quantum linear system algorithm’ in the 2 February issue of Physical Review Letters.
A few proof-of-principle demonstrations of the earlier quantum linear system algorithm have been conducted on small-scale quantum computers. Jansen and his colleagues hope to work with an experimental group to run a proof-of-principle demonstration of their algorithm.
They also want to do a full analysis of the effort required to implement the algorithm, checking what overhead costs there may be.
Bigger quantum computers will be required to show a real advantage over the classical algorithms. Jansen said, “We’re maybe looking at three to five years in the future when we can actually use the hardware built by the experimentalists to do meaningful quantum computation with application in artificial intelligence.”