EITC/QI/QIF Quantum Information Fundamentals je evropski program IT sertifikacije o teoretskim i praktičnim aspektima kvantnih informacija i kvantnog računanja, zasnovan na zakonima kvantne fizike, a ne klasične fizike i nudi kvalitativne prednosti u odnosu na njihove klasične kolege.
Nastavni plan i program EITC/QI/QIF Osnove kvantnih informacija pokriva uvod u kvantnu mehaniku (uključujući razmatranje eksperimenta sa dvostrukim prorezom i interferencije talasa materije), uvod u kvantne informacije (kubiti i njihov geometrijski prikaz), polarizaciju svetlosti, princip nesigurnosti, kvantne isprepletenost, EPR paradoks, kršenje Bell nejednakosti, napuštanje lokalnog realizma, kvantna obrada informacija (uključujući unitarnu transformaciju, jednokubitna i dvokubitna vrata), teorema bez kloniranja, kvantna teleportacija, kvantno mjerenje, kvantno računanje (uključujući uvod u višestruko -qubit sistemi, univerzalna porodica kapija, reverzibilnost računanja), kvantni algoritmi (uključujući kvantnu Fourierovu transformaciju, Simonov algoritam, proširenu Churh-Turingovu tezu, Shor'q kvantni faktor faktoring algoritam, Groverov kvantni algoritam pretraživanja, opservacijski kvantitet), implementacije kubita, kvantna teorija složenosti, adijabatsko kvantno računanje ion, BQP, uvod u spin, u okviru sljedeće strukture, koja obuhvata sveobuhvatan video didaktički sadržaj kao referencu za ovu EITC certifikat.
Kvantna informacija je informacija o stanju kvantnog sistema. To je osnovni entitet proučavanja u kvantnoj teoriji informacija i njime se može manipulirati korištenjem tehnika kvantne obrade informacija. Kvantne informacije odnose se i na tehničku definiciju u smislu Von Neumannove entropije i na opći računski termin.
Kvantne informacije i računarstvo je interdisciplinarno polje koje uključuje kvantnu mehaniku, informatiku, teoriju informacija, filozofiju i kriptografiju između ostalih polja. Njegovo proučavanje je takođe relevantno za discipline kao što su kognitivna nauka, psihologija i neuronauka. Njegov glavni fokus je u izdvajanju informacija iz materije na mikroskopskom nivou. Promatranje u nauci je temeljni distinktivni kriturijum stvarnosti i jedan od najvažnijih načina sticanja informacija. Stoga je mjerenje potrebno kako bi se kvantificiralo zapažanje, što ga čini ključnim za naučnu metodu. U kvantnoj mehanici, zbog principa neizvjesnosti, ne-komutirajuće opservable ne mogu se precizno mjeriti istovremeno, jer vlastito stanje u jednoj bazi nije svojstveno stanje u drugoj bazi. Kako obje varijable nisu istovremeno dobro definirane, kvantno stanje nikada ne može sadržavati konačne informacije o obje varijable. Zbog ovog fundamentalnog svojstva mjerenja u kvantnoj mehanici, ova teorija se općenito može okarakterizirati kao nedeterministička za razliku od klasične mehanike, koja je potpuno deterministička. Indeterminizam kvantnih stanja karakteriše informacije definisane kao stanja kvantnih sistema. U matematičkom smislu ova stanja su u superpozicijama (linearnim kombinacijama) stanja klasičnih sistema.
Kako je informacija uvijek kodirana u stanju fizičkog sistema, ona je sama po sebi fizička. Dok se kvantna mehanika bavi ispitivanjem svojstava materije na mikroskopskom nivou, kvantna informaciona nauka fokusira se na izdvajanje informacija iz tih svojstava, a kvantno računanje manipuliše i obrađuje kvantne informacije – izvodi logičke operacije – koristeći tehnike obrade kvantnih informacija.
Kvantne informacije, kao i klasične informacije, mogu se obraditi pomoću kompjutera, prenositi s jedne lokacije na drugu, manipulirati algoritmima i analizirati pomoću računarstva i matematike. Baš kao što je osnovna jedinica klasične informacije bit, kvantna informacija se bavi kubitima, koji mogu postojati u superpoziciji 0 i 1 (istovremeno su donekle istiniti i lažni). Kvantne informacije mogu postojati i u takozvanim zapletenim stanjima, koja manifestuju čisto neklasične nelokalne korelacije u svojim mjerenjima, omogućavajući primjene kao što je kvantna teleportacija. Nivo isprepletenosti može se izmjeriti korištenjem Von Neumannove entropije, koja je također mjera kvantne informacije. Nedavno je oblast kvantnog računarstva postala veoma aktivna istraživačka oblast zbog mogućnosti da poremeti moderno računarstvo, komunikaciju i kriptografiju.
Istorija kvantnih informacija započela je na prijelazu iz 20. stoljeća kada je klasična fizika revolucionirana u kvantnu fiziku. Teorije klasične fizike predviđale su apsurde kao što je ultraljubičasta katastrofa, ili spirala elektrona u jezgro. U početku su ovi problemi odbačeni dodavanjem ad hoc hipoteze klasičnoj fizici. Ubrzo je postalo očito da se mora stvoriti nova teorija kako bi se shvatili ovi apsurdi, i nastala je teorija kvantne mehanike.
Kvantnu mehaniku je formulisao Schrödinger koristeći mehaniku valova, a Heisenberg koristeći matričnu mehaniku. Ekvivalencija ovih metoda je kasnije dokazana. Njihove formulacije su opisivale dinamiku mikroskopskih sistema, ali su imale nekoliko nezadovoljavajućih aspekata u opisivanju mjernih procesa. Von Neumann je formulisao kvantnu teoriju koristeći algebru operatora na način da opisuje mjerenje kao i dinamiku. Ove studije su više naglašavale filozofske aspekte mjerenja nego kvantitativni pristup izdvajanju informacija putem mjerenja.
1960-ih, Stratonovič, Helstrom i Gordon su predložili formulaciju optičkih komunikacija koristeći kvantnu mehaniku. Ovo je bila prva historijska pojava kvantne teorije informacija. Oni su uglavnom proučavali vjerovatnoće grešaka i kapacitete kanala za komunikaciju. Kasnije je Holevo dobio gornju granicu brzine komunikacije u prijenosu klasične poruke putem kvantnog kanala.
Sedamdesetih godina prošlog stoljeća počele su se razvijati tehnike za manipulaciju kvantnim stanjima jednog atoma, kao što su atomska zamka i skenirajući tunelski mikroskop, što je omogućilo izolaciju pojedinačnih atoma i njihovo slaganje u nizove. Prije ovog razvoja, precizna kontrola nad pojedinačnim kvantnim sistemima nije bila moguća, a eksperimenti su koristili grublju, istovremenu kontrolu nad velikim brojem kvantnih sistema. Razvoj održivih tehnika manipulacije sa jednim stanjem doveo je do povećanog interesovanja za oblast kvantnih informacija i računanja.
Osamdesetih godina prošlog vijeka pojavilo se zanimanje da li je moguće koristiti kvantne efekte za opovrgavanje Ajnštajnove teorije relativnosti. Kada bi bilo moguće klonirati nepoznato kvantno stanje, bilo bi moguće koristiti zamršena kvantna stanja za prijenos informacija bržim od brzine svjetlosti, pobijajući Ajnštajnovu teoriju. Međutim, teorema o zabrani kloniranja pokazala je da je takvo kloniranje nemoguće. Teorema je bila jedan od najranijih rezultata kvantne teorije informacija.
Razvoj iz kriptografije
Uprkos svom uzbuđenju i interesovanju zbog proučavanja izolovanih kvantnih sistema i pokušaja da se pronađe način da se zaobiđe teorija relativnosti, istraživanja u kvantnoj teoriji informacija stagnirala su 1980-ih. Međutim, otprilike u isto vrijeme drugi put se počeo baviti kvantnim informacijama i računanjem: kriptografija. U opštem smislu, kriptografija je problem komunikacije ili računanja koji uključuje dvije ili više strana koje možda ne vjeruju jedna drugoj.
Bennett i Brassard su razvili komunikacijski kanal na kojem je nemoguće prisluškivati a da ne budu otkriveni, način tajne komunikacije na velikim udaljenostima koristeći kvantni kriptografski protokol BB84. Ključna ideja bila je korištenje temeljnog principa kvantne mehanike da promatranje ometa promatranog, a uvođenje prisluškivača u sigurnu komunikacijsku liniju će odmah omogućiti dvije strane koje pokušavaju komunicirati da znaju za prisustvo prisluškivača.
Razvoj iz informatike i matematike
Sa pojavom revolucionarnih ideja Alana Turinga o programabilnom računaru, ili Turing mašini, on je pokazao da se svako računanje u stvarnom svetu može prevesti u ekvivalentno računanje koje uključuje Turingovu mašinu. Ovo je poznato kao Church-Turingova teza.
Ubrzo su napravljeni prvi računari i kompjuterski hardver je rastao tako brzim tempom da je rast, kroz iskustvo u proizvodnji, kodifikovan u empirijski odnos nazvan Mooreov zakon. Ovaj 'zakon' je projektivni trend koji kaže da se broj tranzistora u integriranom kolu udvostručuje svake dvije godine. Kako su tranzistori počeli da postaju sve manji i manji kako bi dobili više snage po površini, kvantni efekti su se počeli pojavljivati u elektronici što je rezultiralo nenamjernim smetnjama. To je dovelo do pojave kvantnog računarstva, koje je koristilo kvantnu mehaniku za dizajniranje algoritama.
U ovom trenutku, kvantni kompjuteri su obećali da će biti mnogo brži od klasičnih računara za određene specifične probleme. Jedan takav primjer problema su razvili David Deutsch i Richard Jozsa, poznat kao Deutsch–Jozsa algoritam. Međutim, ovaj problem nije imao praktične primjene. Peter Shor je 1994. godine došao do vrlo važnog i praktičnog problema, jednog od pronalaženja prostih faktora cijelog broja. Problem diskretnog logaritma, kako je nazvan, mogao bi se efikasno riješiti na kvantnom računaru, ali ne i na klasičnom računaru, što pokazuje da su kvantni računari moćniji od Turingovih mašina.
Razvoj iz teorije informacija
Otprilike u vrijeme kada je kompjuterska nauka napravila revoluciju, kao i teorija informacija i komunikacija, preko Claudea Shanona. Shannon je razvio dvije fundamentalne teoreme teorije informacija: teoremu o bešumnom kanalnom kodiranju i teoremu o šumnom kanalnom kodiranju. Takođe je pokazao da se kodovi za ispravljanje grešaka mogu koristiti za zaštitu informacija koje se šalju.
Kvantna teorija informacija je također slijedila sličnu putanju, Ben Schumacher je 1995. napravio analogiju Shanonovoj teoremi bešumnog kodiranja koristeći kubit. Razvijena je i teorija ispravljanja grešaka, koja omogućava kvantnim računarima da izvrše efikasne proračune bez obzira na buku i da ostvare pouzdanu komunikaciju preko bučnih kvantnih kanala.
Kubiti i teorija informacija
Kvantne informacije se snažno razlikuju od klasičnih informacija, oličenih bitovima, na mnogo upečatljivih i nepoznatih načina. Dok je osnovna jedinica klasične informacije bit, najosnovnija jedinica kvantne informacije je kubit. Klasična informacija se mjeri pomoću Šenonove entropije, dok je kvantnomehanički analog Von Neumannova entropija. Statistički ansambl kvantnih mehaničkih sistema karakteriše matrica gustine. Mnoge mjere entropije u klasičnoj teoriji informacija također se mogu generalizirati na kvantni slučaj, kao što je Holevo entropija i uslovna kvantna entropija.
Za razliku od klasičnih digitalnih stanja (koja su diskretna), kubit ima kontinualnu vrijednost i može se opisati smjerom na Bloch sferi. Uprkos tome što se kontinuirano vrednuje na ovaj način, kubit je najmanja moguća jedinica kvantne informacije, i uprkos tome što je stanje kubita kontinuirano vrednovano, nemoguće je precizno izmeriti vrednost. Pet poznatih teorema opisuju ograničenja manipulacije kvantnim informacijama:
- teorem bez teleportacije, koji kaže da se kubit ne može (u potpunosti) pretvoriti u klasične bitove; odnosno ne može se u potpunosti „pročitati“,
- teorema bez kloniranja, koja sprječava kopiranje proizvoljnog kubita,
- teorema bez brisanja, koja sprječava brisanje proizvoljnog kubita,
- teorema o zabrani emitiranja, koja sprječava da se proizvoljni kubit isporuči većem broju primalaca, iako se može prenijeti s mjesta na mjesto (npr. putem kvantne teleportacije),
- Teorema bez skrivanja, koja pokazuje očuvanje kvantnih informacija, Ove teoreme dokazuju da su kvantne informacije unutar univerzuma očuvane i otvaraju jedinstvene mogućnosti u kvantnoj obradi informacija.
Kvantna obrada informacija
Stanje kubita sadrži sve njegove informacije. Ovo stanje se često izražava kao vektor na Bloch sferi. Ovo stanje se može promijeniti primjenom linearnih transformacija ili kvantnih kapija na njih. Ove unitarne transformacije su opisane kao rotacije na Bloch sferi. Dok klasične kapije odgovaraju poznatim operacijama Booleove logike, kvantne kapije su fizički unitarni operatori.
Zbog nestabilnosti kvantnih sistema i nemogućnosti kopiranja stanja, pohranjivanje kvantnih informacija je mnogo teže od pohranjivanja klasičnih informacija. Ipak, uz korištenje kvantne korekcije grešaka, kvantne informacije se u principu i dalje mogu pouzdano pohraniti. Postojanje kvantnih kodova za ispravljanje grešaka takođe je dovelo do mogućnosti kvantnog izračunavanja otpornog na greške.
Klasični bitovi se mogu kodirati u i naknadno izvući iz konfiguracija kubita, korištenjem kvantnih kapija. Sam po sebi, jedan kubit ne može prenijeti više od jednog bita dostupnih klasičnih informacija o njegovoj pripremi. Ovo je Holevova teorema. Međutim, u supergustom kodiranju, pošiljalac, djelujući na jedan od dva zapletena kubita, može prenijeti primaocu dva bita dostupnih informacija o njihovom zajedničkom stanju.
Kvantne informacije mogu se kretati unaokolo, u kvantnom kanalu, analogno konceptu klasičnog komunikacijskog kanala. Kvantne poruke imaju konačnu veličinu, mjerenu u kubitima; kvantni kanali imaju konačan kapacitet kanala, mjeren u kubitima u sekundi.
Kvantne informacije i promjene u kvantnim informacijama mogu se kvantitativno izmjeriti korištenjem analoga Šenonove entropije, nazvane von Neumannova entropija.
U nekim slučajevima kvantni algoritmi se mogu koristiti za izvođenje proračuna brže nego u bilo kojem poznatom klasičnom algoritmu. Najpoznatiji primjer ovoga je Shorov algoritam koji može faktorizirati brojeve u polinomskom vremenu, u poređenju sa najboljim klasičnim algoritmima koji uzimaju sub-eksponencijalno vrijeme. Kako je faktorizacija važan dio sigurnosti RSA enkripcije, Shorov algoritam je pokrenuo novo polje post-kvantne kriptografije koja pokušava pronaći šeme šifriranja koje ostaju sigurne čak i kada su kvantni računari u igri. Drugi primjeri algoritama koji demonstriraju kvantnu nadmoć uključuju Groverov algoritam pretraživanja, gdje kvantni algoritam daje kvadratno ubrzanje u odnosu na najbolji mogući klasični algoritam. Klasa složenosti problema koje efikasno rešava kvantni računar poznata je kao BQP.
Kvantna distribucija ključeva (QKD) omogućava bezuvjetno siguran prijenos klasičnih informacija, za razliku od klasične enkripcije, koja se uvijek može razbiti u principu, ako ne u praksi. Imajte na umu da se o nekim suptilnim točkama u vezi sa sigurnošću QKD-a još uvijek žestoko raspravlja.
Proučavanje svih gore navedenih tema i razlika obuhvata kvantnu teoriju informacija.
Odnos prema kvantnoj mehanici
Kvantna mehanika proučava kako se mikroskopski fizički sistemi dinamički mijenjaju u prirodi. U polju kvantne teorije informacija, kvantni sistemi koji se proučavaju su apstrahovani od bilo kojeg realnog svijeta. Kubit bi, na primjer, mogao fizički biti foton u linearnom optičkom kvantnom kompjuteru, ion u zarobljenom ionskom kvantnom kompjuteru, ili može biti velika zbirka atoma kao u supravodljivom kvantnom kompjuteru. Bez obzira na fizičku implementaciju, ograničenja i karakteristike kubita koje implicira kvantna teorija informacija vrijede jer su svi ovi sistemi matematički opisani istim aparatom matrica gustine nad kompleksnim brojevima. Još jedna bitna razlika u odnosu na kvantnu mehaniku je u tome što, dok kvantna mehanika često proučava beskonačno-dimenzionalne sisteme kao što je harmonijski oscilator, kvantna teorija informacija se bavi i sistemima s kontinuiranom promjenjivom i konačno-dimenzionalnim sistemima.
Kvantno računanje
Kvantno računanje je vrsta proračuna koja koristi kolektivna svojstva kvantnih stanja, kao što su superpozicija, interferencija i zapetljanost, za izvođenje proračuna. Uređaji koji izvode kvantna izračunavanja poznati su kao kvantni računari.: I-5 Iako su trenutni kvantni računari premali da bi nadmašili uobičajene (klasične) računare za praktične primjene, vjeruje se da su sposobni riješiti određene računske probleme, kao što je faktorizacija cijelih brojeva (koji je u osnovi RSA enkripcije), znatno brži od klasičnih računara. Proučavanje kvantnog računarstva je potpolje kvantne informatičke nauke.
Kvantno računanje počelo je 1980. godine kada je fizičar Paul Benioff predložio kvantnomehanički model Turingove mašine. Richard Feynman i Yuri Manin su kasnije sugerirali da kvantni kompjuter ima potencijal da simulira stvari koje klasični kompjuter ne može učiniti. Godine 1994. Peter Shor je razvio kvantni algoritam za faktoring cijelih brojeva s potencijalom za dešifriranje RSA šifriranih komunikacija. Godine 1998. Isaac Chuang, Neil Gershenfeld i Mark Kubinec stvorili su prvi kvantni kompjuter od dva kubita koji je mogao izvoditi proračune. Uprkos tekućem eksperimentalnom napretku od kasnih 1990-ih, većina istraživača vjeruje da je “kvantno računanje otporno na greške [još] prilično daleki san”. Posljednjih godina, u javnom i privatnom sektoru povećana su ulaganja u istraživanja kvantnog računarstva. Dana 23. oktobra 2019. godine, Google AI, u partnerstvu sa Američkom nacionalnom administracijom za aeronautiku i svemir (NASA), tvrdio je da je izvršio kvantno izračunavanje koje je bilo neizvodljivo na bilo kom klasičnom računaru, ali da li je ova tvrdnja bila ili još uvek važi, tema je aktivno istraživanje.
Postoji nekoliko tipova kvantnih računara (takođe poznatih kao kvantni računarski sistemi), uključujući model kvantnog kola, kvantnu Turingovu mašinu, adijabatski kvantni računar, jednosmerni kvantni računar i razne kvantne ćelijske automate. Najrasprostranjeniji model je kvantno kolo, bazirano na kvantnom bitu, ili „kubitu“, koji je donekle analogan bitu u klasičnom računanju. Kubit može biti u kvantnom stanju 1 ili 0, ili u superpoziciji stanja 1 i 0. Međutim, kada se meri, uvek je 0 ili 1; vjerovatnoća bilo kojeg ishoda zavisi od kvantnog stanja kubita neposredno prije mjerenja.
Napori ka izgradnji fizičkog kvantnog računara fokusirani su na tehnologije kao što su transmoni, jonske zamke i topološki kvantni kompjuteri, koji imaju za cilj stvaranje visokokvalitetnih kubita.: 2–13 Ovi kubiti mogu biti dizajnirani drugačije, u zavisnosti od računarskog modela punog kvantnog računara, bilo da su kvantna logička kapija, kvantno žarenje ili adijabatsko kvantno računanje. Trenutno postoji niz značajnih prepreka za izgradnju korisnih kvantnih kompjutera. Posebno je teško održavati kvantna stanja kubita, jer oni pate od kvantne dekoherencije i vjernosti stanja. Stoga kvantni računari zahtijevaju ispravljanje grešaka.
Svaki računski problem koji se može riješiti klasičnim računarom može se riješiti i kvantnim računarom. Suprotno tome, svaki problem koji se može riješiti kvantnim kompjuterom može se riješiti i klasičnim kompjuterom, barem u principu ako mu se da dovoljno vremena. Drugim riječima, kvantni kompjuteri poštuju Church-Turingovu tezu. To znači da, dok kvantni računari ne daju nikakve dodatne prednosti u odnosu na klasične računare u smislu izračunljivosti, kvantni algoritmi za određene probleme imaju znatno manju vremensku složenost od odgovarajućih poznatih klasičnih algoritama. Zanimljivo je da se vjeruje da kvantni kompjuteri mogu brzo riješiti određene probleme koje nijedan klasični kompjuter ne bi mogao riješiti ni u jednom izvodljivom vremenu - podvig poznat kao "kvantna nadmoć". Proučavanje računske složenosti problema u odnosu na kvantne računare poznato je kao kvantna teorija složenosti.
Preovlađujući model kvantnog izračunavanja opisuje računanje u smislu mreže kvantnih logičkih kapija. Ovaj model se može smatrati apstraktnom linearno-algebarskom generalizacijom klasičnog kola. Budući da ovaj model kola poštuje kvantnu mehaniku, vjeruje se da je kvantni kompjuter sposoban za efikasno pokretanje ovih kola fizički ostvariv.
Memorija koja se sastoji od n bitova informacija ima 2^n mogućih stanja. Tako vektor koji predstavlja sva memorijska stanja ima 2^n unosa (po jedan za svako stanje). Ovaj vektor se posmatra kao vektor verovatnoće i predstavlja činjenicu da se memorija nalazi u određenom stanju.
U klasičnom pogledu, jedan unos bi imao vrijednost 1 (tj. 100% vjerovatnoću da se nalazi u ovom stanju), a svi ostali unosi bi bili nula.
U kvantnoj mehanici, vektori vjerovatnoće se mogu generalizirati na operatore gustoće. Formalizam vektora kvantnog stanja obično se uvodi prvi jer je konceptualno jednostavniji i zato što se može koristiti umjesto formalizma matrice gustine za čista stanja, gdje je poznat cijeli kvantni sistem.
kvantno računanje se može opisati kao mreža kvantnih logičkih kapija i mjerenja. Međutim, svako mjerenje se može odgoditi do kraja kvantnog izračunavanja, iako ovo odlaganje može imati računsku cijenu, tako da većina kvantnih kola prikazuje mrežu koja se sastoji samo od kvantnih logičkih kapija i bez mjerenja.
Svako kvantno računanje (koje je, u gornjem formalizmu, bilo koja unitarna matrica preko n kubita) može se predstaviti kao mreža kvantnih logičkih kapija iz prilično male porodice kapija. Izbor porodice kapija koji omogućava ovu konstrukciju poznat je kao univerzalni set kapija, pošto je računar koji može pokrenuti takva kola univerzalni kvantni računar. Jedan zajednički takav skup uključuje sve jednokubitne kapije, kao i CNOT kapiju odozgo. To znači da se svako kvantno izračunavanje može izvesti izvršavanjem niza jednokubitnih kapija zajedno sa CNOT kapijama. Iako je ovaj skup kapija beskonačan, može se zamijeniti skupom konačnih kapija pozivanjem na Solovay-Kitajev teorem.
Kvantni algoritmi
Napredak u pronalaženju kvantnih algoritama obično se fokusira na ovaj model kvantnog kola, iako postoje izuzeci poput kvantnog adijabatskog algoritma. Kvantni algoritmi se mogu grubo kategorizirati prema tipu ubrzanja postignutog u odnosu na odgovarajuće klasične algoritme.
Kvantni algoritmi koji nude više od polinomskog ubrzanja u odnosu na najpoznatiji klasični algoritam uključuju Shorov algoritam za faktoring i srodne kvantne algoritme za izračunavanje diskretnih logaritama, rješavanje Pellove jednadžbe i općenito rješavanje problema skrivene podgrupe za abelove konačne grupe. Ovi algoritmi zavise od primitivnosti kvantne Fourierove transformacije. Nije pronađen nikakav matematički dokaz koji pokazuje da se jednako brz klasični algoritam ne može otkriti, iako se to smatra malo vjerojatnim.[samoobjavljen izvor?] Određeni problemi proročanstva poput Simonovog problema i Bernstein–Vaziraninog problema daju dokaziva ubrzanja, iako ovo nije moguće. nalazi se u modelu kvantnog upita, koji je ograničeni model gdje je donje granice mnogo lakše dokazati i ne znači nužno ubrzanje praktičnih problema.
Drugi problemi, uključujući simulaciju kvantnih fizičkih procesa iz hemije i fizike čvrstog stanja, aproksimaciju određenih Jonesovih polinoma i kvantni algoritam za linearne sisteme jednačina, imaju kvantne algoritme za koje se čini da daju super-polinomska ubrzanja i da su BQP-potpuni. Budući da su ovi problemi BQP-potpuni, jednako brz klasični algoritam za njih bi implicirao da nijedan kvantni algoritam ne daje super-polinomsko ubrzanje, za koje se vjeruje da je malo vjerovatno.
Neki kvantni algoritmi, poput Groverovog algoritma i amplitude amplifikacije, daju polinomska ubrzanja u odnosu na odgovarajuće klasične algoritme. Iako ovi algoritmi daju relativno skromno kvadratno ubrzanje, oni su široko primjenjivi i stoga daju ubrzanja za širok raspon problema. Mnogi primjeri dokazivih kvantnih ubrzanja za probleme upita vezani su za Groverov algoritam, uključujući Brassard, Høyer i Tappov algoritam za pronalaženje sudara u funkcijama dva prema jedan, koji koristi Groverov algoritam i Farhi, Goldstone i Gutmannov algoritam za procjenu NAND-a. stabla, što je varijanta problema pretraživanja.
Kriptografske aplikacije
Značajna primjena kvantnog računanja je za napade na kriptografske sisteme koji su trenutno u upotrebi. Vjeruje se da je cjelobrojna faktorizacija, koja podupire sigurnost kriptografskih sistema javnog ključa, računski neizvodljiva sa običnim računarom za velike cijele brojeve ako su oni proizvod nekoliko prostih brojeva (npr. proizvodi dva 300-cifreni broj prostih brojeva). Poređenja radi, kvantni kompjuter bi mogao efikasno riješiti ovaj problem koristeći Shorov algoritam da pronađe njegove faktore. Ova sposobnost bi omogućila kvantnom kompjuteru da razbije mnoge kriptografske sisteme koji se danas koriste, u smislu da bi postojao algoritam polinomskog vremena (u broju cifara celog broja) za rešavanje problema. Konkretno, većina popularnih šifri javnog ključa zasnovana je na težini faktoringa cijelih brojeva ili problemu diskretnog logaritma, a oba se mogu riješiti Shorovim algoritmom. Konkretno, algoritmi RSA, Diffie–Hellman i eliptične krive Diffie–Hellman algoritmi mogu biti slomljeni. Oni se koriste za zaštitu sigurnih web stranica, šifrirane e-pošte i mnogih drugih vrsta podataka. Njihovo kršenje bi imalo značajne posljedice za elektroničku privatnost i sigurnost.
Identifikacija kriptografskih sistema koji mogu biti sigurni od kvantnih algoritama je tema koja se aktivno istražuje u polju post-kvantne kriptografije. Neki algoritmi sa javnim ključem su zasnovani na problemima koji nisu celobrojni faktorizacija i problemi diskretnog logaritma na koje se Shorov algoritam primenjuje, kao što je McEliece kriptosistem zasnovan na problemu u teoriji kodiranja. Takođe nije poznato da su kriptosistemi zasnovani na rešetki razbijeni od strane kvantnih računara, a pronalaženje algoritma polinomskog vremena za rešavanje problema skrivene podgrupe diedrala, koji bi razbio mnoge kriptosisteme zasnovane na rešetki, je dobro proučavan otvoreni problem. Dokazano je da primjena Groverovog algoritma za razbijanje simetričnog (tajnog ključa) algoritma grubom silom zahtijeva vrijeme jednako otprilike 2n/2 poziva osnovnog kriptografskog algoritma, u poređenju sa otprilike 2n u klasičnom slučaju, što znači da su simetrične dužine ključa efektivno prepolovljeno: AES-256 bi imao istu sigurnost od napada koristeći Groverov algoritam koji AES-128 ima protiv klasične brute-force pretrage (pogledajte Veličina ključa).
Kvantna kriptografija bi potencijalno mogla ispuniti neke od funkcija kriptografije javnog ključa. Kvantno zasnovani kriptografski sistemi mogli bi stoga biti sigurniji od tradicionalnih sistema protiv kvantnog hakovanja.
Problemi u potrazi
Najpoznatiji primjer problema koji priznaje polinomsko kvantno ubrzanje je nestrukturirana pretraga, pronalaženje označene stavke sa liste od n stavki u bazi podataka. Ovo se može riješiti Groverovim algoritmom korištenjem O(sqrt(n)) upita bazi podataka, kvadratno manje od Omega(n) upita potrebnih za klasične algoritme. U ovom slučaju, prednost je ne samo dokaziva već i optimalna: pokazalo se da Groverov algoritam daje maksimalnu moguću vjerovatnoću pronalaženja željenog elementa za bilo koji broj traženja proročišta.
Problemi koji se mogu riješiti Groverovim algoritmom imaju sljedeća svojstva:
- Ne postoji struktura koja se može pretraživati u zbirci mogućih odgovora,
- Broj mogućih odgovora za provjeru je isti kao i broj ulaza u algoritam, i
- Postoji logička funkcija koja procjenjuje svaki ulaz i određuje da li je to tačan odgovor
Za probleme sa svim ovim svojstvima, vrijeme rada Groverovog algoritma na kvantnom kompjuteru mjeri se kao kvadratni korijen broja ulaza (ili elemenata u bazi podataka), za razliku od linearnog skaliranja klasičnih algoritama. Opšta klasa problema na koje se Groverov algoritam može primijeniti je Bulov problem zadovoljivosti, gdje je baza podataka kroz koju se algoritam ponavlja je baza svih mogućih odgovora. Primjer i (moguća) primjena ovoga je kreker lozinke koji pokušava pogoditi lozinku. Simetrične šifre kao što su Triple DES i AES su posebno ranjive na ovu vrstu napada. [potreban citat] Ova primjena kvantnog računarstva je glavni interes vladinih agencija.
Simulacija kvantnih sistema
Budući da se hemija i nanotehnologija oslanjaju na razumijevanje kvantnih sistema, a takve sisteme je nemoguće simulirati na efikasan način na klasičan način, mnogi vjeruju da će kvantna simulacija biti jedna od najvažnijih primjena kvantnog računarstva. Kvantna simulacija se također može koristiti za simulaciju ponašanja atoma i čestica u neobičnim uvjetima kao što su reakcije unutar sudarača. Kvantne simulacije bi se mogle koristiti za predviđanje budućih putanja čestica i protona pod superpozicijom u eksperimentu sa dvostrukim prorezom.[citat potreban] Oko 2% godišnje globalne proizvodnje energije koristi se za fiksaciju dušika za proizvodnju amonijaka za Haberov proces u poljoprivredi. industriju gnojiva, dok prirodni organizmi također proizvode amonijak. Kvantne simulacije mogu se koristiti za razumijevanje ovog procesa koji povećava proizvodnju.
Kvantno žarenje i adijabatska optimizacija
Kvantno žarenje ili adijabatsko kvantno računanje oslanja se na adijabatsku teoremu za poduzimanje proračuna. Sistem se postavlja u osnovno stanje za jednostavan Hamiltonijan, koji se polako razvija u složeniji Hamiltonijan čije osnovno stanje predstavlja rješenje problema o kojem je riječ. Adijabatska teorema kaže da ako je evolucija dovoljno spora, sistem će ostati u svom osnovnom stanju cijelo vrijeme kroz proces.
Mašinsko učenje
Budući da kvantni računari mogu proizvesti rezultate koje klasični računari ne mogu proizvesti efikasno, i pošto je kvantno računanje u osnovi linearno algebarsko, neki izražavaju nadu u razvoj kvantnih algoritama koji mogu ubrzati zadatke mašinskog učenja. Na primjer, vjeruje se da kvantni algoritam za linearne sisteme jednačina, ili "HHL algoritam", nazvan po svojim otkrivačima Harrowu, Hassidimu i Lloydu, omogućava ubrzanje u odnosu na klasične kolege. Neke istraživačke grupe su nedavno istraživale upotrebu hardvera za kvantno žarenje za obuku Boltzmanovih mašina i dubokih neuronskih mreža.
Računarska biologija
U polju računske biologije, kvantno računanje je odigralo veliku ulogu u rješavanju mnogih bioloških problema. Jedan od dobro poznatih primjera bio bi u kompjuterskoj genomici i kako je računarstvo drastično smanjilo vrijeme za sekvenciranje ljudskog genoma. S obzirom na to kako kompjuterska biologija koristi generičko modeliranje i skladištenje podataka, očekuje se da će se pojaviti i njene primjene na računsku biologiju.
Kompjuterski potpomognut dizajn lijekova i generativna hemija
Duboki generativni kemijski modeli pojavljuju se kao moćni alati za ubrzanje otkrivanja lijekova. Međutim, ogromna veličina i složenost strukturnog prostora svih mogućih molekula sličnih drogama predstavljaju značajne prepreke, koje bi u budućnosti mogli savladati kvantni kompjuteri. Kvantni kompjuteri su prirodno dobri za rješavanje složenih kvantnih problema s više tijela i stoga mogu biti instrumentalni u aplikacijama koje uključuju kvantnu hemiju. Stoga se može očekivati da će kvantno poboljšani generativni modeli uključujući kvantne GAN-ove na kraju biti razvijeni u ultimativne algoritme generativne hemije. Hibridne arhitekture koje kombinuju kvantne računare sa dubokim klasičnim mrežama, kao što su kvantni varijacioni autoenkoderi, već se mogu obučiti na komercijalno dostupnim žarionicima i koristiti za generisanje novih molekularnih struktura sličnih lekovima.
Razvoj fizičkih kvantnih kompjutera
Izazovi
Postoji niz tehničkih izazova u izgradnji velikog kvantnog računara. Fizičar David DiVincenzo naveo je ove zahtjeve za praktični kvantni kompjuter:
- Fizički skalabilan za povećanje broja kubita,
- Kubiti koji se mogu inicijalizirati na proizvoljne vrijednosti,
- Kvantna vrata koja su brža od vremena dekoherencije,
- Univerzalni set kapija,
- Kubiti koji se lako čitaju.
Nabavka delova za kvantne računare je takođe veoma teška. Mnogim kvantnim računarima, poput onih koje su konstruisali Google i IBM, potreban je helijum-3, nusproizvod nuklearnog istraživanja, i specijalni supravodljivi kablovi koje proizvodi samo japanska kompanija Coax Co.
Kontrola multi-kubit sistema zahtijeva generiranje i koordinaciju velikog broja električnih signala sa čvrstom i determinističkom vremenskom rezolucijom. Ovo je dovelo do razvoja kvantnih kontrolera koji omogućavaju povezivanje sa kubitima. Skaliranje ovih sistema da podrže sve veći broj kubita je dodatni izazov.
Kvantna dekoherencija
Jedan od najvećih izazova vezanih za konstruiranje kvantnih kompjutera je kontrola ili uklanjanje kvantne dekoherencije. Ovo obično znači izolovanje sistema od njegovog okruženja jer interakcije sa spoljnim svetom uzrokuju dekoheraciju sistema. Međutim, postoje i drugi izvori dekoherencije. Primjeri uključuju kvantne kapije, i vibracije rešetke i pozadinski termonuklearni spin fizičkog sistema koji se koristi za implementaciju kubita. Dekoherencija je nepovratna, jer je efektivno ne-jedinstvena i obično je nešto što bi trebalo visoko kontrolisati, ako ne i izbjegavati. Vremena dekoherencije za sisteme kandidate, posebno vrijeme poprečne relaksacije T2 (za NMR i MRI tehnologiju, koje se naziva i vrijeme defaziranja), obično se kreće između nanosekundi i sekundi na niskoj temperaturi. Trenutno, neki kvantni računari zahtijevaju da se njihovi kubiti ohlade na 20 milikelvina (obično koristeći hladnjak za razrjeđivanje) kako bi se spriječila značajna dekoherencija. Studija iz 2020. godine tvrdi da jonizujuće zračenje, poput kosmičkih zraka, ipak može uzrokovati dekoheraciju određenih sistema unutar milisekundi.
Kao rezultat toga, dugotrajni zadaci mogu učiniti neke kvantne algoritme neoperativnim, jer će održavanje stanja kubita dovoljno dugo vremena na kraju pokvariti superpozicije.
Ova pitanja su teža za optičke pristupe jer su vremenske skale za redove veličine kraće i često citirani pristup za njihovo prevazilaženje je oblikovanje optičkih impulsa. Stope grešaka su obično proporcionalne omjeru vremena rada i vremena dekoherencije, stoga svaka operacija mora biti završena mnogo brže od vremena dekoherencije.
Kao što je opisano u teoremu o kvantnom pragu, ako je stopa greške dovoljno mala, smatra se da je moguće koristiti kvantnu korekciju greške za suzbijanje grešaka i dekoherencije. Ovo omogućava da ukupno vrijeme izračunavanja bude duže od vremena dekoherencije ako shema korekcije greške može ispraviti greške brže nego što ih dekoherencija uvodi. Često citirana brojka za potrebnu stopu greške u svakoj kapiji za izračunavanje otporne na greške je 10-3, pod pretpostavkom da se šum depolarizira.
Ispunjavanje ovog uslova skalabilnosti moguće je za širok spektar sistema. Međutim, korištenje ispravljanja grešaka sa sobom nosi cijenu znatno povećanog broja potrebnih kubita. Broj potreban za faktoriranje cijelih brojeva korištenjem Shorovog algoritma je još uvijek polinom i smatra se da je između L i L2, gdje je L broj cifara u broju koji se rastavlja na faktore; Algoritmi za ispravljanje grešaka bi povećali ovu cifru za dodatni faktor L. Za 1000-bitni broj, ovo implicira potrebu za oko 104 bita bez korekcije greške. Uz korekciju greške, broj bi se povećao na oko 107 bita. Vrijeme izračunavanja je oko L2 ili oko 107 koraka i na 1 MHz, oko 10 sekundi.
Veoma drugačiji pristup problemu stabilnosti-dekoherencije je stvaranje topološkog kvantnog kompjutera sa anjonima, kvazi-česticama koje se koriste kao niti i oslanjajući se na teoriju pletenica za formiranje stabilnih logičkih kapija.
Kvantna nadmoć
Kvantna supremacija je termin koji je skovao John Preskill koji se odnosi na inženjerski podvig demonstriranja da programabilni kvantni uređaj može riješiti problem izvan mogućnosti vrhunskih klasičnih kompjutera. Problem ne mora biti koristan, pa neki gledaju na test kvantne nadmoći samo kao na potencijalno buduće mjerilo.
U oktobru 2019. godine, Google AI Quantum, uz pomoć NASA-e, postao je prvi koji je tvrdio da je postigao kvantnu nadmoć izvodeći proračune na kvantnom računaru Sycamore više od 3,000,000 puta brže nego što bi se mogli uraditi na Summitu, koji se općenito smatra najbržim na svijetu. kompjuter. Ova tvrdnja je naknadno osporena: IBM je izjavio da Summit može izvoditi uzorke mnogo brže nego što se tvrdi, a istraživači su od tada razvili bolje algoritme za problem uzorkovanja koji se koristi za traženje kvantne nadmoći, dajući značajno smanjenje ili zatvaranje jaza između Sycamore i Sycamorea. klasičnih superračunara.
U decembru 2020., grupa u USTC implementirala je tip uzorkovanja bozona na 76 fotona s fotonskim kvantnim kompjuterom Jiuzhang kako bi demonstrirala kvantnu nadmoć. Autori tvrde da bi klasičnom savremenom superkompjuteru bilo potrebno vreme računanja od 600 miliona godina da generiše broj uzoraka koji njihov kvantni procesor može da generiše za 20 sekundi. IBM je 16. novembra 2021. na samitu kvantnog računarstva predstavio mikroprocesor od 127 kubita pod nazivom IBM Eagle.
Fizičke implementacije
Za fizičku implementaciju kvantnog računara, traže se mnogi različiti kandidati, među njima (odlikuje se fizičkim sistemom koji se koristi za realizaciju kubita):
- Superprovodno kvantno računanje (kubit implementiran stanjem malih supravodljivih kola, Josephsonovih spojeva)
- Kvantni kompjuter zarobljenih jona (kubit implementiran unutrašnjim stanjem zarobljenih jona)
- Neutralni atomi u optičkim rešetkama (kubit implementiran unutrašnjim stanjima neutralnih atoma zarobljenih u optičkoj rešetki)
- Računar s kvantnim tačkama, zasnovan na spinu (npr. Loss-DiVincenzo kvantni kompjuter) (kubit dat spinskim stanjima zarobljenih elektrona)
- Računar s kvantnim tačkama, prostorno zasnovan (kubit dat položajem elektrona u dvostrukoj kvantnoj tački)
- Kvantno računanje korištenjem projektiranih kvantnih bunara, koje bi u principu mogle omogućiti izgradnju kvantnih računara koji rade na sobnoj temperaturi
- Spojena kvantna žica (kubit implementiran parom kvantnih žica povezanih kvantnim kontaktom)
- Kvantni kompjuter nuklearne magnetne rezonancije (NMRQC) implementiran sa nuklearnom magnetskom rezonancom molekula u otopini, gdje se kubiti dobivaju nuklearnim spinovima unutar otopljenog molekula i ispituju radio valovima
- NMR Kane kvantni kompjuteri u čvrstom stanju (kubit ostvaren nuklearnim spinskim stanjem donora fosfora u silicijumu)
- Kvantni kompjuteri elektroni na helijumu (kubit je spin elektrona)
- Kvantna elektrodinamika šupljine (CQED) (kubit koji osigurava unutrašnje stanje zarobljenih atoma spojenih na šupljine visoke finoće)
- Molekularni magnet (kubit dat spinskim stanjima)
- ESR kvantni kompjuter baziran na fulerenu (kubit zasnovan na elektronskom spinu atoma ili molekula zatvorenih u fulerenima)
- Nelinearni optički kvantni kompjuter (kubiti ostvareni obradom stanja različitih modova svjetlosti kroz linearne i nelinearne elemente)
- Linearni optički kvantni kompjuter (kubiti ostvareni obradom stanja različitih modova svjetlosti kroz linearne elemente npr. ogledala, razdjelnici zraka i fazni pomaci)
- Kvantni kompjuter zasnovan na dijamantu (kubit ostvaren elektronskim ili nuklearnim spinom centara za praznine dušika u dijamantu)
- Kvantni kompjuter na bazi Bose-Einstein kondenzata
- Kvantni kompjuter baziran na tranzistoru – kvantni kompjuteri sa nizom sa uvlačenjem pozitivnih rupa pomoću elektrostatičke zamke
- Kvantni kompjuteri zasnovani na anorganskim kristalima dopiranim jonima rijetkih metala (kubit ostvaren unutrašnjim elektronskim stanjem dodataka u optičkim vlaknima)
- Kvantni kompjuteri bazirani na metalnim ugljičnim nanosferama
- Veliki broj kandidata pokazuje da je kvantno računarstvo, uprkos brzom napretku, još uvijek u povojima.
Postoji niz modela kvantnog računarstva, koji se razlikuju po osnovnim elementima u kojima se računanje dekomponuje. Za praktične implementacije, četiri relevantna modela proračuna su:
- Kvantni niz gejta (računanje dekomponirano u niz kvantnih kapija od nekoliko kubita)
- Jednosmjerni kvantni kompjuter (računanje dekomponirano u niz mjerenja od jednog kubita primijenjenih na jako zapetljano početno stanje ili stanje klastera)
- Adijabatski kvantni kompjuter, zasnovan na kvantnom žarenju (računanje razloženo u sporu kontinuiranu transformaciju početnog Hamiltonijana u konačni Hamiltonijan, čija osnovna stanja sadrže rješenje)
- Topološki kvantni kompjuter (računanje razloženo na pletenje biloona u 2D rešetki)
Kvantna Turingova mašina je teoretski važna, ali fizička implementacija ovog modela nije izvodljiva. Pokazalo se da su sva četiri modela proračuna ekvivalentna; svaki može simulirati drugu s ne više od polinoma.
Da biste se detaljno upoznali sa nastavnim planom i programom sertifikacije, možete proširiti i analizirati tabelu ispod.
EITC/QI/QIF kurikulum sertifikacije Osnove kvantnih informacija upućuje na didaktičke materijale otvorenog pristupa u video obliku. Proces učenja je podijeljen u strukturu korak po korak (programi -> lekcije -> teme) koja pokriva relevantne dijelove kurikuluma. Takođe su obezbeđene neograničene konsultacije sa stručnjacima iz domena.
Za detalje o proceduri certifikacije provjerite Kako funkcionira.
Glavne napomene sa predavanja
U. Vazirani bilješke s predavanja:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Bilješke s predavanja
L. Jacak i dr. bilješke s predavanja (sa dopunskim materijalima):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Glavni pomoćni udžbenik
Kvantno računanje i kvantne informacije udžbenik (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Dodatne bilješke sa predavanja
Bilješke s predavanja J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Childs beleške sa predavanja:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Bilješke s predavanja S. Aaronson:
https://scottaaronson.blog/?p=3943
R. de Wolf bilješke s predavanja:
https://arxiv.org/abs/1907.09415
Ostali preporučeni udžbenici
Klasično i kvantno računanje (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Kvantno računarstvo od Demokrita (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Teorija kvantne informacije (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Kvantna teorija informacija (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Preuzmite kompletne pripremne materijale za vanmrežno samoučenje za program EITC/QI/QIF Quantum Information Fundamentals u PDF datoteci
EITC/QI/QIF pripremni materijali – standardna verzija
EITC/QI/QIF pripremni materijali – proširena verzija sa pitanjima za pregled