Forskere bryder Googles kvantealgoritme

Google ræser om at udvikle kvanteforbedrede processorer, der bruger kvantemekaniske effekter til at øge hastigheden, hvormed data kan behandles. På kort sigt, Google har udtænkt nye kvanteforstærkede algoritmer, der fungerer i nærvær af realistisk støj. Den såkaldte kvantetilnærmede optimeringsalgoritme, eller QAOA for kort, er hjørnestenen i en moderne indsats mod støjtolerant kvanteforstærket algoritmeudvikling.

Den berømte tilgang fra Google i QAOA har vakt stor kommerciel interesse og antændt et globalt forskningsfællesskab til at udforske nye applikationer. Endnu, der er lidt kendt om de ultimative ydeevnebegrænsninger af Googles QAOA-algoritme.

Et team af forskere fra Skoltechs Deep Quantum Laboratory tog denne nutidige udfordring op. All-Skoltech-teamet ledet af prof. Jacob Biamonte opdagede og kvantificerede, hvad der ser ud til at være en grundlæggende begrænsning i den bredt anvendte tilgang, som Google har iværksat.

Indrapportering Fysisk gennemgangsbreve , forfatterne detaljerede opdagelsen af ​​såkaldte utilgængelighedsmangler - forfatterne viser, at disse mangler sætter en grundlæggende begrænsning på QAOA's evne til selv at tilnærme en løsning på et problem, eksempel.

Skoltech-teamets resultater rapporterer en klar begrænsning af den variationsmæssige QAOA kvantealgoritme. QAOA og andre variationsmæssige kvantealgoritmer har vist sig ekstremt vanskelige at analysere ved hjælp af kendte matematiske teknikker på grund af en intern kvante-til-klassisk feedback-proces. Nemlig en given kvanteberegning kan kun køre i et bestemt tidsrum. Inden for denne faste tid, et fast antal kvanteoperationer kan udføres. QAOA søger at udnytte disse kvanteoperationer iterativt ved at danne en sekvens af stadig mere optimale tilnærmelser for at minimere en objektiv funktion. Undersøgelsen sætter nye grænser for denne proces.

Forfatterne opdagede, at QAOAs evne til at tilnærme optimale løsninger for ethvert kvantekredsløb med fast dybde er grundlæggende afhængig af problemernes "densitet". I tilfælde af problemet kaldet MAX-SAT, den såkaldte tæthed kan defineres som forholdet mellem problemernes begrænsninger og variabelt antal. Dette kaldes nogle gange klausulens tæthed.

Forfatterne opdagede problematiske tilfælde af høj tæthed med optimale løsninger, der ikke kan tilnærmes med garanteret succes, uanset algoritmens køretid.