Algebra akimirksniu  

Kvantiniai kompiuteriai gali daryti nuostabius dalykus. Tik viena bėda – jų dar nėra. Tačiau tai netrukdo teoretikams kurti jiems naujus algoritmus, sprendžiančius uždavinius gerokai greičiau nei įmanoma su Circuit of Quantum Computer įprastiniais kompiuteriais. Kai tik atsiras kvantiniai kompiuteriai, tie algoritmai taps taikymų, reikalaujančių didelio kiekio skaičių apdorojimo, pagrindu – nuo inžinerijos sprendimų iki kompiuterinių žaidimų.

Naujausias kvantinis algoritmas kelią susižavėjimą. Jis sprendžia tiesines lygtis, t.y. tokio tipo išraiškas: 3x+2y=7. Jos kiaurai persmelkę mechaniką ir per daug metų tapo tiesiog nuobodu jas spręsti – kiekvienu žingsniu eliminuojant po vieną kintamąjį. Sprendimo greitis tampa labai svarbu, kai turima milijonus kintamųjų ir lygčių, pvz. analizuojant meteorologijos reiškinius.

A.W. Harrow iš Bristolio un-to (Anglija) ir A. Hassidim bei S. Lloyd iš MTI (JAV) pasiūlytas kvantinis algoritmas pateikia esminę informaciją apie sprendinį nebaigus visų skaičiavimų ir taip nepaprastai paspartinant sprendimą (pvz., oro prognozės atveju jis gali pasakyti apie vidutinę temperatūrą konkrečiame mieste nelaukiant, kol bus pateikta visa prognozė miestui po miesto.

Jis aprašytas 2009 m. spalio 9 d. „Physical Review Letters“. Visa informacija koduojama kvantiniais bitais (kubitais), kurie, skirtingai nuo įprastinių bitų, galinčių įgauti tik „1“ ir „0“ reikšmes, gali vienu turėti abi šias reikšmes (arba kaip fizikai sako, turėti persiklojančias būsenas). Algoritmas bitus transformuoja į būseną, užkoduojančią visus galimus sistemos sprendimus, apimančius visas galimas lygčių konstantų reikšmes (dešinėje pusėje). Iš šio „universalaus“ sprendimo galima gauti svarbius iš konkretaus sprendimo nepaskaičiavus jų visų iki galo.

Greitis išauga nepaprastai. Kintamųjų skaičiui padidėjus 1000 kartų, algoritmas sulėtėja tik 3 kartus (vietoje daugiau nei 1000 kartų įprastiniuose algoritmuose). Bet kol kas teegzistuoja eksperimentiniai kvantiniai kompiuteriai, teturintys po kelis (kvantinius) bitus. Tačiau naujų algoritmų pademonstravimas turėtų būti jau artimoje ateityje.

Tekstas publikuotas 2009 m.  

Kliūtys kvantinių kompiuterių kelyje

Kvantiniai kompiuteriai niekada nepakeis įprastinių įtaisų, tokių, su kuriuo dabar skaitote šį tekstą. Juose ne tik kad neveiks naršyklės, jie nepadės jums su mokesčių paskaičiavimu ar su nelegaliai atsisiųsto naujausio filmo pažiūrėjimu.

O jie atliks, - kas jau senai iš jų tikimasi, - iš esmės kitokio pobūdžio tam tikrus paskaičiavimus. Jie pajėgs išpręsti uždavinius, kurie tradiciniams kompiuteriams užimtų milijonus metų. Jie galės atlikti sudėtingų kvantinių sistemų (kaip biologinės molekulės) simuliacijas ar rasti ypač didelių skaičių pirminius daugiklius, taip nieku paversdami dabartines šifravimo priemones. Taigi, svarbu suprasti, kur glūdi tas jų kvantinis pranašumas.

Iš tikro, šis terminas dirbtinis, - daugiau kalbos išsireiškimas, pagudravimas. Todėl rimti kvantinių skaičiavimų kūrėjai (tarkim, IBM) jo nesiekia. Tačiau, iš kitos pusės, jis apibūdina takoskyrą kompiuterių istorijoje – kvantiniai kompiuteriai būtų naudingi kai kurių praktinių uždavinių sprendimui.

Kaip jis pasiekiamas? Tarkim, metam lošimų kauliuką. Kvantinis kompiuteris gali iškart (vienu metu) paskaičiuoti visų 6-ių galimų atvejų pasekmes, kai įprastiniui kompiuteriui reiktų paeiliui atlikti skaičiavimus kiekvienam atvejui. Tarkim, turime schemą iš 50 kubitų. Informacijai einant per schemą galimos būsenos jungiasi ir schemos išėjimo taške turim 250 galimų būsenų perstatų.

Tai kas stabdo? Kol kvantinės schemos yra mažo dydžio, įprastiniai kompiuteriai gali būti ramūs. Siekiant pademonstruoti kvantinį pranašumą reikia sukurti didesnes schemas, o to inžinieriai dar nesugeba. Kvantinis hakeris

Schemos dydis nusakomas pradiniu kubitų skaičiumi ir kiekiu kartų, panaudotu manipuliavimui su tais kubitais. Manipuliacijos atliekamos naudojant „vartus“. Skirtingi vartų tipai kubitus transformuoja skirtingais būdais. Jei kubitai praleidžiami pro 10 „vartų“, sakoma, kad schemos gylis yra 10. Kvantinio pranašumo pademonstravimui mokslininkai tikisi turėti 70-100 kubitų schemą, kurios gylis 10.

Problema, su kuria dabar susiduria inžinieriai, yra ta, kad didinant kubitų skaičių ir schemos gylį, didėja ir klaidų skaičius. O kai klaidų skaičius didelis, tai kvantiniai kompiuteriai netenka pranašumo net prieš klasikinius kompiuterius. Yra daug klaidų priežasčių. Rimčiausia jų ta, kad klaida kaupiasi skaičiavime kaskart, kai schema atlieka „vartų“ operaciją. Šiuo metu geriausių dviejų kubitų „vartų“ klaidos lygis yra apie 0,5%, t.y. maždaug 1 klaida kas 200-ais paskaičiavimas. Tai beprotiškai aukštas klaidų lygis – ypač, kai įprastinių kompiuterių yra 1 klaida per 1017 operacijų. Tad inžinieriai siekia minėtos schemos klaidų lygį sumažinti bent iki 0,1%.

Kur dabar esam? „Google“ gviešiasi pademonstruoti kvantinį pranašumą iki šių metų (t.y. 2019-ųjų) pabaigos (na,... jie tą patį sakė ir 2017-ais). Nemažai kitų grupių irgi gali netrukus tai pasiekti (IBM, „IonQ“, „Rigetti“, Harvardo un-tas). Tos grupės kvantinį kompiuterį kuria skirtingai. „Google“, IBM ir „Rigetti“ jam panaudoja superlaidininkų grandines; „IonQ“ – „sugautus“ jonus; Harvarde M. Lukino grupė – rubidžio atomus valdomus lazerio spinduliu. O štai „Microsoft“ pasirinko „topologinius kubitus“, kas atrodo esant tolimu šūviu. Kiekvienas būdas turi savų pliusų ir savų minusų.

Superlaidininkinių pranašumas tas, kad jie iš kietų medžiagų; juos galima sukurti egzistuojančiomis priemonėmis ir „vartų“ operacijas jie atlieka labai sparčiai. Be to, kubitai „neišsivaikšto“, kas irgi pranašumas prieš kitas technologijas. Tačiau jie turi būti atšaldyti iki labai žemų temperatūrų ir kiekvienas kubitas superlaidininkinėje mikroscehemoje privalo būti 'indiv'idualiai kalibruotas, kas trukdo sukurti tūkstančių kubitų apimties kvantinius kompiuterius.

Jonų „spąstuose“ viskas priešingai. Atskiri jonai yra identiški, kad palengvina jų sukūrimą, ir „spąstai“ suteikia daugiau laiko skaičiavimams atlikti, kol bus užgošti aplinkos triukšmo. Tačiau „vartai“ veikia gerokai lėčiau (tūkstančius kartų lyginant su superlaidininkais), o paskiri jonai gali „išsilakstyti“, kai to nenorima.

Taip pat skaitykite IBM kuria kvantinį kompiuterį
2018 m.: palaidotos viltys dėl kvantinių skaičiavimų pranašumo?

Nobelio premija fizikams

2012 m. Nobelio premija fizikos srityje skirta Serge Haroche (Prancūzija) ir David Wineland (JAV) už eksperimentinius metodus vienetinių kvantinių sistemų srityje. Jie parodo, kad galima betarpiškai stebėti kvantines daleles jų nesunaikinant. Pavienėms dalelėms ar spinduliams klasikinės fizikos dėsniai nebegalioja, - joms taikomi kvantinės mechanikos metodai. Tačiau pavienes daleles labai sunku atskirti nuo jų aplinkos, o taip pat jos, sąveikaudamas su išoriniu pasauliu, praranda savo mistines kvantines savybes. S. Haroche ir D. Wineland'as su kolegomis sugebėjo išmatuoti labai nepatvarias kvantines būsenas. D. Wineland‘as sukūrė elektrinį krūvį turinčių atomų (jonų) gaudymo ir matavimo fotonais sistemą. O S. Haroche gaudė fotonus ir tyrė jų savybes per spąstus leisdamas atomus.

Abu laureatai dirba kvantinės optikos srityje, tiriančioje šviesos ir medžiagos sąveikas. Atradimai galėtų padėti sukurti ypač sparčius kvantinius kompiuterius, o taip pat nepaprastai tikslius laikrodžius.

[ Kvantinio kompiuterio veikimas pagrįstas tuo, kad vienu metu galimos kelios būsenos. Tad vietoje bitų turėtume kubitus, galinčius turėti tokias reikšmes: 0, 1 arba tų būsenų superpozicija, kad toks kompiuteris veiktų, būtina, kad atskiri kubitai būtų kvantiškai susieti. ]


Taip pat skaitykite: Kvantinė mechanika ir jos ribotumas
Savaime besiorganizuojantis kvantinis pasaulis


Ar kompiuteriai supranta meną?  

Žironos universiteto ir M. Planko instituto mokslininkai parodė, kad matematiniai algoritmai gali padėti nustatyti paveikslo menininko stilių. Spalvų parinkimas bei tam tikri estetiniai matavimai gali būti apdorojami kompiuteriu ir nurodyti, kuriam periodui priklauso paveikslas. Tuos „žemo lygio“ paveikslo duomenis sudaro potėpio storis, drobės tipas ir spalvų paletė. Vidutinio lygio informacija apima tam tikrus objektus bei scenas, o taip pat paveikslo tipą (kraštovaizdis, portretas ir pan.). Aukšto lygio informacija atsižvelgia į istorinį kontekstą ir žinias apie menininkus bei jų meninius polinkius. Paskutinės dvi prieinamos tik žmonėms.

Tokio pobūdžio tyrimus 1933-iais pradėjo matematikas George D. Birkhoff, pabandęs formalizuoti grožio sąvoką estetinių matų, apibrėžiamų kaip sąryšiai tarp tvarkos ir sudėtingumo, pagalba. Vėliau filosofas Max Bense tai pavertė matavimais, pagrįstais entropija. Anot jo, kūrybinis procesas yra selektyvus („kurti – tai pasirinkti“), renkantis iš elementų gausos (spalvų paletė, garsai, fonemos ir pan.). Į kūrybą galima žvelgti kaip į kanalą, perduodantį informaciją tarp paletės ir menininko bei atvaizdo objektų arba ypatybių. Ši koncepcija pateikia galingą įrankį, leidžiantį kompozicijos analizę bei paveikslo vizualinį dėmesį („išsikišimą“)

Elektroninis kompozitorius  

A. Beliajevo „Misteris Juokas“ (1937) herojė mis Bulver kuria „aparatą, kuriuo bus galima mechaniškai gaminti melodijas. Na bent jau taip, kaip aritmometras parodo galutinę reikšmę“. Bet panašūs bandymai žinomi jau nuo 18 a., kai naudoti grynai mechaniniai metodai. Pvz., Mocartas bandė kurti muziką žaidimo kauliukų pagalba....

Tačiau A. Beliajevas atkreipia dėmesį į labai svarbią detalę: pirma reikia suprasti kūrybos dėsnius, muzikos kūrimo technologiją, ir tik tada panaudoti mašiną. Taip ir pasielgė kibernetikai: 1955 m. Ilinojaus un-te Hileris ir Izaksonas užprogramavo ILLIAC kompiuterį, kad sukurtų siuitą styginiam kvartetui. Žinomi ir tarybinio tyrinėtojo R.Ch. Zaripovo*) bandymai modeliuojant muziką skaičiavimo mašina „Ural“.

Encryption

Nulaužtas 200 m. senumo šifras  

1801 m. prezidentui Tomui Džefersonui užšifruotą laišką atsiuntė Amerikos Filosofų draugijos kolega Robertas Patersonas, Pensilvanijos un-to matematikos profesorius. Tekste nebuvo nei didžiųjų raidžių, nei tarpų; jis buvo suplaktas taip, kad jame nebuvo perskaitomų fragmentų. Pradinis tekstas aprašė šifravimo būdą, tačiau nepateikė konkretaus rakto, reikalingo dešifravimui. Šifravimas nebuvo panašus į jokį kitą, naudojamą tuo metu. Patersonas spėjo, kad šifro niekas nenulauš. Jis tekstą surašė vertikaliais stulpeliais, suplakė horizontalias eilutes ir eilučių pradžiose įrašė papildomų raidžių. Raktas buvo skaičiai, nurodantys tvarką eilutėse bei papildomų raidžių kiekis kiekvienos eilutės pradžioje.

Tai buvo patraukli tema istorikams, o taip pat šifravimų entuziastams. Džefersonas, pats buvęs kriptografu, ėmėsi šifro su entuziazmu. Jis pasiūlė jį naudoti diplomatinėje korespondencijoje, tačiau kiti neįvertino jo perspėjimų dėl tuo menu naudojamų šifravimų silpnumo.

Minėtą šifrą 2007 m. įveikė Lawren Smithline (kuris tuo metu buvo 36 m. amžiaus), išdėstęs sprendimą „American Scientist“ žurnale. Sprendimas apėmė tiek lingvistinę intuiciją, tiek kompiuterinį algoritmą. Pareikalavęs 100 tūkst. paskaičiavimų, Smithline metodas buvo lengvas kąsnelis kompiuteriams – ir jis galėjo būti panaudotas ir Patersono laikais. Pasirodo, kad tai buvo Preambulė Nepliklausomybės deklaracijai.


*) Rudolfas Zaripovas (1929 - 1991) – tarybinis matematikas, dirbęs Psichologijos inst-te ir MA skaičiavimo centre. Užsiėmė mąstymo psichologijos matematinio modeliavimo klausimais, dirbtiniu intelektu, pavyzdžiu paėmęs muziką. Baigė Kazanės un-tą. Jis, išanalizavęs daug muzikinių fragmentų, teigė, kad, parinkus atitinkamas statistikas, galima suformuluoti taisykles, parodančias kaip veikia kompozitoriaus intuicija (nors G. Altšuleris tai padarė dar 6-me dešimtm. techninių išradimų srityje).

Erdvės formos
Monte-Karlo metodas
Kur viešpatauja chaosas?
Matematika ir biologija
Kaip supakuoti standžiau?
Iniciatyva: Matematikos keliu
Izingo modelis įmagnetinimui
Kolmogorovo DI alfa ir omega
Skaičiai B ir jų kvantinės sistemos
Tiuringas – liūdno likimo genijus
Paradoksai sulig dirbtiniu intelektu
P-NP: Ant sveiko proto svarstyklių
Kvantinė mechanika ir jos ribotumas
Džordžas Birkhofas - matematikas ir meno matuotojas
Intuicijos ribojimas matematikoje 19-me amžiuje
Kantoro aibių teorija ir tikrosios begalybės intuicija
Netiesinis mąstymas: išspręsti neišsprendžiamą
Semantinės derybos: Dviprasmybių modeliavimas
Laimėti pralaimint: „dviejų vokų“ paradoksas
Egzotiškosios hipersferos - problema išspręsta
D. Spielmanas gavo Nevanlinna premiją
Ultimatyvi logika: Iki begalybės ir toliau
Simpsonų trauka ir žaidimas skaičiais
Kvantinė chemija – ateities mokslas?
Naujas pirminių skaičių dėsningumas
Nepaprasti Visatos skaičiai
Dirbtinis intelektas kare
Nešo pusiausvyra
Smeilo paradoksas
Algebros istorija
Vartiklis