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

Walking crystals may lead to new field of crystal robotics

February 23, 2018

Researchers have demonstrated that tiny micrometer-sized crystals—just barely visible to the human eye—can "walk" inchworm-style across the slide of a microscope. Other crystals are capable of different modes of locomotion ...

Researchers turn light upside down

February 23, 2018

Researchers from CIC nanoGUNE (San Sebastian, Spain) and collaborators have reported in Science the development of a so-called hyperbolic metasurface on which light propagates with completely reshaped wafefronts. This scientific ...

Recurrences in an isolated quantum many-body system

February 23, 2018

It is one of the most astonishing results of physics—when a complex system is left alone, it will return to its initial state with almost perfect precision. Gas particles, for example, chaotically swirling around in a container, ...

Seeing nanoscale details in mammalian cells

February 23, 2018

In 2014, W. E. Moerner, the Harry S. Mosher Professor of Chemistry at Stanford University, won the Nobel Prize in chemistry for co-developing a way of imaging shapes inside cells at very high resolution, called super-resolution ...

Hauling antiprotons around in a van

February 22, 2018

A team of researchers working on the antiProton Unstable Matter Annihilation (PUMA) project near CERN's particle laboratory, according to a report in Nature, plans to capture a billion antiprotons, put them in a shipping ...

0 comments

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.