Kvantu aprēķins: apmācība

Samuel L. Braunstein

Abstract:

Iedomājieties datoru, kura atmiņa ir eksponenciāli lielāka par tā šķietamo fizisko izmēru; dators, kas var vienlaicīgi manipulēt ar eksponenciālu ievades kopu; dators, kas aprēķina Hilberta telpas krēslas zonā. Jūs domājat par kvantu datoru. Lai izveidotu kvantu datorus, ir nepieciešams salīdzinoši maz un vienkāršu kvantu mehānikas koncepciju. Smalkums ir bijis iemācīties manipulēt ar šiem jēdzieniem. Vai šāds dators ir neizbēgama, vai arī to uzbūvēt būs pārāk grūti?

Šajā rakstā mēs sniedzam apmācību par to, kā kvantu mehāniku var izmantot, lai uzlabotu aprēķinus. Mūsu izaicinājums: atrisināt eksponenciāli sarežģītu problēmu parastam datoram — liela skaita faktoru aprēķinam. Kā ievads mēs apskatām standarta skaitļošanas rīkus, universālos vārtus un mašīnas. Šīs idejas vispirms tiek pielietotas klasiskajiem, bezizkliedes datoriem un pēc tam kvantu datoriem. Ir aprakstīts kvantu datora shematisks modelis, kā arī daži tā programmēšanas smalkumi. Šora algoritms [1,2] efektīvai skaitļu faktoringai kvantu datorā ir parādīts divās daļās: kvantu procedūra algoritma ietvaros un klasiskais algoritms, kas izsauc kvantu procedūru. Tiek apspriesta faktoringa matemātiskā struktūra, kas padara iespējamu Šora algoritmu. Mēs noslēdzam ar perspektīvu par kvantu skaitļošanas iespējamību un perspektīvām nākamajos gados.

Sāksim ar šīs problēmas aprakstu: skaitļa N iekļaušana tā galvenajos faktoros (piemēram, skaitli 51688 var sadalīt kā ). Ērts veids, kā kvantitatīvi noteikt, cik ātri konkrēts algoritms var atrisināt problēmu, ir jautāt, kā tiek ievadīts algoritma pabeigšanas soļu skaits, ņemot vērā algoritma “ievades” lielumu. Faktoringa problēmai šī ievade ir tikai skaitlis N, kuru vēlamies faktorēt; tātad ievades garums ir . (Logaritma bāzi nosaka mūsu numerācijas sistēma. Tādējādi bāze 2 dod garumu binārā; bāze 10 decimāldaļās.) “Saprātīgi” algoritmi ir tādi, kas mērogojas kā daži mazas pakāpes polinomi ievades izmērā. (ar pakāpi, iespējams, 2 vai 3).

Parastos datoros pazīstamākais faktoringa algoritms darbojas soļos [3]. Tāpēc šis algoritms tiek eksponenciāli mērogots ar ievades lielumu . Piemēram, 1994. gadā 129 ciparu skaitlis (pazīstams kā RSA129 [3′]) tika veiksmīgi iekļauts, izmantojot šo algoritmu, aptuveni 1600 darbstacijās, kas izkaisītas visā pasaulē; visa faktorizēšana aizņēma astoņus mēnešus [4]. Izmantojot to, lai novērtētu iepriekšminētās eksponenciālās mērogošanas prefaktoru, mēs atklājam, ka būtu nepieciešami aptuveni 800 000 gadu, lai faktorētu 250 ciparu skaitli ar tādu pašu datora jaudu; tāpat 1000 ciparu skaitlim būtu nepieciešami gadi (ievērojami ilgāk par Visuma vecumu). Lielu skaitļu faktoringa grūtības ir ļoti svarīgas publiskās atslēgas kriptosistēmām, piemēram, tām, ko izmanto bankas. Tur šādi kodi ir atkarīgi no faktoringa skaitļu grūtībām ar aptuveni 250 cipariem.

Nesen tika izstrādāts algoritms skaitļu faktoringa noteikšanai kvantu datorā, kas darbojas soļos, kur ir mazs [1]. Ievades lielums ir aptuveni kvadrātisks, tāpēcfaktorēšanai 1000  ciparu skaitļaar šādu algoritmu būtu nepieciešami tikai daži miljoni soļu. Tas nozīmē, ka publiskās atslēgas kriptosistēmas, kuru pamatā ir faktorings, var būt salaužamas.

Lai sniegtu jums priekšstatu par to, kā šis eksponenciālais uzlabojums varētu būt iespējams, mēs pārskatām elementāru kvantu mehānisko eksperimentu, kas parāda, kur šāda jauda var būt paslēpta [5]. Divu spraugu eksperiments ir prototips kvantu mehāniskās uzvedības novērošanai: avots izstaro fotonus, elektronus vai citas daļiņas, kas nonāk spraugu pārī. Šīs daļiņas tiek pakļautas vienotai attīstībai un visbeidzot mērījumiem. Mēs redzam traucējumu modeli ar abām spraugām atvērtām, kas pilnībā izzūd, ja kāds no spraugām tiek aizsegts. Savā ziņā daļiņas paralēli iziet cauri abām spraugām. Ja šāda vienota evolūcija atspoguļotu aprēķinu (vai darbību aprēķinos), tad kvantu sistēma veiktu aprēķinus paralēli. Kvantu paralēlisms ir pieejams bez maksas. Šīs sistēmas izvadi dotu konstruktīvi traucējumi paralēlo aprēķinu starpā.

Subscribe to our alerts

Join the Privacy Club and receive alerts about VPN deals.

You can unsubscribe at any time

Subscribe to VPN alerts