Kvantový procesor Google Sycamore, zdroj: Google

Kvantově posílený algoritmus Googlu byl prolomen

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?

Jak funguje mrtvá voda

Mrtvou vodou se zde nemyslí voda bez života či voda jedovatá, ale stav, kdy kapalina …

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close