Quantum algorithm could help AI think faster

One of the ways that computers 'think' is by analysing relationships within large sets of data. An international team has shown that quantum computers can do one such analysis faster than classical computers, for a wider array of data types than was previously expected.

The team's proposed 'quantum linear system algorithm' is published in the 2 February issue of Physical Review Letters. In the future, it could help crunch numbers on problems as varied as commodities pricing, social networks and chemical structures.

"The previous quantum algorithm of this kind applied to a very specific type of problem. We need an upgrade if we want to achieve a quantum speed up for other data," says Zhikuan Zhao, corresponding author on the work.

That's exactly what he's offering, in joint work with colleague Anupam Prakash at the Centre for Quantum Technologies, National University of Singapore, and collaborator Leonard Wossnig, then at ETH Zurich and the University of Oxford. Zhao is a PhD student with the Singapore University of Technology and Design.

The first quantum linear system algorithm was proposed in 2009 by a different group of researchers. That algorithm kick-started research into quantum forms of machine learning, or artificial intelligence.

A linear system algorithm works on a large matrix of data. For example, a trader might be trying to predict the future price of goods. The matrix may capture historical data about price movements over time and data about features that could be influencing these 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.

"There is a lot of computation involved in analysing the matrix. When it gets beyond say 10,000 by 10,000 entries, it becomes hard for classical computers," explains Zhao. This is because the number of computational steps goes up rapidly with the number of elements in the matrix: every doubling of the matrix size increases the length of the calculation eight-fold.

The 2009 algorithm could cope better with bigger matrices, but only if the data in them is what's known as 'sparse'. In these cases, there are limited relationships among the elements, which is often not true of real-world data.

Zhao, Prakash and Wossnig present a new algorithm that is faster than both the classical and the previous quantum versions, without restrictions on the kind of data it works for.

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.

There have been a few proof-of-principle demonstrations of the earlier quantum linear system algorithm on small-scale quantum computers. Zhao and his colleagues hope to work with an experimental group to run a proof-of-principle demonstration of their algorithm, too. They also want to do a full analysis of the effort required to implement the algorithm, checking what overhead costs there may be.

To show a real quantum advantage over the classical algorithms will need bigger quantum computers. Zhao estimates that "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."

Research Report: "A quantum linear system algorithm for dense matrices"

Related Links
Centre for Quantum Technologies at the National University of Singapore
All about the robots on Earth and beyond!

Tweet

Thanks for being there;
We need your help. The SpaceDaily news network continues to grow but revenues have never been harder to maintain.

With the rise of Ad Blockers, and Facebook - our traditional revenue sources via quality network advertising continues to decline. And unlike so many other news sites, we don't have a paywall - with those annoying usernames and passwords.

Our news coverage takes time and effort to publish 365 days a year.

If you find our news sites informative and useful then please consider becoming a regular supporter or for now make a one off contribution.

SpaceDaily Monthly Supporter
$5+ Billed Monthly

paypal only

SpaceDaily Contributor
$5 Billed Once

credit card or paypal

Bezos hails Alexa as Amazon profits surge
San Francisco (AFP) Feb 1, 2018
Amazon on Thursday reported its profits had more than doubled in the past quarter as company founder Jeff Bezos heaped praise on the performance of its Alexa digital assistant. Net profit more than doubled to $1.9 billion, compared with $749 million a year earlier, for the US online giant which has expanded from retail to video to cloud computing and other services. Overall revenues for Amazon rose 38 percent from last year to $60.5 billion. The growth was even more impressive considering Am ... read more