Sciencemag.cz
Doporučujeme
Co vlastně znamená titulek převzatý z původní tiskové zprávy? Prolomení patří do uvozovek, v podstatě má jít o to, že optimalizační kvantový algoritmus QAOA (quantum approximate optimization algorithm) má své limity a u určitých typů úloh se jeho výsledky podstatně liší od správného řešení, skutečných maxim/minim.
Snad si to můžeme představit podobně jako fungování (nikoliv univerzálního) kvantového počítače D-Wave, který bude také dávat pro různé varianty optimalizačních úloh různě kvalitní výsledky.
Google příslušné algoritmy vyvíjí spolu s procesory, které by měly být vylepšeny (quantum-enhanced) o kvantové efekty. Algoritmus QAOA vlastně odpovídá situaci, kdy klasické a kvantové systémy pracují společně a předávají si mezivýsledky; dále je pak speciálně navržen tak, aby dokázal pracovat s daty plnými šumu. Nyní se ale ukazuje, že QAOA má některá zásadní omezení.
Jacob Biamonte ze Skoltechu (instituce vzniklá ve spolupráci s MIT) a jeho kolegové ve Physical Review Letters tvrdí, že QAOA i jiné tzv. kvantové variační algoritmy je stávajícími matematickými technikami velmi obtížné analyzovat, protože v jejich nitru dochází ke zpětné vazbě mezi klasickými a kvantovými částmi celého systému. Kvantová část může fungovat pouze po určitý omezený čas a během této doby se provede pouze limitované množství kvantových operací. V podstatě se jedná o iterace, kdy si jednotlivé části předávají data postupně se blížící konečnému výsledku.
Nicméně kvalita výsledku závisí na řadě parametrů, „hustotě“ problému, což může být např. hustota klauzule. Při problému splnitelnosti (satisfiability) se „hustota klauzule“ např. odvozuje od počtu proměnných a omezujících podmínek (dejme tomu, že v případě, jak rozsadit lidi na večírku, jde o počet lidí/židlí a omezení ve stylu, kdo vedle koho musí nebo nesmí sedět). „Hustota“ zde odpovídá podílu počtu omezení k počtu proměnných. Nový výsledek analýzy příslušných algoritmů praví: V případě vysoké hustoty problému nelze garantovat, že přístup QAOA dosáhne požadované přesnosti, a to bez ohledu na dobu běhu algoritmu (iterační přístup nefunguje).
Dosud bylo podobných omezení algoritmů tohoto typu známo jen málo, právě kvůli problematické analýze systémů kombinujících klasické a kvantové výpočty.
Reachability Deficits in Quantum Approximate Optimization, Physical Review Letters (2020).
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.124.090504
Zdroj: Skolkovo Institute of Science and Technology/Phys.org
Poznámka PH: Dalo by se tedy říct, že algoritmus se kouše na těch úlohách, které by byly výpočetně nejnáročnější i pro klasické algoritmy, nebo „vysoká hustota“ znamená něco trochu jiného?
