Kvantový procesor Google Sycamore, zdroj: Google

Dokázali výpočetní nadřazenost kvantového počítače

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

Viz také:
Google vs. IBM: kvantová nadřazenost pod lupou

S ohromnou přesností zvážili planety v systému TRAPPIST-1

Před dvěma lety vyšla studie, ve které vědci upřesnili hmotnosti planet u TRAPPIST-1. Eric Agol …

One comment

  1. 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).

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