Kako delujejo kvantni računalniki. Sestavljanje sestavljanke
Kvantni računalniki in kvantno računalništvo - novo modna beseda, ki smo ga dodali v naš informacijski prostor skupaj z umetna inteligenca, strojno učenje in drugi visokotehnološki izrazi. Hkrati mi na internetu nikoli ni uspelo najti gradiva, ki bi sestavilo sestavljanko v moji glavi, imenovano "kako delujejo kvantni računalniki". Da, veliko je odličnih del, tudi na Habru (glej. Seznam virov), komentarji, ki so, kot je v navadi, še bolj informativni in koristni, vendar se slika v moji glavi, kot pravijo, ni sestavila.
In pred kratkim so moji kolegi prišli do mene in me vprašali: »Ali razumete, kako deluje kvantni računalnik? Nam lahko poveste?" In potem sem ugotovil, da nisem edini, ki ima težave s sestavljanjem koherentne slike v glavi.
Posledično je prišlo do poskusa zbrati informacije o kvantnih računalnikih v konsistentno logično vezje, v katerem osnovna raven, brez poglobljenega poglabljanja v matematiko in strukturo kvantnega sveta, je bilo pojasnjeno, kaj je kvantni računalnik, po kakšnih principih deluje in s kakšnimi težavami se srečujejo znanstveniki pri izdelavi in delovanju.
Avtor ni strokovnjak za kvantno računalništvo in Ciljna publika članka so isti IT ljudje, ne kvantni strokovnjaki, ki prav tako želijo v svojih glavah sestaviti sliko z naslovom "Kako delujejo kvantni računalniki." Zaradi tega so številni koncepti v članku namerno poenostavljeni, da bi bolje razumeli kvantne tehnologije na "osnovni" ravni, vendar brez zelo močna poenostavitev z izgubo informacijske vsebine in ustreznosti.
Članek na nekaterih mestih uporablja materiale iz drugih virov, katerih seznam je podan na koncu članka. Kjer je le mogoče, so vstavljene neposredne povezave in navedbe na izvirno besedilo, tabelo ali sliko. Če sem kje kaj pozabil (ali koga) napiši, bom popravil.
V tem poglavju si bomo na kratko ogledali, kako se je začela kvantna doba, kaj je bil motivacijski razlog za idejo o kvantnem računalniku, kdo (katere države in korporacije) so trenutno vodilni igralci na tem področju ter na kratko spregovorili o glavnih smereh razvoja kvantnega računalništva.
Za izhodišče kvantne dobe štejemo leto 1900, ko je M. Planck prvič predlagal hipoteza da se energija oddaja in absorbira ne neprekinjeno, ampak v ločenih kvantih (porcijah). Idejo so prevzeli in razvili številni izjemni znanstveniki tistega časa - Bohr, Einstein, Heisenberg, Schrödinger, kar je na koncu pripeljalo do nastanka in razvoja takšne znanosti, kot je kvantna fizika. Na internetu je veliko dobrih gradiv o nastanku kvantne fizike kot znanosti, v tem članku se o tem ne bomo podrobneje ukvarjali, vendar je bilo treba navesti datum, ko smo vstopili v novo kvantno dobo.
Kvantna fizika je v naš vsakdan prinesla številne izume in tehnologije, brez katerih si danes težko predstavljamo svet okoli nas. Na primer laser, ki se zdaj uporablja povsod, od gospodinjskih aparatov (laserske nivelire itd.) Do visokotehnoloških sistemov (laserji za korekcijo vida, zdravo meklon ). Logično bi bilo domnevati, da bo prej ali slej nekdo prišel na idejo, zakaj ne bi uporabili kvantnih sistemov za računalništvo. In potem se je leta 1980 zgodilo.
Wikipedia navaja, da je prvo idejo o kvantnem računalništvu leta 1980 izrazil naš znanstvenik Jurij Manin. Zares pa so o tem začeli govoriti šele leta 1981, ko je znani R. Feynman govor na prvi konferenci o računalniški fiziki na MIT, je opozoril, da je nemogoče simulirati razvoj kvantnega sistema na klasičnem računalniku na učinkovit način. Predlagal je osnovni model kvantni računalnik, ki bo sposoben izvajati takšno modeliranje.
Kot lahko vidite, je minilo 17 let (od 1981 do 1998) od trenutka ideje do njene prve izvedbe v računalniku z 2 kubiti in 21 let (od 1998 do 2019) do trenutka, ko se je število kubitov povečalo. do 53. Trajalo je 11 let (od 2001 do 2012), da smo izboljšali rezultat Shorovega algoritma (podrobneje si ga bomo ogledali malo kasneje) s številke 15 na 21. Šele pred tremi leti smo prišli do točke izvajati tisto, o čemer je govoril Feynman, in se naučiti modelirati najpreprostejše fizične sisteme.
Razvoj kvantnega računalništva je počasen. Znanstveniki in inženirji so postavljeni pred zelo težke naloge, kvantna stanja so zelo kratkotrajna in krhka, da pa se ohranijo dovolj dolgo za izračune, morajo zgraditi sarkofage za več deset milijonov dolarjev, v katerih se vzdržuje temperatura tik nad absolutno ničlo in ki so maksimalno zaščiteni pred zunanjimi vplivi. V nadaljevanju bomo podrobneje govorili o teh nalogah in težavah.
Vse tehnološko uspešne države trenutno aktivno razvijajo kvantne tehnologije. V te raziskave se vlaga ogromno denarja in nastajajo posebni programi za podporo kvantnim tehnologijam.
V kvantni tekmi ne sodelujejo le države, ampak tudi zasebna podjetja. Skupaj so Google, IBM, Intel in Microsoft nedavno vložili okoli 0,5 milijarde dolarjev v razvoj kvantnih računalnikov ter ustvarili velike laboratorije in raziskovalne centre.
Na Habréju in na internetu je veliko člankov, npr. glej, glej и glej, v katerem je podrobneje preučeno trenutno stanje z razvojem kvantnih tehnologij v različnih državah. Za nas je zdaj glavno, da vse vodilne tehnološko razvite države in akterji vlagajo ogromne količine denarja v raziskave v tej smeri, kar daje upanje za izhod iz trenutne tehnološke slepe ulice.
Trenutno (lahko se motim, popravite me) so glavni napori (in bolj ali manj pomembni rezultati) vseh vodilnih igralcev koncentrirani na dveh področjih:
Specializirani kvantni računalniki, ki so namenjeni reševanju določenega specifičnega problema, na primer optimizacijskega problema. Primer izdelka so kvantni računalniki D-Wave.
Univerzalni kvantni računalniki — ki so sposobni izvajati poljubne kvantne algoritme (Shor, Grover itd.). Implementacije IBM-a, Googla.
Drugi vektorji razvoja, ki nam jih daje kvantna fizika, kot so:
Najpomembnejša stvar, ki jo morate razumeti iz tega razdelka, je, da
Kvantni računalnik (za razliko od običajnih) uporablja kot nosilce informacij kvantni objekti, za izvedbo izračunov pa morajo biti kvantni objekti povezani kvantni sistem.
Kaj je kvantni objekt?
Kvantni objekt - objekt mikrosveta (kvantni svet), ki kaže kvantne lastnosti:
Ima definirano stanje z dvema mejnima nivojema
Je v superpoziciji svojega stanja do trenutka meritve
Zaplete se z drugimi predmeti, da ustvari kvantne sisteme
Zadovoljuje izrek o prepovedi kloniranja (stanja predmeta ni mogoče kopirati)
Oglejmo si vsako lastnost podrobneje:
Ima definirano stanje z dvema mejnima nivojema (končno stanje)
Klasičen primer iz resničnega sveta je kovanec. Ima "stransko" stanje, ki ima dve mejni ravni - "glave" in "repi".
Je v superpoziciji svojega stanja do trenutka meritve
Vrgli so kovanec, leti in se vrti. Medtem ko se vrti, je nemogoče reči, v katerem od mejnih nivojev se nahaja njegovo "stransko" stanje. Toda takoj, ko ga zalomimo in pogledamo rezultat, se superpozicija stanj takoj zruši v eno od dveh mejnih stanj - "glave" in "repi". Udarec kovanca je v našem primeru meritev.
Zaplete se z drugimi predmeti, da ustvari kvantne sisteme
S kovancem je težko, a poskusimo. Predstavljajte si, da vržemo tri kovance tako, da se vrtijo oprijeti drug drugega, to je žongliranje s kovanci. V vsakem trenutku ni le vsaka od njih v superpoziciji stanj, ampak ta stanja medsebojno vplivajo druga na drugo (kovanci trčijo).
Zadovoljuje izrek o prepovedi kloniranja (stanja predmeta ni mogoče kopirati)
Medtem ko kovanci letijo in se vrtijo, ne moremo ustvariti kopije stanja vrtenja katerega koli od kovancev, ločeno od sistema. Sistem živi v sebi in je zelo ljubosumen na sproščanje kakršnih koli informacij v zunanji svet.
Še nekaj besed o samem konceptu “superpozicije”, v skoraj vseh člankih je superpozicija razložena kot "je v vseh stanjih hkrati", kar je seveda res, a na trenutke po nepotrebnem zmedeno. Superpozicijo stanj si lahko predstavljamo tudi kot dejstvo, da ima kvantni objekt v vsakem trenutku obstajajo določene verjetnosti kolapsa v vsako od njenih mejnih ravni, v seštevku pa so te verjetnosti naravno enake 1. Kasneje, ko bomo obravnavali qubit, se bomo o tem podrobneje posvetili.
Za kovance je to mogoče vizualizirati - odvisno od začetne hitrosti, kota meta, stanja okolja, v katerem kovanec leti, je v vsakem trenutku verjetnost, da dobimo "glave" ali "repe", drugačna. In, kot smo že omenili, si lahko stanje takšnega letečega kovanca predstavljamo kot "v vseh svojih mejnih stanjih hkrati, vendar z različnimi verjetnostmi njihove uveljavitve."
Vsak objekt, za katerega so izpolnjene zgornje lastnosti in ga lahko ustvarimo in nadzorujemo, lahko uporabimo kot nosilec informacij v kvantnem računalniku.
Malo naprej bomo govorili o trenutnem stanju fizične implementacije kubitov kot kvantnih predmetov in o tem, kaj znanstveniki zdaj uporabljajo v tej vlogi.
Torej tretja lastnost pravi, da se lahko kvantni objekti zapletejo in ustvarijo kvantne sisteme. Kaj je kvantni sistem?
Kvantni sistem — sistem zapletenih kvantnih objektov z naslednjimi lastnostmi:
Kvantni sistem je v superpoziciji vseh možnih stanj objektov, iz katerih je sestavljen
Nemogoče je vedeti stanje sistema do trenutka meritve
V trenutku merjenja sistem izvaja eno od možnih variant svojih mejnih stanj
(in če pogledam malo naprej)
Posledica za kvantne programe:
Kvantni program ima dano stanje sistema na vhodu, superpozicijo znotraj, superpozicijo na izhodu
Na izhodu programa po meritvi imamo verjetnostno izvedbo enega od možnih končnih stanj sistema (plus možne napake)
Vsak kvantni program ima arhitekturo dimnika (vhod -> izhod. Ni zank, ne morete videti stanja sistema sredi procesa.)
Zdaj pa primerjajmo običajni in kvantni računalnik.
navaden računalnik
Kvantni računalnik
Logika
0 / 1
`a|0> + b|1>, a^2+b^2=1`
Fizika
Polprevodniški tranzistor
Kvantni objekt
Medijski nosilec
Ravni napetosti
Polarizacija, spin,…
Operacije
NE, IN, ALI, XOR nad biti
Ventili: CNOT, Hadamard,…
Medsebojno povezovanje
Polprevodniški čip
Zmeda drug z drugim
Algoritmi
Standard (glej Whip)
Posebne (Shore, Grover)
Načelo
Digitalno, deterministično
Analogno, verjetnostno
Logična raven
V navadnem računalniku je to malo. Nam dobro znano naokoli deterministični bit. Lahko sprejme vrednosti 0 ali 1. Popolnoma se spopada z vlogo logična enota za običajen računalnik, vendar je popolnoma neprimeren za opis stanja kvantni objekt, ki se, kot smo že povedali, v divjini nahaja vsuperpozicije njihovih mejnih stanj.
To so prišli do tega qubit. V svojih mejnih stanjih realizira stanja, podobna 0 in 1 |0> in |1>, in v superpoziciji predstavlja porazdelitev verjetnosti po svojih mejnih stanjih|0> и |1>:
a|0> + b|1>, такое, что a^2+b^2=1
a in b predstavljata amplitude verjetnosti, kvadrati njihovih modulov pa so dejanske verjetnosti, da dobimo natanko takšne vrednosti mejnih stanj |0> и |1>, če qubit z meritvijo prav zdaj strnete.
Fizični sloj
Na trenutni tehnološki stopnji razvoja je fizična izvedba bita za običajen računalnik polprevodniški tranzistor, za kvant, kot smo že povedali, katerikoli kvantni objekt. V naslednjem razdelku bomo govorili o tem, kaj se trenutno uporablja kot fizični medij za kubite.
Medij za shranjevanje
Za navaden računalnik je to električni tok - nivoji napetosti, prisotnost ali odsotnost toka itd., za kvantne - enako stanje kvantnega objekta (smer polarizacije, spin itd.), ki je lahko v stanju superpozicije.
Operacije
Za izvedbo logičnih vezij na običajnem računalniku uporabljamo dobro znane logične operacije, je bilo za operacije na kubitih treba pripraviti povsem drugačen sistem operacij, imenovan kvantna vrata. Vrata so lahko eno-kubitna ali dvojna-kubitna, odvisno od tega, koliko kubitov se pretvori.
Primeri kvantnih vrat:
Obstaja koncept univerzalni set ventilov, ki zadoščajo za kakršen koli kvantni izračun. Na primer, univerzalni niz vključuje Hadamardova vrata, vrata za fazni zamik, vrata CNOT in vrata π⁄8. Z njihovo pomočjo lahko izvedete poljuben kvantni izračun na poljubni množici kubitov.
V tem članku se ne bomo podrobneje ukvarjali s sistemom kvantnih vrat, več o njih in logičnih operacijah na kubitih si lahko preberete npr. tukaj. Glavna stvar, ki si jo morate zapomniti:
Operacije na kvantnih objektih zahtevajo ustvarjanje novih logičnih operaterjev (kvantnih vrat).
Kvantna vrata so eno-kubitna in dvojno-kubitna tipa.
Obstajajo univerzalni nizi vrat, ki jih je mogoče uporabiti za izvajanje katerega koli kvantnega računanja
Medsebojno povezovanje
En tranzistor je za nas popolnoma neuporaben; za izračune moramo med seboj povezati veliko tranzistorjev, torej iz milijonov tranzistorjev ustvariti polprevodniški čip, na katerem bomo zgradili logična vezja, ALU in na koncu dobili sodoben procesor v klasični obliki.
Tudi en kubit je za nas popolnoma neuporaben (no, če le v akademskem smislu),
za izvedbo izračunov potrebujemo sistem kubitov (kvantnih objektov)
ki, kot smo že povedali, nastane s prepletanjem kubitov med seboj, tako da se spremembe v njihovih stanjih dogajajo usklajeno.
Algoritmi
Standardni algoritmi, ki jih je človeštvo nabralo do danes, so popolnoma neprimerni za implementacijo na kvantnem računalniku. Da, na splošno ni potrebe. Kvantni računalniki, ki temeljijo na logiki vrat prek kubitov, zahtevajo ustvarjanje popolnoma drugačnih algoritmov, kvantnih algoritmov. Od najbolj znanih kvantnih algoritmov lahko ločimo tri:
In najpomembnejša razlika je načelo delovanja. Za standardni računalnik je to digitalno, strogo deterministično načelo, ki temelji na dejstvu, da če nastavimo neko začetno stanje sistema in ga prenesemo skozi dani algoritem, potem bo rezultat izračunov enak, ne glede na to, kolikokrat izvedemo ta izračun. Pravzaprav je to vedenje točno tisto, kar pričakujemo od računalnika.
Kvantni računalnik deluje naprej analogni, verjetnostni princip. Rezultat danega algoritma v danem začetnem stanju je vzorec iz verjetnostne porazdelitve končne izvedbe algoritma plus možne napake.
Ta verjetnostna narava kvantnega računalništva je posledica samega verjetnostnega bistva kvantnega sveta. "Bog se ne kocka z vesoljem.", je rekel stari Einstein, a vsi dosedanji poskusi in opazovanja (v trenutni znanstveni paradigmi) potrjujejo nasprotno.
Kot smo že povedali, lahko kubit predstavljamo s kvantnim objektom, torej fizičnim objektom, ki izvaja zgoraj opisane kvantne lastnosti. To je, grobo rečeno, vsak fizični objekt, v katerem sta dve stanji in sta ti dve stanji v stanju superpozicije, se lahko uporabi za izdelavo kvantnega računalnika.
»Če lahko postavimo atom na dve različni ravni in ju nadzorujemo, potem imate kubit. Če lahko to naredimo z ionom, je to kubit. Enako je s tokom. Če ga zaženemo v smeri urinega kazalca in nasprotni smeri urinega kazalca hkrati, imate qubit.«(C)
Obstaja čudovit komentar к članek, v katerem je podrobneje obravnavana trenutna raznolikost fizičnih izvedb kubita, bomo le našteli najbolj znane in pogoste:
Od vse te sorte je najbolj razvita prva metoda pridobivanja kubitov, ki temelji na superprevodniki. google, IBM, Intel in drugi vodilni igralci ga uporabljajo za gradnjo svojih sistemov.
Torej, predstavljajte si, da imamo naslednjo nalogo:
Obstaja skupina treh ljudi: (A)ndrey, (B)olodya in (C)erezha. Obstajata dva taksija (0 in 1).
Znano je tudi, da:
(A)ndrey, (B)olodya sta prijatelja
(A)ndrey, (C)erezha sta sovražnika
(B)olodya in (C)erezha sta sovražnika
Naloga: Postavite ljudi v taksije tako, da Max (prijatelji) и Min (sovražniki)
Ocena: L = (število prijateljev) - (število sovražnikov) za vsako namestitveno možnost
POMEMBNO: Ob predpostavki, da ni hevristike, ni optimalne rešitve. V tem primeru je težavo mogoče rešiti le s popolnim iskanjem možnosti.
Rešitev na običajnem računalniku
Kako rešiti to težavo na običajnem (super) računalniku (ali grozdu) - to je jasno prebrskati morate vse možne možnosti. Če imamo večprocesorski sistem, potem lahko paraleliziramo izračun rešitev na več procesorjih in nato zbiramo rezultate.
Imamo 2 možni možnosti namestitve (taxi 0 in taxi 1) in 3 osebe. Prostor rešitve 2^3 = 8. S kalkulatorjem lahko celo preberete 8 možnosti, to ni problem. Zdaj pa zapletimo problem - imamo 20 ljudi in dva avtobusa, prostor za rešitev 2^20 = 1. Tudi nič zapletenega. Povečajmo število ljudi za 2.5-krat - vzemimo 50 ljudi in dva vlaka, rešitev prostor je zdaj 2^50 = 1.12 x 10^15. Navaden (super)računalnik ima že resne težave. Povečajmo število ljudi za 2-krat, 100 ljudi nam bo že dalo 1.2 x 10^30 možne možnosti.
To je to, te naloge ni mogoče izračunati v razumnem času.
Priključitev superračunalnika
Trenutno najmočnejši računalnik je številka 1 Top500je Vrh, produktivnost 122 Pflops. Predpostavimo, da potrebujemo 100 operacij za izračun ene možnosti, nato pa bomo za rešitev problema za 100 ljudi potrebovali:
(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 x 10^37 let.
Kot lahko vidimo ko se dimenzija začetnih podatkov povečuje, prostor rešitev raste po potenčnem zakonu, v splošnem primeru imamo za N bitov 2^N možnih možnosti rešitve, ki nam za razmeroma majhne N (100) dajo neizračunan (na trenutni tehnološki ravni) prostor rešitev.
Ali obstajajo kakšne alternative? Kot ste morda uganili, da, obstaja.
Toda preden se lotimo tega, kako in zakaj lahko kvantni računalniki učinkovito rešujejo težave, kot so ti, si vzemimo trenutek in povzamemo, kaj so. porazdelitev verjetnosti. Naj vas ne skrbi, to je pregledni članek, tu ne bo težke matematike, zadovoljili se bomo s klasičnim primerom z vrečo in žogami.
Samo malo kombinatorike, teorije verjetnosti in čuden eksperimentator
Vzamemo vrečko in jo damo vanjo 1000 belih in 1000 črnih kroglic. Izvedli bomo poskus - vzeli kroglico, zapisali barvo, vrnili kroglico v vrečko in premešali kroglice v vrečki.
Poskus je bil izveden 10-krat, izvlekel 10 črnih kroglic. morda? Čisto. Ali nam ta vzorec daje kakšno razumno predstavo o resnični porazdelitvi v vrečki? Očitno ne. Kaj je treba narediti – prav, strposkus ponovite milijonkrat in izračunajte frekvence črnih in belih kroglic. Dobimo npr 49.95 % črna in 50.05 % bela. V tem primeru je struktura porazdelitve, iz katere vzorčimo (odvzamemo eno kroglico), že bolj ali manj jasna.
Glavna stvar je razumeti to sam eksperiment ima verjetnostno naravo, z enim vzorcem (kroglo) ne bomo poznali prave strukture porazdelitve, poskus moramo večkrat ponoviti in povprečite rezultate.
Dodajmo ga v torbo 10 rdečih in 10 zelenih žog (napake). Poskus ponovimo 10-krat. INizvlekel 5 rdečih in 5 zelenih. morda? ja Lahko rečemo nekaj o pravi distribuciji - Ne. Kaj je treba storiti - no, razumete.
Da bi razumeli strukturo verjetnostne porazdelitve, je treba večkrat vzorčiti posamezne rezultate iz te porazdelitve in povprečiti rezultate.
Povezovanje teorije s prakso
Zdaj pa namesto črno-belih krogel vzemimo biljardne krogle in jih pospravimo v vrečko 1000 žog s številko 2, 1000 s številko 7 in 10 žog z drugimi številkami. Predstavljajmo si eksperimentatorja, ki je izurjen v najpreprostejših dejanjih (vzame žogico, zapiše številko, vrne žogico v vrečko, premeša kroglice v vrečki) in to naredi v 150 mikrosekundah. No, tak eksperimentator na hitrosti (ni reklama za zdravila!!!). Nato bo v 150 sekundah lahko izvedel naš poskus 1 milijonkrat in nam posredujte rezultate povprečja.
Eksperimentatorja so posedli, mu dali vrečko, se obrnili stran, počakali 150 sekund in prejeli:
Da, tako je, naša torba je kvantni računalnik z algoritmom, ki rešuje naš problem, žoge pa so možne rešitve. Ker sta torej dve pravilni rešitvi kvantni računalnik nam bo dal katero koli od teh možnih rešitev z enako verjetnostjo in 0.5 % (10/2000) napakami, o katerem bomo govorili kasneje.
Če želite dobiti rezultat kvantnega računalnika, morate večkrat zagnati kvantni algoritem na istem nizu vhodnih podatkov in povprečiti rezultat.
Razširljivost kvantnega računalnika
Zdaj si predstavljajte, da za nalogo, ki vključuje 100 ljudi (prostor rešitve 2^100 tega se spomnimo), sta tudi samo dve pravilni odločitvi. Potem, če vzamemo 100 kubitov in napišemo algoritem, ki izračuna našo ciljno funkcijo (L, glej zgoraj) nad temi kubiti, potem bomo dobili vrečko, v kateri bo 1000 kroglic s številko prvega pravilnega odgovora, 1000 s številko drugega pravilnega odgovora in 10 žogic z drugimi številkami. In v istih 150 sekundah nam bo naš eksperimentator dal oceno porazdelitve verjetnosti pravilnih odgovorov.
Čas izvajanja kvantnega algoritma (z nekaterimi predpostavkami) lahko štejemo za konstanto O(1) glede na dimenzijo prostora rešitev (2^N).
In prav to je lastnost kvantnega računalnika - konstantnost delovanja v povezavi z naraščajočo potenčno zakonodajo kompleksnost prostora rešitev je ključna.
Qubit in vzporedni svetovi
Kako se to zgodi? Kaj omogoča kvantnemu računalniku, da tako hitro izvaja izračune? Vse je v kvantni naravi qubita.
Poglejte, rekli smo, da je qubit kot kvantni objekt ob opazovanju spozna eno od svojih dveh stanj, v “divji naravi” pa je v superpozicije stanj, to pomeni, da je v obeh svojih mejnih stanjih hkrati (z nekaj verjetnosti).
Vzemi (A)ndreja in si predstavljajte njegovo stanje (v katerem vozilu je - 0 ali 1) kot qubit. Potem imamo (v kvantnem prostoru) dva vzporedna svetova, v enem (A) sedi v taksiju 0, v drugem svetu - v taksiju 1. V dveh taksijih hkrati, vendar z nekaj verjetnosti, da ga med opazovanjem najdemo v vsakem od njih.
Vzemi (B) mlad in si predstavljajmo tudi njegovo stanje kot qubit. Nastaneta še dva vzporedna svetova. Ampak za zdaj ti pari svetov (A) и (AT) sploh ne komunicirajo. Kaj je treba storiti za ustvarjanje povezano sistem? Tako je, te kubite potrebujemo zvezati (zmešati). Vzamemo in zmedemo (A) z (B) — dobimo kvantni sistem dveh kubitov (A, B), v sebi uresničuje štiri soodvisni vzporedni svetovi. Dodaj (S)ergej in dobimo sistem treh kubitov (ABC), izvajanje osmih soodvisni vzporedni svetovi.
Bistvo kvantnega računalništva (izvedba verige kvantnih vrat nad sistemom povezanih kubitov) je dejstvo, da se izračun zgodi v vseh vzporednih svetovih hkrati.
In ni pomembno, koliko jih imamo, 2^3 ali 2^100, kvantni algoritem se bo izvajal v končnem času nad vsemi temi vzporednimi svetovi in nam bo dal rezultat, ki je vzorec iz porazdelitve verjetnosti odgovorov algoritma.
Za boljše razumevanje si lahko to predstavljamo kvantni računalnik na kvantni ravni izvaja 2^N vzporednih procesov reševanja, od katerih vsak dela na eni možni možnosti, nato zbira rezultate dela - in nam poda odgovor v obliki superpozicije rešitve (verjetnostna porazdelitev odgovorov), iz katere vsakokrat vzorčimo enega (za vsak poskus).
Zapomnite si čas, ki ga potrebuje naš eksperimentator (150 µs) za izvedbo eksperimenta, nam bo to koristilo malo naprej, ko bomo govorili o glavnih problemih kvantnih računalnikov in dekoherenčnem času.
Kot že omenjeno, običajni algoritmi, ki temeljijo na binarni logiki, niso uporabni za kvantni računalnik, ki uporablja kvantno logiko (kvantna vrata). Zanj je bilo treba pripraviti nove, ki v celoti izkoriščajo potencial kvantne narave računalništva.
Za razliko od klasičnih kvantni računalniki niso univerzalni. Do sedaj je bilo najdenih le majhno število kvantnih algoritmov.(C)
Hvala oksoron za povezavo do Kvantni algoritem Zoo, kraj, kjer je po mnenju avtorja ("Stephen Jordan"), najboljši predstavniki kvantno-algoritemskega sveta so bili zbrani in se še naprej zbirajo.
V tem članku ne bomo podrobno analizirali kvantnih algoritmov, na internetu je veliko odličnih materialov za vse stopnje kompleksnosti, vendar moramo še vedno na kratko pregledati tri najbolj znane.
Najbolj znan kvantni algoritem je Shorov algoritem (izumil ga je leta 1994 angleški matematik Peter Shore), ki je namenjen reševanju problema faktorizacije števil na prafaktorje (problem faktorizacije, diskretni logaritem).
Prav ta algoritem navajajo kot primer, ko pišejo, da bodo kmalu vdrli v vaše bančne sisteme in gesla. Glede na to, da dolžina ključev, ki se danes uporabljajo, ni manjša od 2048 bitov, čas za omejitev še ni prišel.
Do danes Rezultati več kot skromno. Najboljši rezultati faktorizacije s Shorovim algoritmom - številke 15 и 21, kar je veliko manj kot 2048 bitov. Za preostale rezultate iz tabele pa drugače algoritem izračuni, vendar je tudi najboljši rezultat po tem algoritmu (291311) zelo daleč od realne uporabe.
Več o Shorjevem algoritmu lahko preberete na primer tukaj. O praktični izvedbi - tukaj.
Eden od trenutne ocene Kompleksnost in potrebna moč za faktoriziranje 2048-bitnega števila ima računalnik 20 milijonov kubitov. Mirno spimo.
Za iskanje se lahko uporabi Groverjev algoritem mediane и aritmetična sredina številske serije. Poleg tega se lahko uporablja za reševanje NP-popoln težave z izčrpnim iskanjem med številnimi možnimi rešitvami. To lahko pomeni znatno povečanje hitrosti v primerjavi s klasičnimi algoritmi, čeprav brez zagotavljanja "polinomska rešitev" na splošno.(C)
Lahko preberete več tukajAli tukaj. Več tukaj Obstaja dobra razlaga algoritma na primeru škatel in žoge, toda na žalost se zaradi razlogov, ki niso pod nadzorom nikogar, to spletno mesto ne odpre zame iz Rusije. Če imate to spletno mesto je tudi blokiran, zato je tukaj kratek povzetek:
Groverjev algoritem. Predstavljajte si, da imate N kosov oštevilčenih zaprtih škatel. Vsi so prazni, razen enega, v katerem je žoga. Vaša naloga: ugotovite številko škatle, v kateri je žogica (to neznano število je pogosto označeno s črko w).
Kako rešiti ta problem? Najbolj neumno je, da izmenično odpirate škatle in prej ali slej naletite na škatlo z žogico. Koliko polj je treba v povprečju preveriti, preden se najde škatla z žogico? V povprečju morate odpreti približno polovico N/2 škatel. Glavna stvar pri tem je, da če povečamo število škatel za 100-krat, se bo povprečno število škatel, ki jih je treba odpreti, preden se najde škatla z žogico, povečalo za enakih 100-krat.
Zdaj pa naredimo še eno pojasnilo. Ne odpirajmo škatel sami z rokami in preverjajmo prisotnost žoge v vsaki, vendar obstaja določen posrednik, recimo mu Oracle. Oracleju rečemo "potrditveno polje številka 732," in Oracle pošteno preveri in odgovori, "v polju številka 732 ni žogice." Zdaj, namesto da povemo, koliko škatel moramo v povprečju odpreti, rečemo "kolikokrat v povprečju bi morali iti do Oraklja, da bi našli številko škatle z žogico".
Izkazalo se je, da če to težavo s škatlami, kroglo in orakljem prevedemo v kvantni jezik, dobimo izjemen rezultat: če želimo najti številko škatle s kroglo med N škatlami, moramo orakelj motiti le okoli SQRT (N)-krat!
To pomeni, da se kompleksnost iskalne naloge z uporabo Groverjevega algoritma zmanjša za kvadratni koren iz časa.
Deutsch-Jozsi problem je ugotoviti, ali je funkcija več binarnih spremenljivk F(x1, x2, ... xn) konstantna (zavzame vrednost 0 ali 1 za kateri koli argument) ali uravnotežena (za polovico domene potrebuje vrednost 0, za drugo polovico 1). V tem primeru velja, da je a priori znano, da je funkcija konstantna ali uravnotežena.(C)
Algoritem Deutsch (Deutsch-Jozsi) temelji na surovi sili, vendar omogoča, da se izvede hitreje kot običajno. Predstavljajte si, da je na mizi kovanec in morate ugotoviti, ali je ponarejen ali ne. Če želite to narediti, morate dvakrat pogledati kovanec in ugotoviti: "glave" in "repi" so resnični, dve "glavi", dva "repa" sta lažna. Torej, če uporabljate Deutschov kvantni algoritem, potem lahko to določitev izvedete z enim pogledom - meritvijo.(C)
Pri načrtovanju in delovanju kvantnih računalnikov se znanstveniki in inženirji soočajo z ogromno težavami, ki so bile do danes rešene z različno uspešnostjo. Po navedbah raziskave (in tudi tukaj) je mogoče prepoznati naslednjo vrsto težav:
Kvantno stanje zelo krhka stvarkubiti v zapletenem stanju so izjemno nestabilni, vsak zunanji vpliv lahko (in tudi uniči) to povezavo. Sprememba temperature za najmanjši del stopinje, tlak, naključni foton, ki leti v bližini - vse to destabilizira naš sistem.
Za rešitev tega problema se gradijo nizkotemperaturni sarkofagi, v katerih je temperatura (-273.14 stopinj Celzija) malo nad absolutno ničlo, z maksimalno izolacijo notranje komore s procesorjem od vseh (morebitnih) vplivov zunanjega okolja.
Največja življenjska doba kvantnega sistema več zapletenih kubitov, med katero ohrani svoje kvantne lastnosti in se lahko uporablja za izračune, se imenuje dekoherenčni čas.
Trenutno je dekoherenčni čas v najboljših kvantnih raztopinah reda velikosti desetine in stotine mikrosekund.
Točnih podatkov o Sycamoreju nisem našel, v večini pa članek o kvantni nadvladi podani sta dve številki - 1 milijon izračunov v 200 sekundah, na drugem mestu - za 130 sekund brez izgube krmilnih signalov itd.. V vsakem primeru nam to daje dekoherenčni čas je približno 150 μs. Zapomnite si naše eksperimentator z vrečko? No, tukaj je.
računalnik Ime
N kubitov
Max seznanjen
T2 (µs)
IBM Q System One
20
6
70
Google Sycamore
53
4
~ 150-200
S čim nam grozi dekoherenca?
Glavna težava je, da bo po 150 μs naš računalniški sistem N zapletenih kubitov začel oddajati verjetnostni beli šum namesto verjetnostne porazdelitve pravilnih rešitev.
Se pravi, potrebujemo:
Inicializirajte sistem qubit
Izvedite izračun (veriga operacij vrat)
Preberite rezultat
In vse to naredite v 150 mikrosekundah. Nisem imel časa - rezultat se je spremenil v bučo.
Kot smo rekli, kvantni procesi in kvantno računalništvo so verjetnostne narave, o ničemer ne moremo biti 100% prepričani, ampak samo z neko verjetnostjo. Položaj še dodatno poslabšuje dejstvo, da kvantno računalništvo je nagnjeno k napakam. Glavne vrste napak v kvantnem računalništvu so:
Napake dekoherence povzročajo kompleksnost sistema in interakcija z zunanjim okoljem
Napake, povezane z dekoherenco, se pojavijo takoj, ko zapletemo naše kubite in začnemo računati. Več kubitov kot zapletemo, bolj zapleten je sistem, in lažje ga je uničiti. Nizkotemperaturni sarkofagi, zaščitene komore, vsi ti tehnološki triki so namenjeni ravno zmanjšanju števila napak in podaljšanju časa dekoherence.
Računske napake vrat - vsaka operacija (vrata) na kubitih se lahko z neko verjetnostjo konča z napako, za implementacijo algoritma pa moramo izvesti na stotine vrat, zato si predstavljajte, kaj dobimo na koncu izvajanja našega algoritma. Klasičen odgovor na vprašanje je "Kakšna je verjetnost, da srečamo dinozavra v dvigalu?" - 50x50, ali se boste srečali ali ne.
Težavo dodatno otežuje dejstvo, da standardne metode odpravljanja napak (podvajanje izračunov in povprečenje) v kvantnem svetu zaradi izreka o prepovedi kloniranja ne delujejo. Za popravek napak v kvantnem računalništvu je bilo treba izumiti metode kvantne korekcije. Grobo rečeno, vzamemo N navadnih kubitov in naredimo enega od njih logični qubit z nižjo stopnjo napak.
Tu pa se pojavi še ena težava - skupno število kubitov. Poglejte, recimo, da imamo procesor s 100 kubiti, od katerih se 80 kubitov uporablja za popravljanje napak, potem nam jih ostane le še 20 za izračune.
Napake pri branju končnega rezultata — kot se spomnimo, nam je rezultat kvantnih izračunov predstavljen v obliki verjetnostna porazdelitev odgovorov. Toda branje končnega stanja lahko tudi ne uspe z napako.
Na istem Online Obstajajo primerjalne tabele procesorjev po stopnjah napak. Za primerjavo vzemimo iste procesorje kot v prejšnjem primeru - IBM IBM Q System One и Google Sycamore:
računalnik
1-Qubit Gate Fidelity
2- Qubit Gate Fidelity
Zvestoba branja
IBM Q System One
99.96%
98.31%
-
Google Sycamore
99.84%
99.38%
96.2%
Tukaj zvestoba je merilo podobnosti dveh kvantnih stanj. Velikost napake je mogoče grobo izraziti kot 1-Fidelity. Kot lahko vidimo, so napake na 2-kubitnih vratih in napake pri branju glavna ovira za izvajanje kompleksnih in dolgih algoritmov na obstoječih kvantnih računalnikih.
V teoriji gradimo in upravljamo vezja desetin zapletenih kubitov, v resnici je vse bolj zapleteno. Vsi obstoječi kvantni čipi (procesorji) so zgrajeni tako, da zagotavljajo neboleče prepletenost enega kubita samo s sosednjimi, ki jih ni več kot šest.
Če moramo zaplesti 1. kubit, recimo, z 12., potem bomo morali zgraditi verigo dodatnih kvantnih operacij, vključujejo dodatne kubite itd., kar poveča splošno stopnjo napake. Da, in ne pozabite dekoherenčni čas, morda do trenutka, ko končate povezovanje kubitov v vezje, ki ga potrebujete, se bo čas končal in celotno vezje se bo spremenilo v lep generator belega šuma.
Tudi tega ne pozabite Arhitektura vseh kvantnih procesorjev je drugačna, program, ki je napisan v emulatorju v načinu »povezljivost vseh za vse«, pa bo treba »rekompilirati« v arhitekturo določenega čipa. Obstajajo celo posebni programi za optimizacijo za izvedbo te operacije.
Največja povezljivost in največje število kubitov za iste vrhunske čipe:
računalnik Ime
N kubitov
Max seznanjen
T2 (µs)
IBM Q System One
20
6
70
Google Sycamore
53
4
~ 150-200
In za primerjavo, tabela s podatki iz prejšnje generacije procesorjev. Primerjajte število kubitov, čas dekoherence in stopnjo napak s tem, kar imamo zdaj z novo generacijo. Kljub temu je napredek počasen, a premikajoč se.
Torej:
Trenutno ni popolnoma povezanih arhitektur z > 6 kubiti
Za zapletanje qubit 0 s na resničnem procesorju lahko na primer qubit 15 zahteva več deset dodatnih operacij
Več operacij -> več napak -> močnejši vpliv dekoherence
Dekoherenca je Prokrustovo ležišče sodobnega kvantnega računalništva. Vse moramo umestiti v 150 μs:
Inicializacija začetnega stanja kubitov
Računanje problema z uporabo kvantnih vrat
Popravite napake, da dobite pomembne rezultate
Preberite rezultat
Zaenkrat pa so rezultati razočarajoči tukaj trdijo, da na kvantnem računalniku, ki temelji na ionske pasti:
Izmerimo koherentni čas kubitov, ki presega 0.5 s, z magnetno zaščito pa pričakujemo, da bo ta izboljšava daljša od 1000 s
Preberete lahko tudi o tej tehnologiji tukaj ali na primer tukaj.
Situacijo dodatno zaplete dejstvo, da je pri izvajanju kompleksnih izračunov treba uporabiti vezja za kvantno odpravljanje napak, kar prav tako žre tako čas kot razpoložljive kubite.
In končno, sodobne arhitekture ne dovoljujejo izvajanja shem zapletanja, boljših od 1 od 4 ali 1 od 6 z minimalnimi stroški.
Za rešitev zgoraj navedenih težav se trenutno uporabljajo naslednji pristopi in metode:
Uporaba kriokomor z nizkimi temperaturami (10 mK (–273,14 °C))
Uporaba procesorskih enot, ki so maksimalno zaščitene pred zunanjimi vplivi
Uporaba kvantnih sistemov za odpravljanje napak (Logic Qubit)
Uporaba optimizatorjev pri programiranju vezij za določen procesor
Potekajo tudi raziskave, namenjene povečanju časa dekoherence, iskanju novih (in izboljšanju znanih) fizikalnih izvedb kvantnih objektov, optimizaciji korekcijskih vezij itd., itd. Napredek je (poglejte zgoraj značilnosti prejšnjih in današnjih vrhunskih čipov), vendar je zaenkrat počasen, zelo, zelo počasen.
D-Wave 2000Q 2000-kubitni računalnik. Vir: D-Wave sistemi
Sredi Googlove napovedi o doseganju kvantne premoči z uporabo 53-kubitnega procesorja, računalniki и obvestila iz podjetja D-Wave, v katerem se število kubitov meri v tisočih, nekoliko zmoti. No, res, če je 53 kubitov uspelo doseči kvantno premoč, česa je potem zmožen računalnik z 2048 kubiti? A ni vse tako dobro...
Na kratko (povzeto iz wikija):
Računalniki D-Wave delo po principu kvantna sprostitev (kvantno žarjenje), lahko rešijo zelo omejen podrazred optimizacijskih problemov in niso primerni za izvajanje tradicionalnih kvantnih algoritmov in kvantnih vrat.
Za več podrobnosti si lahko preberete npr. tukaj, tukaj (previdno, morda se ne odpira iz Rusije), oz Scott Aaronson в članek od njegovega objava v spletnem dnevniku. Mimogrede, zelo priporočam branje njegovega bloga na splošno, tam je veliko dobrega materiala
Na splošno je imela znanstvena skupnost od samega začetka objav vprašanja o računalnikih D-Wave. Na primer, leta 2014 je IBM podvomil v dejstvo, da D-Wave uporablja kvantne učinke. Prišlo je do te točke, da je leta 2015 Google skupaj z Naso kupil enega od teh kvantnih računalnikov in po raziskavi potrjeno, da ja, računalnik dela in izračuna problem hitreje kot navaden. Več o Googlovi izjavi si lahko preberete tukaj in npr. tukaj.
Glavna stvar je, da računalnikov D-Wave z njihovimi stotinami in tisoči kubitov ni mogoče uporabiti za izračun in izvajanje kvantnih algoritmov. Na njih na primer ne morete zagnati Shorovega algoritma. Vse, kar lahko storijo, je uporaba določenih kvantnih mehanizmov za rešitev določene optimizacijske težave. Lahko štejemo, da je D-Wave kvantni ASIC za določeno nalogo.
Po delovanju - za natančno emulacijo 49-kubitnega vezja, sestavljenega iz približno 39 "ciklov" (neodvisnih plasti vrat) je vzelo 2^63 kompleksnih množenj - 4 Pflops superračunalnika za 4 ure
Posnemanje 50+ kubitnega kvantnega računalnika na klasičnih sistemih velja za nemogoče v razumnem času. Tudi zato je Google uporabil 53-kubitni procesor za svoj eksperiment kvantne premoči.
Wikipedia nam daje naslednjo definicijo nadvlade kvantnega računalništva:
Kvantna premoč – sposobnost kvantno računalništvo naprave za reševanje problemov, ki jih klasični računalniki praktično ne morejo rešiti.
Pravzaprav doseganje kvantne nadmoči pomeni, da je na primer faktorizacijo velikih števil z algoritmom Shor mogoče rešiti v ustreznem času ali pa je mogoče kompleksne kemične molekule emulirati na kvantni ravni itd. Se pravi, nastopilo je novo obdobje.
Toda v besedilu definicije je nekaj vrzeli, "ki jih klasični računalniki praktično ne morejo rešiti" Pravzaprav to pomeni, da če ustvarite kvantni računalnik s 50+ kubiti in na njem poženete neko kvantno vezje, potem, kot smo razpravljali zgoraj, rezultata tega vezja ni mogoče posnemati na običajnem računalniku. To je klasičen računalnik ne bo mogel poustvariti rezultata takega vezja.
Spletni članki Sycamore se pogosto nanašajo na 54-kubitni procesor ali 53-kubitni procesor. Resnica je, da glede na izvirni članek, je procesor fizično sestavljen iz 54 kubitov, vendar eden od njih ne deluje in je bil umaknjen iz uporabe. Tako imamo v resnici 53-kubitni procesor.
IBM-ova ekipa za kvantno računalništvo je to kasneje izjavila Google je lažno poročal o doseganju kvantne premoči. Družba trdi, da bo običajen računalnik tej nalogi v najslabšem primeru kos v 2,5 dneh, rezultat pa bo natančnejši od odgovora kvantnega računalnika. Ta sklep je bil narejen na podlagi rezultatov teoretične analize več optimizacijskih metod.
Kaj je Google pravzaprav naredil? Za podrobnejše razumevanje preberite Aaronsona, vendar na kratko tukaj:
Seveda ti lahko povem, ampak počutim se precej neumno. Izračun je naslednji: eksperimentator ustvari naključno kvantno vezje C (tj. naključno zaporedje 1-kubitnih in 2-kubitnih vrat med najbližjimi sosedi z globino na primer 20, ki delujejo na 2D mrežo n = 50-60 kubitov). Eksperimentator nato pošlje C kvantnemu računalniku in ga prosi, naj uporabi C v začetnem stanju 0, izmeri rezultat v osnovi {0,1}, pošlje nazaj n-bitno opazovano zaporedje (niz) in ponovi več tisoč ali milijonkrat. Končno eksperimentator s svojim znanjem C izvede statistični test, da ugotovi, ali se rezultat ujema s pričakovanim rezultatom kvantnega računalnika.
Zelo na kratko:
Naključno vezje dolžine 20 od 53 kubitov je ustvarjeno z uporabo vrat
Vezje se začne z začetnim stanjem [0…0] za izvedbo
Izhod vezja je naključni bitni niz (vzorec)
Porazdelitev rezultata ni naključna (interferenca)
Porazdelitev dobljenih vzorcev primerjamo s pričakovano
Zaključuje Quantum Supremacy
To pomeni, da je Google implementiral sintetični problem na 53-kubitnem procesorju in svojo trditev o doseganju kvantne premoči utemeljuje z dejstvom, da je nemogoče posnemati tak procesor na standardnih sistemih v razumnem času.
Za razumevanje - Ta razdelek na noben način ne zmanjšuje Googlovih dosežkov, so inženirji res odlični in vprašanje, ali se to lahko šteje za pravo kvantno superiornost ali ne, kot je bilo omenjeno prej, je bolj filozofsko kot inženirsko. Vendar moramo razumeti, da po doseganju takšne računalniške superiornosti nismo napredovali niti koraka do zmožnosti izvajanja Shorjevega algoritma na 2048-bitnih številih.
Pravega komercialnega izkoriščanja še ni (in ni jasno, kdaj bo)
Kaj lahko pomaga:
Nekakšno fizično odkritje, ki zmanjša stroške ožičenja in delovanja procesorjev
Odkritje nečesa, kar bo podaljšalo čas dekoherence za red velikosti in/ali zmanjšalo napake
Po mojem (čisto osebnem mnenju) V trenutni znanstveni paradigmi znanja ne bomo dosegli pomembnejših uspehov pri razvoju kvantnih tehnologij, tukaj potrebujemo kakovosten preboj na nekem področju temeljne ali uporabne znanosti, ki bo dal zagon novim idejam in metodam.
Vmes pa nabiramo izkušnje na področju kvantnega programiranja, zbiramo in ustvarjamo kvantne algoritme, testiramo ideje itd. itd. Čakamo na preboj.
V tem članku smo šli skozi glavne mejnike v razvoju kvantnega računalništva in kvantnih računalnikov, preučili princip njihovega delovanja, preučili glavne težave, s katerimi se soočajo inženirji pri razvoju in delovanju kvantnih procesorjev, pogledali pa smo tudi, kaj je multi-qubit Računalniki D pravzaprav so. Nedavna napoved Wavea in Googla o doseganju kvantne premoči.
V zakulisju so ostala vprašanja programiranja kvantnih računalnikov (jeziki, pristopi, metode itd.) in vprašanja v zvezi s specifično fizično implementacijo procesorjev, kako se kubiti upravljajo, povezujejo, berejo itd. Morda bo to tema naslednjega članka ali člankov.
Hvala za vašo pozornost, upam, da bo ta članek komu koristen.