CQT researchers and their collaborator present a quantum speed-up for machine learning
One of the ways that computers ‘think’ is by analysing relationships within large sets of data. CQT’s Jansen (Zhikuan) Zhao, Anupam Prakash and their collaborator have 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 Jansen, who is corresponding author on the work.
That’s exactly what the team is offering. The CQT researchers began collaborating with Leonard Wossnig when he visited the Centre. He was then a Master’s Student at ETH Zurich. Jansen is a PhD student, and Anupam is a research fellow. Jansen’s PhD is 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 Jansen. 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.
Jansen, Anupam and Leonard 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. Jansen 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. Jansen 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.”
Learn more: Quantum algorithm could help AI think faster
The Latest on: Machine learning
- Machine learning with limited data on February 23, 2018 at 2:07 pm
Machine learning has been credited with a wide range of advancements over the past few years. It’s the backbone of image recognition technology, chatbots and driverless cars. “Many people right now are building machine learning applications across ... […]
- How Search Engines Use Machine Learning: 9 Things We Know for Sure on February 23, 2018 at 12:00 am
When we first started hearing about machine learning in the early 2010s, it seemed scary at first. But once it was explained to us (and we realized how technology is already being used to provide us with solutions), we started to get down to the practical ... […]
- Roundup Of Machine Learning Forecasts And Market Estimates, 2018 on February 22, 2018 at 6:39 pm
Machine learning patents grew at a 34% Compound Annual Growth Rate (CAGR) between 2013 and 2017, the third-fastest growing category of all patents granted. International Data Corporation (IDC) forecasts that spending on AI and ML will grow from $12B in ... […]
- Cisco: AI, Machine Learning Will Be Security Priorities in 2018 on February 22, 2018 at 5:43 pm
Security teams are investing in their defense strategies with technologies that leverage automation, machine learning and AI. But criminals are doing plenty of investing of their own in attack technologies while maturing the techniques they use to exploit ... […]
- GE Digital’s Edge Manager Relies on Machine Learning and Analytics on February 22, 2018 at 10:15 am
GE Digital believes that edge computing will play a key role in the industrial Internet of Things (IoT), and that’s why the company announced last October that it was expanding its Predix industrial IoT platform’s capabilities to better handle ... […]
- How machine learning can be used to break down language barriers on February 22, 2018 at 9:10 am
Machine learning has transformed major aspects of the modern world with great success. Self-driving cars, intelligent virtual assistants on smartphones, and cybersecurity automation are all examples of how far the technology has come. But of all the ... […]
- Google unveils machine learning ad tool on February 22, 2018 at 7:55 am
This story was delivered to BI Intelligence "Digital Media Briefing" subscribers hours before appearing on Business Insider. To be the first to know, please click here. Google unveiled Auto ads, a new ad unit for AdSense, its ad placement service for ... […]
- 3 Tips for Successfully Adopting Machine Learning Technologies on February 22, 2018 at 7:00 am
Insight for I&O leaders on deploying AIOps platforms to enhance performance monitoring today. Read the Guide. It’s no surprise that machine learning, natural language processing (NLP), and cognitive search technologies are being adopted at high rates. […]
- Feature Labs launches out of MIT to accelerate the development of machine learning algorithms on February 22, 2018 at 6:00 am
Feature Labs, a startup with roots in research begun at MIT, officially launched today with a set of tools to help data scientists build machine learning algorithms more quickly. Co-founder and CEO Max Kanter says the company has developed a way to ... […]
via Google News and Bing News