Quantum algorithm could help AI think faster

February 5, 2018, National University of Singapore
Credit: CC0 Public Domain

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 is published in 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.

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 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 their data is 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 that is faster than both the classical and the previous quantum versions, without restrictions on the kind of data it crunches.

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 tens of thousands of steps and the new quantum algorithm just hundreds 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 computation with application in artificial intelligence."

Explore further: Researchers implement 3-qubit Grover search on a quantum computer

More information: Leonard Wossnig et al, Quantum Linear System Algorithm for Dense Matrices, Physical Review Letters (2018). DOI: 10.1103/PhysRevLett.120.050502

Related Stories

Solving systems of linear equations with quantum mechanics

June 9, 2017

(Phys.org)—Physicists have experimentally demonstrated a purely quantum method for solving systems of linear equations that has the potential to work exponentially faster than the best classical methods. The results show ...

Quantum algorithm breakthrough

February 24, 2013

An international research group led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, has demonstrated a quantum algorithm that performs a true calculation for the first time. ...

Developing quantum algorithms for optimization problems

July 26, 2017

Quantum computers of the future hold promise for solving complex problems more quickly than ordinary computers. For example, they can factor large numbers exponentially faster than classical computers, which would allow them ...

Recommended for you

How a particle may stand still in rotating spacetime

May 25, 2018

When a massive astrophysical object, such as a boson star or black hole, rotates, it can cause the surrounding spacetime to rotate along with it due to the effect of frame dragging. In a new paper, physicists have shown that ...

Scientists discover new magnetic element

May 25, 2018

A new experimental discovery, led by researchers at the University of Minnesota, demonstrates that the chemical element ruthenium (Ru) is the fourth single element to have unique magnetic properties at room temperature. The ...

Long live the doubly charmed particle

May 25, 2018

Finding a new particle is always a nice surprise, but measuring its characteristics is another story and just as important. Less than a year after announcing the discovery of the particle going by the snappy name of Ξcc++ (Xicc++), ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.