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:

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.
AI for #MeToo: Training algorithms to spot online trolls
Machine learning could be a powerful tool for allowing social media platforms to spot online trolls.
Developing a new AI breast cancer diagnostic tool
Scientists are developing a new way to identify the unique chemical 'fingerprints' for different types of breast cancers.
Artificial intelligence-based algorithm for intensive care of traumatic brain injury
A recent Finnish study, published in Scientific Reports, presents the first artificial intelligence (AI) based algorithm that may be utilized in the intensive care unit for treating patients with severe traumatic brain injury.
New algorithms train AI to avoid specific bad behaviors
Robots, self-driving cars and other intelligent machines could become better-behaved if machine-learning designers adopt a new framework for building AI with safeguards against specific undesirable outcomes.
New machine learning algorithms offer safety and fairness guarantees
Writing in Science, Thomas and his colleagues Yuriy Brun, Andrew Barto and graduate student Stephen Giguere at UMass Amherst, Bruno Castro da Silva at the Federal University of Rio Grande del Sol, Brazil, and Emma Brunskill at Stanford University this week introduce a new framework for designing machine learning algorithms that make it easier for users of the algorithm to specify safety and fairness constraints.
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

Listen Again: Meditations on Loneliness
Original broadcast date: April 24, 2020. We're a social species now living in isolation. But loneliness was a problem well before this era of social distancing. This hour, TED speakers explore how we can live and make peace with loneliness. Guests on the show include author and illustrator Jonny Sun, psychologist Susan Pinker, architect Grace Kim, and writer Suleika Jaouad.
Now Playing: Science for the People

#565 The Great Wide Indoors
We're all spending a bit more time indoors this summer than we probably figured. But did you ever stop to think about why the places we live and work as designed the way they are? And how they could be designed better? We're talking with Emily Anthes about her new book "The Great Indoors: The Surprising Science of how Buildings Shape our Behavior, Health and Happiness".
Now Playing: Radiolab

The Third. A TED Talk.
Jad gives a TED talk about his life as a journalist and how Radiolab has evolved over the years. Here's how TED described it:How do you end a story? Host of Radiolab Jad Abumrad tells how his search for an answer led him home to the mountains of Tennessee, where he met an unexpected teacher: Dolly Parton.Jad Nicholas Abumrad is a Lebanese-American radio host, composer and producer. He is the founder of the syndicated public radio program Radiolab, which is broadcast on over 600 radio stations nationwide and is downloaded more than 120 million times a year as a podcast. He also created More Perfect, a podcast that tells the stories behind the Supreme Court's most famous decisions. And most recently, Dolly Parton's America, a nine-episode podcast exploring the life and times of the iconic country music star. Abumrad has received three Peabody Awards and was named a MacArthur Fellow in 2011.