EITC/QI/QIF Quantum Information Fundamentals je europski program za certifikaciju IT-a o teoretskim i praktičnim aspektima kvantnih informacija i kvantnog računanja, koji se temelji na zakonima kvantne fizike umjesto klasične fizike i nudi kvalitativne prednosti u odnosu na njihove klasične kolege.
Nastavni plan i program EITC/QI/QIF Quantum Information Fundamentals pokriva uvod u kvantnu mehaniku (uključujući razmatranje eksperimenta s dvostrukim prorezom i interferencije valova materije), uvod u kvantne informacije (kubiti i njihov geometrijski prikaz), polarizaciju svjetlosti, princip nesigurnosti, kvant isprepletenost, EPR paradoks, kršenje Bellove nejednakosti, napuštanje lokalnog realizma, kvantna obrada informacija (uključujući unitarnu transformaciju, jednokubitna i dvokubitna vrata), teorem bez kloniranja, kvantna teleportacija, kvantno mjerenje, kvantno računanje (uključujući uvod u višestruki kubit) -qubit sustavi, univerzalna obitelj vrata, reverzibilnost izračunavanja), kvantni algoritmi (uključujući kvantnu Fourierovu transformaciju, Simonov algoritam, proširenu Churh-Turingovu tezu, Shor'q kvantni faktoring algoritam, Groverov algoritam kvantnog pretraživanja, opservacijski kvantitativni kvantitet), implementacije qubita, kvantna teorija složenosti, adijabatsko kvantno računanje ion, BQP, uvod u spin, unutar sljedeće strukture, koja obuhvaća sveobuhvatan videodidaktički sadržaj kao referencu za ovu EITC certifikaciju.
Kvantna informacija je informacija o stanju kvantnog sustava. 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 pojam.
Kvantne informacije i računanje je interdisciplinarno područje koje uključuje kvantnu mehaniku, informatiku, teoriju informacija, filozofiju i kriptografiju između ostalih polja. Njegovo proučavanje također je relevantno za discipline kao što su kognitivna znanost, psihologija i neuroznanost. Njegov je glavni fokus na izvlačenju informacija iz materije na mikroskopskoj razini. Promatranje u znanosti je temeljni distinktivni kriterij stvarnosti i jedan od najvažnijih načina stjecanja informacija. Stoga je mjerenje potrebno kako bi se kvantificiralo promatranje, što ga čini ključnim za znanstvenu metodu. U kvantnoj mehanici, zbog principa nesigurnosti, ne-komutirajuće opservable ne mogu se precizno mjeriti istovremeno, budući da 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 temeljnog 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 karakterizira informacije definirane kao stanja kvantnih sustava. U matematičkom smislu ta su stanja u superpozicijama (linearnim kombinacijama) stanja klasičnih sustava.
Kako je informacija uvijek kodirana u stanju fizičkog sustava, ona je sama po sebi fizička. Dok se kvantna mehanika bavi ispitivanjem svojstava materije na mikroskopskoj razini, kvantna informacijska znanost usredotočuje se na izvlačenje informacija iz tih svojstava, a kvantno računanje manipulira 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 računala, prenositi s jednog mjesta na drugo, manipulirati algoritmima i analizirati pomoću računalne znanosti 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 (istodobno su donekle istiniti i lažni). Kvantne informacije mogu postojati i u takozvanim zapetljanim stanjima, koja očituju čisto neklasične nelokalne korelacije u svojim mjerenjima, omogućujući primjene kao što je kvantna teleportacija. Razina isprepletenosti može se izmjeriti pomoću Von Neumannove entropije, koja je također mjera kvantne informacije. Nedavno je područje kvantnog računalstva postalo vrlo aktivno područje istraživanja zbog mogućnosti narušavanja modernog računanja, komunikacije i kriptografije.
Povijest 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 spiralni ulazak elektrona u jezgru. 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 razumjeli ti apsurdi, i nastala je teorija kvantne mehanike.
Kvantnu mehaniku je formulirao Schrödinger pomoću valne mehanike, a Heisenberg koristeći matričnu mehaniku. Ekvivalencija ovih metoda dokazana je kasnije. Njihove formulacije opisivale su dinamiku mikroskopskih sustava, ali su imale nekoliko nezadovoljavajućih aspekata u opisivanju mjernih procesa. Von Neumann je formulirao kvantnu teoriju koristeći algebru operatora na način da opisuje mjerenje kao i dinamiku. Ove studije su naglasile filozofske aspekte mjerenja, a ne kvantitativni pristup izdvajanju informacija putem mjerenja.
1960-ih, Stratonovich, Helstrom i Gordon predložili su formulaciju optičkih komunikacija korištenjem kvantne mehanike. Ovo je bila prva povijesna pojava kvantne teorije informacija. Uglavnom su proučavali vjerojatnosti pogrešaka i kapacitete kanala za komunikaciju. Kasnije je Holevo dobio gornju granicu brzine komunikacije u prijenosu klasične poruke putem kvantnog kanala.
U 1970-ima 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 sustavima nije bila moguća, a eksperimenti su koristili grublju, istodobnu kontrolu nad velikim brojem kvantnih sustava. Razvoj održivih tehnika manipulacije s jednim stanjem doveo je do povećanog interesa za područje kvantnih informacija i računanja.
U 1980-ima pojavio se interes za pitanje je li moguće koristiti kvantne efekte za opovrgavanje Einsteinove teorije relativnosti. Kad bi bilo moguće klonirati nepoznato kvantno stanje, bilo bi moguće koristiti zapletena kvantna stanja za prijenos informacija bržim od brzine svjetlosti, pobijajući Einsteinovu teoriju. Međutim, teorem o zabrani kloniranja pokazao je da je takvo kloniranje nemoguće. Teorem je bio jedan od najranijih rezultata kvantne teorije informacija.
Razvoj iz kriptografije
Unatoč svom uzbuđenju i interesu zbog proučavanja izoliranih kvantnih sustava i pokušaja pronalaženja načina 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ćem 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 razvili su komunikacijski kanal na kojem je nemoguće prisluškivati a da ga se ne otkrije, 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 da dvije strane koje pokušavaju komunicirati znaju za prisutnost prisluškivača.
Razvoj iz informatike i matematike
S pojavom revolucionarnih ideja Alana Turinga o programibilnom računalu, ili Turingovom stroju, pokazao je da se svako računanje u stvarnom svijetu može prevesti u ekvivalentno računanje koje uključuje Turingov stroj. To je poznato kao Church-Turingova teza.
Ubrzo su napravljena prva računala i računalni hardver je rastao tako brzim tempom da je rast, kroz iskustvo u proizvodnji, kodificiran u empirijski odnos nazvan Mooreov zakon. Ovaj 'zakon' je projektivni trend koji kaže da se broj tranzistora u integriranom krugu udvostručuje svake dvije godine. Kako su tranzistori počeli postajati sve manji i manji kako bi zapakirali 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čunalstva, koje je koristilo kvantnu mehaniku za dizajn algoritama.
U ovom trenutku, kvantna računala su obećala da će biti mnogo brža od klasičnih računala za određene specifične probleme. Jedan takav primjer problema razvili su 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 primarnih faktora cijelog broja. Problem diskretnog logaritma, kako je nazvan, mogao bi se učinkovito riješiti na kvantnom računalu, ali ne i na klasičnom računalu, što pokazuje da su kvantna računala moćnija od Turingovih strojeva.
Razvoj iz teorije informacija
Otprilike u vrijeme kada je kompjuterska znanost napravila revoluciju, kao i teorija informacija i komunikacija, putem Claudea Shannona. Shannon je razvio dva temeljna teorema teorije informacija: teorem o bešumnom kanalnom kodiranju i teorem o šumnom kanalnom kodiranju. Također je pokazao da se kodovi za ispravljanje pogrešaka mogu koristiti za zaštitu informacija koje se šalju.
Kvantna teorija informacija također je slijedila sličnu putanju, Ben Schumacher je 1995. napravio analogiju Shannonovu bešumnom teoremu kodiranja koristeći kubit. Također je razvijena teorija ispravljanja pogrešaka, koja omogućuje kvantnim računalima da izvrše učinkovite izračune bez obzira na šum, te da ostvare pouzdanu komunikaciju preko bučnih kvantnih kanala.
Kubiti i teorija informacija
Kvantne informacije se jako razlikuju od klasičnih informacija, oličenih bitom, na mnoge upečatljive i nepoznate načine. Dok je temeljna jedinica klasične informacije bit, najosnovnija jedinica kvantne informacije je kubit. Klasična informacija se mjeri pomoću Shannon entropije, dok je kvantnomehanički analog Von Neumannova entropija. Statistički ansambl kvantnih mehaničkih sustava karakterizira matrica gustoće. Mnoge mjere entropije u klasičnoj teoriji informacija također se mogu generalizirati na kvantni slučaj, kao što je Holevo entropija i uvjetna kvantna entropija.
Za razliku od klasičnih digitalnih stanja (koja su diskretna), kubit ima kontinuiranu vrijednost i može se opisati smjerom na Bloch sferi. Unatoč tome što se kontinuirano vrednuje na ovaj način, kubit je najmanja moguća jedinica kvantne informacije, a unatoč tome što je stanje kubita kontinuirano vrednovan, nemoguće je precizno izmjeriti vrijednost. Pet poznatih teorema opisuju ograničenja manipulacije kvantnim informacijama:
- teorem o neteleportaciji, koji kaže da se kubit ne može (potpuno) pretvoriti u klasične bitove; odnosno ne može se u potpunosti „pročitati“,
- teorem bez kloniranja, koji sprječava kopiranje proizvoljnog kubita,
- teorem bez brisanja, koji sprječava brisanje proizvoljnog kubita,
- teorem o zabrani emitiranja, koji sprječava da se proizvoljni kubit isporuči više primatelja, iako se može prenijeti s mjesta na mjesto (npr. putem kvantne teleportacije),
- teorem bez skrivanja, koji pokazuje očuvanje kvantnih informacija, Ovi teoremi dokazuju da su kvantne informacije unutar svemira 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 vrata na njih. Ove unitarne transformacije su opisane kao rotacije na Bloch sferi. Dok klasična vrata odgovaraju poznatim operacijama Booleove logike, kvantna vrata su fizički unitarni operatori.
Zbog promjenjivosti kvantnih sustava i nemogućnosti kopiranja stanja, pohranjivanje kvantnih informacija puno je teže od pohranjivanja klasičnih informacija. Ipak, uz korištenje kvantne korekcije pogrešaka kvantne informacije se u načelu još uvijek mogu pouzdano pohraniti. Postojanje kvantnih kodova za ispravljanje pogrešaka također je dovelo do mogućnosti kvantnog izračunavanja otpornog na greške.
Klasični bitovi se mogu kodirati u i naknadno dohvatiti iz konfiguracija kubita, korištenjem kvantnih vrata. Sam po sebi, jedan kubit ne može prenijeti više od jednog bita dostupnih klasičnih informacija o njegovoj pripremi. Ovo je Holevov teorem. Međutim, u supergustom kodiranju pošiljatelj, djelujući na jedan od dva zapletena kubita, može prenijeti primatelju dva bita dostupnih informacija o njihovom zajedničkom stanju.
Kvantne informacije mogu se premještati 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 Shanononove entropije, nazvane von Neumannova entropija.
U nekim se slučajevima kvantni algoritmi mogu koristiti za izvođenje računanja brže nego u bilo kojem poznatom klasičnom algoritmu. Najpoznatiji primjer za to je Shorov algoritam koji može faktorizirati brojeve u polinomskom vremenu, u usporedbi s najboljim klasičnim algoritmima koji uzimaju subeksponencijalno vrijeme. Kako je faktorizacija važan dio sigurnosti RSA enkripcije, Shorov algoritam potaknuo je novo polje post-kvantne kriptografije koja pokušava pronaći sheme šifriranja koje ostaju sigurne čak i kada su kvantna računala u igri. Drugi primjeri algoritama koji pokazuju 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 učinkovito rješava kvantno računalo poznata je kao BQP.
Kvantna distribucija ključa (QKD) omogućuje 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 još uvijek žestoko raspravlja o određenim suptilnim točkama u vezi sa sigurnošću QKD-a.
Proučavanje svih navedenih tema i razlika obuhvaća kvantnu informacijsku teoriju.
Odnos prema kvantnoj mehanici
Kvantna mehanika proučava kako se mikroskopski fizički sustavi dinamički mijenjaju u prirodi. U području kvantne teorije informacija, kvantni sustavi koji se proučavaju apstrahirani su od bilo kojeg stvarnog svijeta. Kubit bi, na primjer, fizički mogao biti foton u linearnom optičkom kvantnom računalu, ion u zarobljenom ionskom kvantnom računalu ili može biti velika zbirka atoma kao u supravodljivom kvantnom računalu. Bez obzira na fizičku implementaciju, ograničenja i značajke kubita koje implicira kvantna teorija informacija vrijede jer su svi ovi sustavi matematički opisani istim aparatom matrica gustoće nad kompleksnim brojevima. Još jedna važna razlika s kvantnom mehanikom je da, dok kvantna mehanika često proučava beskonačno-dimenzionalne sustave kao što je harmonijski oscilator, kvantna teorija informacija se bavi i sustavima s kontinuiranom promjenjivom i konačno-dimenzionalnim sustavima.
Kvantno računanje
Kvantno računanje je vrsta računanja koja koristi kolektivna svojstva kvantnih stanja, kao što su superpozicija, interferencija i zapetljanost, za izvođenje izračuna. Uređaji koji izvode kvantna računanja poznati su kao kvantna računala.: I-5 Iako su trenutna kvantna računala premala da bi nadmašila uobičajena (klasična) računala za praktične primjene, vjeruje se da su sposobni riješiti određene računske probleme, kao što je cjelobrojna faktorizacija (koji je u osnovi RSA enkripcije), znatno brži od klasičnih računala. Proučavanje kvantnog računalstva je potpolje kvantne informacijske znanosti.
Kvantno računalstvo počelo je 1980. godine kada je fizičar Paul Benioff predložio kvantnomehanički model Turingovog stroja. Richard Feynman i Yuri Manin kasnije su sugerirali da kvantno računalo ima potencijal simulirati stvari koje klasično računalo ne može učiniti. Godine 1994. Peter Shor je razvio kvantni algoritam za faktoriranje cijelih brojeva s potencijalom dešifriranja RSA šifriranih komunikacija. Godine 1998. Isaac Chuang, Neil Gershenfeld i Mark Kubinec stvorili su prvo kvantno računalo s dva kubita koje je moglo izvoditi proračune. Unatoč kontinuiranom eksperimentalnom napretku od kasnih 1990-ih, većina istraživača vjeruje da je “kvantno računanje otporno na greške [još uvijek] prilično daleki san”. Posljednjih godina u javnom i privatnom sektoru porasla su ulaganja u istraživanja kvantnog računala. Dana 23. listopada 2019., Google AI, u partnerstvu s Američkom nacionalnom upravom za aeronautiku i svemir (NASA), tvrdio je da je izvršio kvantno izračunavanje koje je bilo neizvedivo na bilo kojem klasičnom računalu, ali je li ova tvrdnja bila ili još uvijek važeća, tema je aktivno istraživanje.
Postoji nekoliko tipova kvantnih računala (također poznatih kao kvantni računalni sustavi), uključujući model kvantnog kruga, kvantni Turingov stroj, adijabatsko kvantno računalo, jednosmjerno kvantno računalo i razne kvantne stanične automate. Najrasprostranjeniji model je kvantni sklop, baziran na kvantnom bitu, ili “qubit”, 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 mjeri, uvijek je 0 ili 1; vjerojatnost bilo kojeg ishoda ovisi o kvantnom stanju kubita neposredno prije mjerenja.
Napori ka izgradnji fizičkog kvantnog računala usredotočeni su na tehnologije kao što su transmoni, ionske zamke i topološka kvantna računala, čiji je cilj stvoriti visokokvalitetne kubite.: 2–13 Ovi kubiti mogu biti dizajnirani drugačije, ovisno o modelu računanja punog kvantnog računala, bilo da su kvantna logička vrata, kvantno žarenje ili adijabatsko kvantno računanje. Trenutno postoji niz značajnih prepreka za izgradnju korisnih kvantnih računala. Posebno je teško održavati kvantna stanja kubita, jer oni pate od kvantne dekoherencije i vjernosti stanja. Kvantna računala stoga zahtijevaju ispravljanje pogrešaka.
Svaki računski problem koji se može riješiti klasičnim računalom može se riješiti i kvantnim računalom. Suprotno tome, svaki problem koji se može riješiti kvantnim računalom može se riješiti i klasičnim računalom, barem u načelu ako mu se da dovoljno vremena. Drugim riječima, kvantna računala poštuju Church-Turingovu tezu. To znači da, dok kvantna računala ne pružaju dodatne prednosti u odnosu na klasična računala u smislu izračunljivosti, kvantni algoritmi za određene probleme imaju znatno nižu vremensku složenost od odgovarajućih poznatih klasičnih algoritama. Naime, vjeruje se da su kvantna računala sposobna brzo riješiti određene probleme koje nijedno klasično računalo ne bi moglo riješiti ni u jednom izvedivom vremenu – pothvat poznat kao “kvantna nadmoć”. Proučavanje računske složenosti problema u odnosu na kvantna računala poznata je kao kvantna teorija složenosti.
Prevladavajući model kvantnog izračunavanja opisuje računanje u smislu mreže kvantnih logičkih vrata. Ovaj model se može smatrati apstraktnom linearno-algebarskom generalizacijom klasičnog sklopa. Budući da ovaj model sklopa poštuje kvantnu mehaniku, vjeruje se da je kvantno računalo sposobno za učinkovito pokretanje ovih sklopova fizički ostvarivo.
Memorija koja se sastoji od n bitova informacija ima 2^n mogućih stanja. Tako vektor koji predstavlja sva stanja memorije ima 2^n unosa (po jedan za svako stanje). Ovaj vektor se promatra kao vektor vjerojatnosti i predstavlja činjenicu da se memorija nalazi u određenom stanju.
U klasičnom pogledu, jedan bi unos imao vrijednost 1 (tj. 100% vjerojatnost da se nalazi u ovom stanju), a svi ostali unosi bili bi nula.
U kvantnoj mehanici, vektori vjerojatnosti mogu se generalizirati na operatore gustoće. Formalizam vektora kvantnog stanja obično se prvi uvodi jer je konceptualno jednostavniji i zato što se može koristiti umjesto formalizma matrice gustoće za čista stanja, gdje je cijeli kvantni sustav poznat.
kvantno se računanje može opisati kao mreža kvantnih logičkih vrata i mjerenja. Međutim, svako mjerenje se može odgoditi do kraja kvantnog računanja, iako to odgađanje može imati računsku cijenu, tako da većina kvantnih sklopova prikazuje mrežu koja se sastoji samo od kvantnih logičkih vrata i bez mjerenja.
Svako kvantno računanje (što je, u gornjem formalizmu, bilo koja unitarna matrica preko n kubita) može se predstaviti kao mreža kvantnih logičkih vrata iz prilično male obitelji vrata. Izbor obitelji vrata koja omogućuje ovu konstrukciju poznat je kao univerzalni skup vrata, budući da je računalo koje može pokretati takve sklopove univerzalno kvantno računalo. Jedan zajednički takav skup uključuje sva vrata s jednim kubitom, kao i CNOT vrata odozgo. To znači da se bilo koje kvantno izračunavanje može izvesti izvođenjem niza jednokubitnih vrata zajedno s CNOT vratima. Iako je ovaj skup vrata beskonačan, može se zamijeniti skupom konačnih vrata pozivanjem na Solovay-Kitaev teorem.
Kvantni algoritmi
Napredak u pronalaženju kvantnih algoritama obično se fokusira na ovaj model kvantnog kruga, iako postoje iznimke poput kvantnog adijabatskog algoritma. Kvantni algoritmi se mogu grubo kategorizirati prema vrsti 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 povezane kvantne algoritme za računanje diskretnih logaritama, rješavanje Pellove jednadžbe i općenito rješavanje problema skrivenih podskupina za abelove konačne grupe. Ovi algoritmi ovise o primitivu 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.[samoobjavljeni izvor?] Određeni problemi proročišta poput Simonovog problema i Bernstein–Vaziraninog problema daju dokaziva ubrzanja, iako ovo nije moguće. nalazi se u kvantnom modelu upita, koji je ograničeni model gdje je donje granice mnogo lakše dokazati i ne znači nužno ubrzavanje praktičnih problema.
Drugi problemi, uključujući simulaciju kvantnih fizikalnih procesa iz kemije i fizike čvrstog stanja, aproksimaciju određenih Jonesovih polinoma i kvantni algoritam za linearne sustave jednadžbi, 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 što se vjeruje da je malo vjerojatno.
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 povezani su s Groverovim algoritamom, 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. stabala, što je varijanta problema pretraživanja.
Kriptografske primjene
Značajna primjena kvantnog računanja je za napade na kriptografske sustave koji su trenutno u upotrebi. Vjeruje se da je cjelobrojna faktorizacija, koja podupire sigurnost kriptografskih sustava javnog ključa, računski neizvediva s običnim računalom za velike cijele brojeve ako su umnožak nekoliko prostih brojeva (npr. proizvodi dvaju prostih brojeva od 300 znamenki). Za usporedbu, kvantno računalo moglo bi učinkovito riješiti ovaj problem koristeći Shorov algoritam za pronalaženje njegovih čimbenika. Ta bi sposobnost omogućila kvantnom računalu da razbije mnoge kriptografske sustave koji se danas koriste, u smislu da bi postojao algoritam polinomskog vremena (u broju znamenki cijelog broja) za rješavanje problema. Konkretno, većina popularnih šifri javnog ključa temelji se 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 krivulje Diffie–Hellman mogu biti slomljeni. Oni se koriste za zaštitu sigurnih web stranica, šifrirane e-pošte i mnogih drugih vrsta podataka. Njihovo probijanje imalo bi značajne posljedice za elektroničku privatnost i sigurnost.
Identificiranje kriptografskih sustava koji bi mogli biti sigurni od kvantnih algoritama je tema koja se aktivno istražuje u području post-kvantne kriptografije. Neki algoritmi s javnim ključem temelje se na problemima osim cjelobrojne faktorizacije i problema diskretnog logaritma na koje se Shorov algoritam primjenjuje, poput McElieceovog kriptosustava koji se temelji na problemu u teoriji kodiranja. Također nije poznato da se kriptosustavi bazirani na rešetki razbijaju od strane kvantnih računala, a pronalaženje algoritma polinomskog vremena za rješavanje problema skrivene podgrupe diedrala, koji bi razbio mnoge kriptosustave temeljene na rešetki, dobro je 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 usporedbi s otprilike 2n u klasičnom slučaju, što znači da su simetrične duljine ključa efektivno prepolovljeno: AES-256 bi imao istu sigurnost protiv napada korištenjem Groverovog algoritma koji AES-128 ima protiv klasičnog pretraživanja grubom silom (vidi Veličina ključa).
Kvantna kriptografija potencijalno bi mogla ispuniti neke od funkcija kriptografije s javnim ključem. Kvantni bazirani kriptografski sustavi mogli bi stoga biti sigurniji od tradicionalnih sustava protiv kvantnog hakiranja.
Problemi s pretraživanjem
Najpoznatiji primjer problema koji dopušta polinomsko kvantno ubrzanje je nestrukturirano pretraživanje, pronalaženje označene stavke s popisa od n stavki u bazi podataka. To 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 nego i optimalna: pokazalo se da Groverov algoritam daje najveću moguću vjerojatnost pronalaska ž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 za pretraživanje u zbirci mogućih odgovora,
- Broj mogućih odgovora za provjeru jednak je broju ulaza u algoritam, i
- Postoji logička funkcija koja procjenjuje svaki unos i određuje je li to točan odgovor
Za probleme sa svim tim svojstvima, vrijeme rada Groverovog algoritma na kvantnom računalu mjeri se kao kvadratni korijen broja ulaza (ili elemenata u bazi podataka), za razliku od linearnog skaliranja klasičnih algoritama. Opća klasa problema na koje se Groverov algoritam može primijeniti je Boolean problem zadovoljivosti, gdje je baza podataka kroz koju algoritam iterira je baza svih mogućih odgovora. Primjer i (moguća) primjena ovoga je kreker zaporke koji pokušava pogoditi lozinku. Simetrične šifre kao što su Triple DES i AES posebno su osjetljive na ovu vrstu napada. [potreban je citat] Ova primjena kvantnog računanja glavni je interes vladinih agencija.
Simulacija kvantnih sustava
Budući da se kemija i nanotehnologija oslanjaju na razumijevanje kvantnih sustava, a takve je sustave nemoguće klasično simulirati na učinkovit način, mnogi vjeruju da će kvantna simulacija biti jedna od najvažnijih primjena kvantnog računanja. Kvantna simulacija također bi se mogla koristiti za simuliranje ponašanja atoma i čestica u neobičnim uvjetima kao što su reakcije unutar sudarača. Kvantne simulacije mogle bi se koristiti za predviđanje budućih putanja čestica i protona pod superpozicijom u eksperimentu s dvostrukim prorezom.[potreban citat] 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 adijabatski teorem za poduzimanje izračuna. Sustav je postavljen u osnovno stanje za jednostavni Hamiltonijan, koji se polako razvija u složeniji Hamiltonijan čije osnovno stanje predstavlja rješenje problema o kojem je riječ. Adijabatski teorem kaže da ako je evolucija dovoljno spora, sustav će ostati u svom osnovnom stanju cijelo vrijeme tijekom procesa.
Strojno učenje
Budući da kvantna računala mogu proizvesti rezultate koje klasična računala ne mogu proizvesti učinkovito, i budući da je kvantno računanje u osnovi linearno algebarsko, neki izražavaju nadu u razvoj kvantnih algoritama koji mogu ubrzati zadatke strojnog učenja. Na primjer, vjeruje se da kvantni algoritam za linearne sustave jednadžbi, ili “HHL algoritam”, nazvan po svojim otkrivačima Harrowu, Hassidimu i Lloydu, omogućuje ubrzanje u odnosu na klasične kolege. Neke istraživačke skupine nedavno su istraživale korištenje hardvera za kvantno žarenje za obuku Boltzmannovih strojeva i dubokih neuronskih mreža.
Računalna biologija
U području računalne biologije, kvantno računanje ima veliku ulogu u rješavanju mnogih bioloških problema. Jedan od dobro poznatih primjera bio bi u računskoj genomici i kako je računalstvo drastično smanjilo vrijeme sekvenciranja ljudskog genoma. S obzirom na to kako računalna biologija koristi generičko modeliranje i pohranu podataka, očekuje se da će se pojaviti i njezine primjene na računsku biologiju.
Računalno potpomognuto dizajniranje lijekova i generativna kemija
Duboki generativni kemijski modeli pojavljuju se kao moćni alati za ubrzanje otkrivanja lijekova. Međutim, golema veličina i složenost strukturnog prostora svih mogućih molekula sličnih lijekovima predstavljaju značajne prepreke, koje bi u budućnosti mogla prevladati kvantna računala. Kvantna računala su prirodno dobra za rješavanje složenih kvantnih problema s više tijela i stoga mogu biti instrumentalna u aplikacijama koje uključuju kvantnu kemiju. Stoga se može očekivati da će se kvantno poboljšani generativni modeli, uključujući kvantne GAN-ove, na kraju razviti u ultimativne generativne kemijske algoritme. Hibridne arhitekture koje kombiniraju kvantna računala s dubokim klasičnim mrežama, kao što su kvantni varijacijski autoenkoderi, već se mogu obučiti na komercijalno dostupnim žarionicima i koristiti za generiranje novih molekularnih struktura sličnih lijekovima.
Razvoj fizičkih kvantnih računala
Izazovi
Postoji niz tehničkih izazova u izgradnji kvantnog računala velikih razmjera. Fizičar David DiVincenzo naveo je ove zahtjeve za praktično kvantno računalo:
- 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 vrata,
- Kubiti koji se lako čitaju.
Dobavljanje dijelova za kvantna računala također je vrlo teško. Mnoga kvantna računala, poput onih koje su konstruirali Google i IBM, trebaju helij-3, nusproizvod nuklearnog istraživanja, i posebne supravodljive kabele koje proizvodi samo japanska tvrtka Coax Co.
Kontrola multi-qubit sustava zahtijeva generiranje i koordinaciju velikog broja električnih signala s tijesnom i determinističkom vremenskom razlučivosti. To je dovelo do razvoja kvantnih kontrolera koji omogućuju povezivanje s kubitima. Skaliranje ovih sustava kako bi podržali sve veći broj kubita dodatni je izazov.
Kvantna dekoherencija
Jedan od najvećih izazova vezanih uz konstruiranje kvantnih računala je kontroliranje ili uklanjanje kvantne dekoherencije. To obično znači izolaciju sustava od okoline jer interakcije s vanjskim svijetom uzrokuju dekoheriranje sustava. Međutim, postoje i drugi izvori dekoherencije. Primjeri uključuju kvantna vrata, vibracije rešetke i pozadinski termonuklearni spin fizičkog sustava koji se koristi za implementaciju kubita. Dekoherencija je nepovratna, budući da je zapravo ne-jedinstvena i obično je nešto što bi trebalo strogo kontrolirati, ako ne i izbjegavati. Vremena dekoherencije za sustave kandidate, posebno vrijeme poprečne relaksacije T2 (za NMR i MRI tehnologiju, također nazvano vrijeme defaziranja), obično se kreće između nanosekundi i sekundi pri niskoj temperaturi. Trenutno, neka kvantna računala zahtijevaju da se njihovi kubiti ohlade na 20 milikelvina (obično pomoću hladnjaka za razrjeđivanje) kako bi se spriječila značajna dekoherencija. Studija iz 2020. tvrdi da ionizirajuće zračenje poput kozmičkih zraka ipak može uzrokovati dekoheriranje određenih sustava 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, a često citirani pristup njihovom prevladavanju je oblikovanje optičkih impulsa. Stope pogrešaka obično su proporcionalne omjeru vremena rada i vremena dekoherencije, stoga se svaka operacija mora završiti mnogo brže od vremena dekoherencije.
Kao što je opisano u teoremu o kvantnom pragu, ako je stopa pogreške dovoljno mala, smatra se da je moguće koristiti kvantnu korekciju pogreške za suzbijanje pogrešaka i dekoherencije. To omogućuje da ukupno vrijeme izračuna bude duže od vremena dekoherencije ako shema ispravljanja pogrešaka može ispraviti pogreške brže nego što ih dekoherencija uvodi. Često citirana brojka za potrebnu stopu pogreške u svakoj kapiji za izračunavanje otporne na greške je 10-3, pod pretpostavkom da se šum depolarizira.
Ispunjavanje ovog uvjeta skalabilnosti moguće je za širok raspon sustava. Međutim, korištenje ispravljanja pogreš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 znamenki u broju koji se faktorira; Algoritmi za ispravljanje pogrešaka povećali bi ovu brojku za dodatni faktor L. Za 1000-bitni broj, to implicira potrebu za oko 104 bita bez ispravljanja pogreške. Uz ispravljanje pogrešaka, 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.
Vrlo drugačiji pristup problemu stabilnosti-dekoherencije je stvaranje topološkog kvantnog računala s bilonima, kvazičesticama koje se koriste kao niti i oslanjajući se na teoriju pletenica za formiranje stabilnih logičkih vrata.
Kvantna nadmoć
Kvantna nadmoć izraz je 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 najsuvremenijih klasičnih računala. Problem ne mora biti koristan, pa neki gledaju na test kvantne nadmoći samo kao na potencijalno buduće mjerilo.
U listopadu 2019., Google AI Quantum, uz pomoć NASA-e, postao je prvi koji je tvrdio da je postigao kvantnu nadmoć izvodeći izračune na kvantnom računalu Sycamore više od 3,000,000 puta brže nego što se to moglo učiniti na Summitu, koji se općenito smatra najbržim na svijetu. Računalo. Ova je tvrdnja 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 tvrdnju o kvantne nadmoći, dajući značajno smanjenje ili zatvaranje jaza između Sycamore i Sycamore klasičnih superračunala.
U prosincu 2020., grupa u USTC-u implementirala je tip uzorkovanja bozona na 76 fotona s fotonskim kvantnim računalom Jiuzhang kako bi demonstrirala kvantnu nadmoć. Autori tvrde da bi klasičnom suvremenom superračunalu bilo potrebno vrijeme računanja od 600 milijuna godina da generira broj uzoraka koji njihov kvantni procesor može generirati u 20 sekundi. Dana 16. studenog 2021. na summitu o kvantnom računarstvu IBM je predstavio 127-kubitni mikroprocesor nazvan IBM Eagle.
Fizičke implementacije
Za fizičku implementaciju kvantnog računala traži se mnogo različitih kandidata, među njima (razlikuje ih fizički sustav koji se koristi za realizaciju kubita):
- Supravodljivo kvantno računanje (kubit implementiran stanjem malih supravodljivih krugova, Josephsonovi spojevi)
- Kvantno računalo zarobljenih iona (kubit implementiran unutarnjim stanjem zarobljenih iona)
- Neutralni atomi u optičkim rešetkama (kubit implementiran unutarnjim stanjima neutralnih atoma zarobljenih u optičkoj rešetki)
- Računalo s kvantnim točkama, zasnovano na spinu (npr. Loss-DiVincenzo kvantno računalo) (kubit zadan spinskim stanjima zarobljenih elektrona)
- Računalo s kvantnim točkama, prostorno (kubit zadan položajem elektrona u dvostrukoj kvantnoj točki)
- Kvantno računalstvo korištenjem projektiranih kvantnih bunara, koje bi u principu mogle omogućiti izgradnju kvantnih računala koja rade na sobnoj temperaturi
- Spojena kvantna žica (kubit implementiran parom kvantnih žica spojenih kvantnim točkastim kontaktom)
- Kvantno računalo nuklearne magnetske rezonancije (NMRQC) implementirano s nuklearnom magnetskom rezonancijom molekula u otopini, gdje se kubiti dobivaju nuklearnim okretajima unutar otopljene molekule i ispituju radio valovima
- NMR Kane kvantna računala u čvrstom stanju (kubit ostvaren nuklearnim spinskim stanjem donora fosfora u siliciju)
- Kvantna računala elektrona na heliju (kubit je spin elektrona)
- Kvantna elektrodinamika šupljine (CQED) (kubit osigurava unutarnje stanje zarobljenih atoma spojenih na šupljine visoke finoće)
- Molekularni magnet (kubit zadan spinskim stanjima)
- Kvantno računalo ESR bazirano na fulerenu (kubit baziran na elektroničkom spinu atoma ili molekula zatvorenih u fulerenima)
- Nelinearno optičko kvantno računalo (kubiti ostvareni obradom stanja različitih modova svjetlosti kroz linearne i nelinearne elemente)
- Linearno optičko kvantno računalo (kubiti ostvareni obradom stanja različitih modova svjetlosti kroz linearne elemente npr. ogledala, razdjelnici snopa i fazni pomaci)
- Kvantno računalo zasnovano na dijamantu (kubit ostvaren elektroničkim ili nuklearnim spinom centara za praznine dušika u dijamantu)
- Kvantno računalo na bazi Bose-Einstein kondenzata
- Kvantno računalo bazirano na tranzistoru – kvantna računala s nizom s uvlačenjem pozitivnih rupa pomoću elektrostatičke zamke
- Kvantna računala bazirana na anorganskim kristalima dopiranim ionima rijetke zemlje (kubit ostvaren unutarnjim elektroničkim stanjem dodataka u optičkim vlaknima)
- Kvantna računala temeljena na ugljičnim nanosferama nalik metalu
- Veliki broj kandidata pokazuje da je kvantno računalstvo, unatoč brzom napretku, još uvijek u povojima.
Postoji niz modela kvantnog računanja, koji se razlikuju po osnovnim elementima u kojima se računanje rastavlja. Za praktične implementacije, četiri relevantna modela računanja su:
- Niz kvantnih vrata (računanje razloženo u niz kvantnih vrata od nekoliko kubita)
- Jednosmjerno kvantno računalo (računanje razloženo u slijed jednokubitnih mjerenja primijenjenih na jako zapetljano početno stanje ili stanje klastera)
- Adijabatsko kvantno računalo, bazirano na kvantnom žarenju (proračun razložen na sporu kontinuiranu transformaciju početnog Hamiltonijana u konačni Hamiltonijan, čija osnovna stanja sadrže rješenje)
- Topološko kvantno računalo (računanje razloženo na pletenje biloona u 2D rešetki)
Kvantni Turingov stroj je teoretski važan, ali fizička implementacija ovog modela nije izvediva. Pokazalo se da su sva četiri modela računanja ekvivalentna; svaki može simulirati drugog s najviše polinomskih nadmetanja.
Da biste se detaljno upoznali s nastavnim planom i programom certificiranja, možete proširiti i analizirati donju tablicu.
EITC/QI/QIF Certification Fundamentals Quantum Information Curriculum navodi didaktičke materijale otvorenog pristupa u obliku videa. Proces učenja podijeljen je u strukturu korak po korak (programi -> lekcije -> teme) koja pokriva relevantne dijelove kurikuluma. Također je osigurano neograničeno savjetovanje sa stručnjacima za domenu.
Za detalje o postupku certificiranja provjerite Kako radi.
Glavne bilješke s predavanja
U. Vazirani bilješke s predavanja:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Potporne bilješke s predavanja
L. Jacak i sur. bilješke s predavanja (s dopunskim materijalom):
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 s predavanja
Bilješke s predavanja J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Childsove bilješke s predavanja:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Bilješke s predavanja S. Aaronson:
https://scottaaronson.blog/?p=3943
Bilješke s predavanja R. de Wolfa:
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čunalstvo 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 izvanmrežne pripremne materijale za samoučenje za program EITC/QI/QIF Quantum Information Fundamentals u PDF datoteci
EITC/QI/QIF pripremni materijali – standardna verzija
Pripremni materijali za EITC/QI/QIF – proširena verzija s pitanjima za ponavljanje