Nav: Home

Skoltech scientists break Google's quantum algorithm

March 05, 2020

Google is racing to develop quantum enhanced processors that utilize quantum mechanical effects to one day dramatically reduce the speed at which data can be processed.

In the near term, Google has devised new quantum enhanced algorithms that operate in the presence of realistic noise. The so called quantum approximate optimisation algorithm, or QAOA for short, is the cornerstone of a modern drive towards noise-tolerant quantum enhanced algorithm development.

The celebrated approach taken by Google in QAOA has sparked vast commercial interest and ignited a global research community to explore novel applications. Yet, little actually remains known about the ultimate performance limitations of Google's QAOA algorithm.

A team of scientists, hailing from Skoltech's Deep Quantum Laboratory, took up this contemporary challenge. The all-Skoltech team led by Prof. Jacob Biamonte discovered and quantified what appears to be a fundamental limitation in the wildly adopted approach initiated by Google.

Reporting in Physical Review Letters, the authors detail the discovery of so called reachability deficits - the authors show how these deficits place a fundamental limitation on the ability of QAOA to even approximate a solution to a problem instance.

The Skoltech team's findings report a clear limitation of the variational QAOA quantum algorithm. QAOA and other variational quantum algorithms have proven extremely difficult to analyse using known mathematical techniques due to an internal quantum-to-classical feedback process. Namely, a given quantum computation can only run for a fixed amount of time. Inside this fixed time, a fixed number of quantum operations can be executed. QAOA seeks to iteratively utilize these quantum operations by forming a sequence of increasingly optimal approximations to minimize an objective function. The study places new limits on this process.

The authors discovered that QAOA's ability to approximate optimal solutions for any fixed depth quantum circuit is fundamentally dependent on the problems "density." In the case of the problem called MAX-SAT, the so called density can be defined as the ratio of the problems constraints to variable count. This is sometimes called clause density.

The authors discovered problem instances of high density whose optimal solutions cannot be approximated with guaranteed success, regardless of the algorithms' run-time.
-end-


Skolkovo Institute of Science and Technology (Skoltech)

Related Algorithms Articles:

Managing data flow boosts cyber-physical system performance
Researchers have developed a suite of algorithms to improve the performance of cyber-physical systems - from autonomous vehicles to smart power grids - by balancing each component's need for data with how fast that data can be sent and received.
New theory hints at more efficient way to develop quantum algorithms
A new theory could bring a way to make quantum algorithm development less of an accidental process, say Purdue University scientists.
AI as good as the average radiologist in identifying breast cancer
Researchers at Karolinska Institutet and Karolinska University Hospital in Sweden have compared the ability of three different artificial intelligence (AI) algorithms to identify breast cancer based on previously taken mammograms.
Context reduces racial bias in hate speech detection algorithms
When it comes to accurately flagging hate speech on social media, context matters, says a new USC study aimed at reducing errors that could amplify racial bias.
Researchers discover algorithms and neural circuit mechanisms of escape responses
Prof. WEN Quan from School of Life Sciences, University of Science and Technology of China (USTC) of the Chinese Academy of Sciences (CAS) has proposed the algorithms and circuit mechanisms for the robust and flexible motor states of nematodes during escape responses.
Lightning fast algorithms can lighten the load of 3D hologram generation
Tokyo, Japan - Researchers from Tokyo Metropolitan University have developed a new way of calculating simple holograms for heads-up displays (HUDs) and near-eye displays (NEDs).
Synergy emergence in deep reinforcement motor learning
Human motor control has always been efficient at executing complex movements naturally, efficiently, and without much thought involved.
Machine learning could improve the diagnosis of mastitis infections in cows
Artificial intelligence could help vets to more accurately diagnose the origin of mastitis on dairy herds, according to a new study from experts at the University of Nottingham.
How a new quantum approach can develop faster algorithms to deduce complex networks
Complex networks are ubiquitous in the real world, from artificial to purely natural ones, and they exhibit very similar geometric properties.
Algorithms 'consistently' more accurate than people in predicting recidivism, study says
In a study with potentially far-reaching implications for criminal justice in the United States, a team of California researchers has found that algorithms are significantly more accurate than humans in predicting which defendants will later be arrested for a new crime.
More Algorithms News and Algorithms Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Debbie Millman: Designing Our Lives
From prehistoric cave art to today's social media feeds, to design is to be human. This hour, designer Debbie Millman guides us through a world made and remade–and helps us design our own paths.
Now Playing: Science for the People

#574 State of the Heart
This week we focus on heart disease, heart failure, what blood pressure is and why it's bad when it's high. Host Rachelle Saunders talks with physician, clinical researcher, and writer Haider Warraich about his book "State of the Heart: Exploring the History, Science, and Future of Cardiac Disease" and the ails of our hearts.
Now Playing: Radiolab

Insomnia Line
Coronasomnia is a not-so-surprising side-effect of the global pandemic. More and more of us are having trouble falling asleep. We wanted to find a way to get inside that nighttime world, to see why people are awake and what they are thinking about. So what'd Radiolab decide to do?  Open up the phone lines and talk to you. We created an insomnia hotline and on this week's experimental episode, we stayed up all night, taking hundreds of calls, spilling secrets, and at long last, watching the sunrise peek through.   This episode was produced by Lulu Miller with Rachael Cusick, Tracie Hunte, Tobin Low, Sarah Qari, Molly Webster, Pat Walters, Shima Oliaee, and Jonny Moens. Want more Radiolab in your life? Sign up for our newsletter! We share our latest favorites: articles, tv shows, funny Youtube videos, chocolate chip cookie recipes, and more. Support Radiolab by becoming a member today at Radiolab.org/donate.