Mi ez a kvantumfölény?

Nem az a lényeg, hogy gyorsabban.

Egy bonyolult problémát sokszor csak exponenciális idő alatt lehet megoldani:

tehát egy kétszer olyan bonyolult az nem kétszer annyi idő, hanem 4-szer vagy 5-ször, és így tovább.

A kvantumszámítás a lehetséges eseteket egyszerre tudja vizsgálni, így a probléma bonyolultsága tűnik el.

Ez pl. azt eredményezheti, hogy egy hagyományos géppel - mondjuk egy szuperszámítógéppel - 10 ezer év alatt megfejthető kódolást 10 perc alatt fejt meg.

Persze ehhez azért kellene egy olyan kvantumszámítógép, amelyik nem csak 10 vagy 30 bites, hanem egy kicsit több.

Mondok konkrét példát is: pl. a mai titkosítások többsége azon alapul, hogy 2 db. hatalmas prímszámot szoroznak össze: mondjuk 30 jegyűeket.

Ott a szorzat, aztán találd meg, hogy mik az összetevői.

Tulajdonképpen nem nagy probléma:

- osztható kettővel?

nyilván nem.

- és hárommal?

azzal sem.

...szépen meg kell keresni, hogy mivel osztható.

Kettőtől fölfelé. Ha ez egy 60 jegyű szám, akkor 30 jegyig kell megnézni minden egyes prímszámot.

Kell hozzá egy kis idő, nem?

De a kvantumgépek egyszerre futtatják le az összes osztást.

Egy osztásnyi idő alatt megkapod az összes eredményt.

Az összes létező titkosításunkat dobhatjuk ki a kukába. Bank, mobiltelefon, és minden más.

Percek alatt fejthető.

Igen, az OTP.

De az meg nagyon macerás, mert hatalmas a kulcs, ami hozzá kell, és csak egyszer használható az életben.

Ha pedig valami ismert kulcsot használsz, pl. egy ismert könyvből veszed, akkor az is könnyen törhető.

Pontosítások:

"Mondok konkrét példát is: pl. a mai titkosítások többsége azon alapul, hogy 2 db. hatalmas prímszámot szoroznak össze: mondjuk 30 jegyűeket. ...

Kettőtől fölfelé. Ha ez egy 60 jegyű szám, akkor 30 jegyig kell megnézni minden egyes prímszámot."

Az RSA-ról írsz, csak nem nevezted meg.

Nem annyi jegyű lesz a szorzat, egyrészt kettes számrendszerben veszik hogy hány jegyű vagy másként mondva hogy hány bites. Manapság 2048 bites a szorzatra a minimum követelmény. Azán vissza lehet számolni hogy ez hatszázvalamennyi decimális számjegy. Az egyes random prímek generálására is van még követelmény amibe most ne menjünk bele. Továbbá nem többségébe ezen alapul hanem mondjuk úgy, hogy a használatban lévő titkosítások jelentős része. Az RSA kulcs prímtényezőire bontásának megpróbálására természetesen vannak optimalizációk, például hülyék lennénk kettőtől indulni. Éppen ezért a biztonság miatt vesznek ekkora prímeket, hogy mondjuk úgy hogy irreális hogy ezt valaki felbontja egy klasszikus számítógéppel (mármint nem kvantumszámítógéppel).

"De a kvantumgépek egyszerre futtatják le az összes osztást.

Egy osztásnyi idő alatt megkapod az összes eredményt."

Azért nem eszik ilyen forrón a kását. Azért ez nem igaz.

Figyelembe véve hogy klasszikusan vannak optimalizációk a naív próbaosztásokhoz képest is, még így ekkor is exponenciális idejű lesz. Vagyis a kulcs hosszát néhány számjeggyel növelve csak egy kicsit lesz hosszabb a kulcs, de a felbontásához szükséges időt megsokszorozza.

Kvantumosan viszont a kulcs hosszának köbével lesz arányos a felbontási idő. Vagyis ez klasszikusan exponenciális idejű, kvantumosan polinom idejű. Nagyon leegyszerűsítve ez olyan hogy nagyon nem mindegy hogy n jegyű szám négyzetgyökéig kell elpörgetni egy egyesével növelhető számlálót vagy n köbéig kell csak.

Részletek : [link]

"Persze ehhez azért kellene egy olyan kvantumszámítógép, amelyik nem csak 10 vagy 30 bites, hanem egy kicsit több."

A kvantumszámítógépeknél nem bitek hanem qubitek azaz kvantumbitek vannak.

"Igen, az OTP.

De az meg nagyon macerás, mert hatalmas a kulcs, ami hozzá kell, és csak egyszer használható az életben.

Ha pedig valami ismert kulcsot használsz, pl. egy ismert könyvből veszed, akkor az is könnyen törhető."

Az OTP ami nem a magyar bank, hanem a one time pad. Ami az egyetlen matematikailag bizonyított algoritmus melynek helyes alkalmazása mellett függetlenül a ráfordított idő és számítási módszer, számítási kapacitás mellett se jut közelebb a visszafejtéshez mint a legelején vagyis törhetetlen. Csak hát a gyakorlatban ez nem úgy megy. Ott már bukik a dolog hogy biztonságba juttasd el a másik félnek a kulcsot, akkor annyi erővel az eredeti üzenet is mehetett volna úgy. Jó meg lehet dumálni , hogy a kulcsot eljuttatom most amikor találkoztunk egy pendriveon. Aztán majd üzenünk egymásnak OTP-t használva amíg el nem fogy addig mehet.

Oké, ezt "mindenki" tudja, de már érdekesebb a dolog ha nem sima kriptográfiát használunk hanem kvantumkriptográfiát. Van az OTP-nek kvantumos megvalósítása, ahol a kvantumos csatorna végtelenített melyen a titoksító/visszafejtő kulcs megy át és van egy klasszikus csatorna. Ha a klasszikus csatornát egy harmadik fél lehallgatja semmit nem ér vele. Ha a kvantumosat hallgatja le akkor meg összeomlassza a hullámfüggvényt és a két fél észreveszi hogy lehallgatják. Persze ez ennél bonyolultabb ezt most csak leegyszerűsítve írtam.

[link]

> Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.[1] The weaker term Quantum advantage refers to the potential to solve problems faster. In computational-complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm.[2] The term was originally popularized by John Preskill[1] but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980)[3] and Richard Feynman's (1981) proposals of quantum computing.[4]