Sciencemag.cz
Doporučujeme
Tentokrát jde o něco jiného než o demonstraci rychlosti řešení konkrétního problému, jak loni tvrdil Google v menším sporu s IBM. Nyní tu máme mít formální důkaz. Vše ovšem vyžaduje trochu vysvětlování: to, že kvantové počítač využívá superpozici a nachází se během výpočtu „v mnoha stavech současně“, samo o sobě žádným důkazem není. Na kvantovém počítači totiž nedokážeme spustit díky tomu rychlejší klasický algoritmus, ale musíme mít speciální kvantový.
Další krok v argumentaci: víme přece, že existují kvantové algoritmy, např. Shorův (faktorizace) a Groverův (vyhledávání), které jsou rychlejší než ty klasické, jenže to stále ještě neznamená důkaz. Může být, že jsme ten nejefektivnější algoritmus (klasický) prozatím jen nenašli. Zde narážíme na to, že pro některé úlohy vůbec nelze rozhodnout, zda daný algoritmus je ten nejrychlejší možný (to je zase nějak ekvivalentní gödelovské nerozhodnutelnosti). U jiných úloh pak povaha nejrychlejšího algoritmu zase stojí na rozhodnutí problému P vs. NP, tj. na dosud nevyřešeném problému výpočetní složitosti. Například kdyby se dokázalo, že P = NP, pak by to znamenalo – protože faktorizace je ekvivalentní NP nebo jednodušší -, že existuje i nějaký dosud neznámy klasický algoritmus pro faktorizaci, s polynomiálně rostoucí složitostí – a tedy rychlejší než kvantový algoritmus Shorův. Takový výsledek sice nepředpokládáme, ale kdyby k němu došlo, rázem by bylo po kvantové nadřazenosti pro tuto úlohu.
Robert König z Technické univerzity v Mnichově, David Gosset z University of Waterloo a Sergey Bravyi z IBM nyní (poznámka PH: článek v Science je z roku 2018, zmínku jsem objevil až nyní) ale přišli s formálním důkazem. Prokázali, že minimálně v jednom typu úlohy jsou kvantové algoritmy nadřazené všem možným klasickým. Konkrétně šlo o klasické vs. kvantové obvody s konstantní hloubkou (constant depth). Součástí důkazu má být i to, že za kvantovou nadřazenost jsou odpovědné konkrétní vlastnosti kvantové fyziky/výpočtů (superpozice, nelokalita atd.).
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, Robert König,
Science, DOI: 10.1126/science.aar3106
Zdroj: Technical University Munich/TechXplore.com
Ti autoři už o tom důkazu psali v 2017.
https://arxiv.org/pdf/1704.00690.pdf
Jde jen o velmi omezený soubor úloh (řešení magického čtverce) diskutabilního využití.
Jde jen o teoretický výsledek (prý mají být takové kvantové počítače nejsnáze/nejdříve zkonstruovatelené, ale stále nejsou).