Google racet om kwantumverbeterde processors te ontwikkelen die kwantummechanische effecten gebruiken om de snelheid te verhogen waarmee gegevens kunnen worden verwerkt. Op korte termijn, Google heeft nieuwe kwantumverbeterde algoritmen bedacht die werken in de aanwezigheid van realistische ruis. Het zogenaamde quantum-benaderingsoptimalisatie-algoritme, of kortweg QAOA, is de hoeksteen van een modern streven naar de ontwikkeling van ruistolerante kwantumverbeterde algoritmen.

De gevierde aanpak van Google in QAOA heeft grote commerciële belangstelling gewekt en een wereldwijde onderzoeksgemeenschap aangestoken om nieuwe toepassingen te verkennen. Nog, er is weinig bekend over de ultieme prestatiebeperkingen van het QAOA-algoritme van Google.

Een team van wetenschappers van Skoltech's Deep Quantum Laboratory ging deze hedendaagse uitdaging aan. Het volledig Skoltech-team onder leiding van prof. Jacob Biamonte ontdekte en kwantificeerde wat een fundamentele beperking lijkt te zijn in de algemeen aanvaarde aanpak die door Google is geïnitieerd.

Melden in Fysieke beoordelingsbrieven , de auteurs beschrijven de ontdekking van zogenaamde bereikbaarheidstekorten - de auteurs laten zien dat deze tekorten een fundamentele beperking opleggen aan het vermogen van QAOA om zelfs maar een oplossing voor een probleem te benaderen, voorbeeld.

De bevindingen van het Skoltech-team melden een duidelijke beperking van het variabele QAOA-kwantumalgoritme. QAOA en andere variabele kwantumalgoritmen zijn uiterst moeilijk te analyseren gebleken met behulp van bekende wiskundige technieken vanwege een intern kwantum-naar-klassiek feedbackproces. Namelijk, een gegeven kwantumberekening kan maar een bepaalde tijd worden uitgevoerd. Binnen deze vaste tijd, een vast aantal kwantumbewerkingen kan worden uitgevoerd. QAOA probeert deze kwantumbewerkingen iteratief te gebruiken door een reeks steeds optimalere benaderingen te vormen om een ​​objectieve functie te minimaliseren. De studie stelt nieuwe grenzen aan dit proces.

De auteurs ontdekten dat het vermogen van QAOA om optimale oplossingen voor elk kwantumcircuit met vaste diepte te benaderen, fundamenteel afhankelijk is van de 'dichtheid' van het probleem. In het geval van het probleem genaamd MAX-SAT, de zogenaamde dichtheid kan worden gedefinieerd als de verhouding van de probleembeperkingen tot het aantal variabelen. Dit wordt soms clausuledichtheid genoemd.

De auteurs ontdekten problematische gevallen van hoge dichtheid met optimale oplossingen die niet met gegarandeerd succes kunnen worden benaderd, ongeacht de looptijd van het algoritme.