EITC/QI/QIF Quantum Information Fundamentals je európsky certifikačný program IT o teoretických a praktických aspektoch kvantových informácií a kvantových výpočtov, založený na zákonoch kvantovej fyziky a nie klasickej fyziky a ponúka kvalitatívne výhody oproti ich klasickým náprotivkom.
Učebné osnovy EITC/QI/QIF Základy kvantových informácií zahŕňajú úvod do kvantovej mechaniky (vrátane zváženia experimentu s dvojitou štrbinou a interferenciou vĺn hmoty), úvod do kvantových informácií (qubity a ich geometrické znázornenie), polarizáciu svetla, princíp neurčitosti, kvantové zapletenie, EPR paradox, porušenie Bellovej nerovnosti, opustenie miestneho realizmu, kvantové spracovanie informácií (vrátane unitárnej transformácie, jedno-qubitových a dvojqubitových brán), veta o neklonovaní, kvantová teleportácia, kvantové meranie, kvantové výpočty (vrátane úvodu do multi -qubitové systémy, univerzálna rodina brán, reverzibilita výpočtu), kvantové algoritmy (vrátane Quantum Fourier Transform, Simonov algoritmus, rozšírená Churhova-Turingova práca, Shor'q kvantový faktoringový algoritmus, Groverov kvantový vyhľadávací algoritmus), kvantové pozorovateľné veličiny, Shrodingerova rovnica implementácie qubitov, teória kvantovej zložitosti, adiabatický kvantový výpočet ion, BQP, úvod do spinu, v rámci nasledujúcej štruktúry, zahŕňajúcej komplexný videodidaktický obsah ako referenciu pre túto certifikáciu EITC.
Kvantová informácia je informácia o stave kvantového systému. Je to základná entita štúdia v teórii kvantovej informácie a možno s ňou manipulovať pomocou techník kvantového spracovania informácií. Kvantová informácia sa vzťahuje na technickú definíciu z hľadiska Von Neumannovej entropie, ako aj na všeobecný výpočtový termín.
Kvantové informácie a výpočty sú interdisciplinárnou oblasťou, ktorá okrem iných oblastí zahŕňa kvantovú mechaniku, informatiku, teóriu informácií, filozofiu a kryptografiu. Jeho štúdium je relevantné aj pre disciplíny ako kognitívna veda, psychológia a neuroveda. Jeho hlavným zameraním je získavanie informácií z hmoty v mikroskopickom meradle. Pozorovanie vo vede je základným osobitým kritériom reality a jedným z najdôležitejších spôsobov získavania informácií. Preto je meranie potrebné na kvantifikáciu pozorovania, čo je kľúčové pre vedeckú metódu. V kvantovej mechanike sa kvôli princípu neurčitosti nedajú presne zmerať nekomutujúce pozorovateľné veličiny súčasne, keďže vlastný stav na jednej báze nie je vlastný stav na druhej báze. Keďže obe premenné nie sú súčasne dobre definované, kvantový stav nemôže nikdy obsahovať definitívne informácie o oboch premenných. Vďaka tejto základnej vlastnosti merania v kvantovej mechanike možno túto teóriu vo všeobecnosti charakterizovať ako nedeterministickú na rozdiel od klasickej mechaniky, ktorá je plne deterministická. Indeterminizmus kvantových stavov charakterizuje informácie definované ako stavy kvantových systémov. Z matematického hľadiska sú tieto stavy v superpozíciách (lineárnych kombináciách) stavov klasických systémov.
Keďže informácia je vždy zakódovaná v stave fyzického systému, je fyzická sama o sebe. Zatiaľ čo kvantová mechanika sa zaoberá skúmaním vlastností hmoty na mikroskopickej úrovni, kvantová informačná veda sa zameriava na získavanie informácií z týchto vlastností a kvantové výpočty manipulujú a spracovávajú kvantové informácie – vykonávajú logické operácie – pomocou techník kvantového spracovania informácií.
Kvantové informácie, podobne ako klasické informácie, možno spracovať pomocou počítačov, prenášať z jedného miesta na druhé, manipulovať s nimi pomocou algoritmov a analyzovať pomocou počítačovej vedy a matematiky. Rovnako ako základná jednotka klasickej informácie je bit, kvantová informácia sa zaoberá qubitmi, ktoré môžu existovať v superpozícii 0 a 1 (súčasne do istej miery pravdivé a nepravdivé). Kvantové informácie môžu existovať aj v takzvaných zapletených stavoch, ktoré vo svojich meraniach prejavujú čisto neklasické nelokálne korelácie, čo umožňuje aplikácie, ako je kvantová teleportácia. Úroveň zapletenia sa dá merať pomocou Von Neumannovej entropie, ktorá je tiež mierou kvantovej informácie. V poslednej dobe sa oblasť kvantových počítačov stala veľmi aktívnou oblasťou výskumu kvôli možnosti narušiť moderné výpočty, komunikáciu a kryptografiu.
História kvantovej informácie sa začala na prelome 20. storočia, keď sa klasická fyzika zmenila na kvantovú fyziku. Teórie klasickej fyziky predpovedali absurdity, ako je ultrafialová katastrofa alebo elektróny v špirále do jadra. Najprv sa tieto problémy odstránili pridaním ad hoc hypotézy do klasickej fyziky. Čoskoro sa ukázalo, že je potrebné vytvoriť novú teóriu, aby tieto absurdity dali zmysel, a zrodila sa teória kvantovej mechaniky.
Kvantovú mechaniku sformuloval Schrödinger pomocou vlnovej mechaniky a Heisenberg pomocou maticovej mechaniky. Ekvivalencia týchto metód bola dokázaná neskôr. Ich formulácie popisovali dynamiku mikroskopických systémov, ale mali niekoľko neuspokojivých aspektov pri opise procesov merania. Von Neumann formuloval kvantovú teóriu pomocou operátorovej algebry spôsobom, ktorý opísal meranie aj dynamiku. Tieto štúdie zdôrazňovali skôr filozofické aspekty merania než kvantitatívny prístup k získavaniu informácií prostredníctvom meraní.
V 1960. rokoch Stratonovich, Helstrom a Gordon navrhli formuláciu optickej komunikácie pomocou kvantovej mechaniky. Toto bol prvý historický objav kvantovej teórie informácie. Študovali hlavne pravdepodobnosti chýb a komunikačné kapacity. Neskôr Holevo získal hornú hranicu komunikačnej rýchlosti pri prenose klasickej správy cez kvantový kanál.
V 1970-tych rokoch sa začali vyvíjať techniky manipulácie s kvantovými stavmi jedného atómu, ako je atómová pasca a skenovací tunelový mikroskop, čo umožňuje izolovať jednotlivé atómy a usporiadať ich do polí. Pred týmto vývojom nebola presná kontrola nad jednotlivými kvantovými systémami možná a experimenty využívali hrubšiu, simultánnu kontrolu nad veľkým počtom kvantových systémov. Vývoj životaschopných jednostavových manipulačných techník viedol k zvýšenému záujmu o oblasť kvantových informácií a výpočtov.
V 1980. rokoch sa objavil záujem o to, či by bolo možné použiť kvantové efekty na vyvrátenie Einsteinovej teórie relativity. Ak by bolo možné naklonovať neznámy kvantový stav, bolo by možné použiť zapletené kvantové stavy na prenos informácií rýchlejšie ako je rýchlosť svetla, čo vyvracia Einsteinovu teóriu. No-klonovacia veta však ukázala, že takéto klonovanie je nemožné. Veta bola jedným z prvých výsledkov kvantovej teórie informácie.
Vývoj z kryptografie
Napriek všetkému vzrušeniu a záujmu o štúdium izolovaných kvantových systémov a snahu nájsť spôsob, ako obísť teóriu relativity, výskum v teórii kvantovej informácie v 1980. rokoch ustrnul. Približne v rovnakom čase sa však do kvantových informácií a výpočtov začala zapájať iná cesta: kryptografia. Vo všeobecnom zmysle je kryptografia problémom komunikácie alebo výpočtov, ktoré zahŕňajú dve alebo viac strán, ktoré si navzájom nemusia dôverovať.
Bennett a Brassard vyvinuli komunikačný kanál, na ktorom nie je možné odpočúvať bez toho, aby bol odhalený, spôsob tajnej komunikácie na veľké vzdialenosti pomocou kvantového kryptografického protokolu BB84. Kľúčovou myšlienkou bolo použitie základného princípu kvantovej mechaniky, že pozorovanie ruší pozorované, a zavedenie odpočúvania v zabezpečenej komunikačnej línii umožní dvom stranám, ktoré sa pokúšajú komunikovať, okamžite dozvedieť o prítomnosti odpočúvania.
Vývoj z informatiky a matematiky
S príchodom revolučných myšlienok Alana Turinga o programovateľnom počítači alebo Turingovom stroji ukázal, že akýkoľvek výpočet v reálnom svete možno previesť na ekvivalentný výpočet zahŕňajúci Turingov stroj. Toto je známe ako Churchova-Turingova téza.
Čoskoro boli vyrobené prvé počítače a počítačový hardvér rástol takým rýchlym tempom, že tento rast bol prostredníctvom skúseností vo výrobe kodifikovaný do empirického vzťahu nazývaného Moorov zákon. Tento „zákon“ je projektívny trend, ktorý hovorí, že počet tranzistorov v integrovanom obvode sa zdvojnásobí každé dva roky. Keď sa tranzistory začali zmenšovať a zmenšovať, aby naplnili väčší výkon na plochu, v elektronike sa začali objavovať kvantové efekty, čo malo za následok neúmyselné rušenie. To viedlo k nástupu kvantovej výpočtovej techniky, ktorá využívala kvantovú mechaniku na navrhovanie algoritmov.
V tomto bode kvantové počítače sľubovali, že budú pri určitých špecifických problémoch oveľa rýchlejšie ako klasické počítače. Jeden takýto príklad problému vyvinuli David Deutsch a Richard Jozsa, známy ako Deutsch–Jozsov algoritmus. Tento problém sa však prakticky neuplatňuje. Peter Shor v roku 1994 prišiel s veľmi dôležitým a praktickým problémom, jedným z hľadania prvočíselných faktorov celého čísla. Problém diskrétneho logaritmu, ako sa nazýval, by sa dal efektívne vyriešiť na kvantovom počítači, ale nie na klasickom počítači, čo ukazuje, že kvantové počítače sú výkonnejšie ako Turingove stroje.
Vývoj z teórie informácie
Približne v čase, keď počítačová veda robila revolúciu, rovnako ako teória informácií a komunikácia prostredníctvom Clauda Shannona. Shannon vyvinul dve základné vety teórie informácie: vetu o kódovaní nehlučného kanála a vetu o kódovaní hlučného kanála. Ukázal tiež, že na ochranu odosielaných informácií možno použiť kódy na opravu chýb.
Kvantová teória informácie tiež sledovala podobnú trajektóriu, Ben Schumacher v roku 1995 vytvoril analógiu k Shannonovej vete o nehlučnom kódovaní pomocou qubit. Vyvinula sa aj teória korekcie chýb, ktorá umožňuje kvantovým počítačom vykonávať efektívne výpočty bez ohľadu na šum a spoľahlivo komunikovať cez hlučné kvantové kanály.
Qubity a teória informácie
Kvantová informácia sa výrazne líši od klasickej informácie, stelesnenej bitom, mnohými pozoruhodnými a neznámymi spôsobmi. Zatiaľ čo základnou jednotkou klasickej informácie je bit, najzákladnejšou jednotkou kvantovej informácie je qubit. Klasická informácia sa meria pomocou Shannonovej entropie, zatiaľ čo kvantovo-mechanickým analógom je Von Neumannova entropia. Štatistický súbor kvantových mechanických systémov je charakterizovaný maticou hustoty. Mnohé miery entropie v klasickej teórii informácie možno zovšeobecniť aj na kvantový prípad, ako je Holevova entropia a podmienená kvantová entropia.
Na rozdiel od klasických digitálnych stavov (ktoré sú diskrétne) má qubit spojitú hodnotu, ktorú možno opísať smerom na Blochovej sfére. Napriek tomu, že je qubit takto nepretržite oceňovaný, je najmenšou možnou jednotkou kvantovej informácie a napriek tomu, že stav qubit je nepretržite hodnotený, nie je možné presne zmerať hodnotu. Päť známych teorémov popisuje limity manipulácie s kvantovými informáciami:
- no-teleportačný teorém, ktorý hovorí, že qubit nemožno (úplne) previesť na klasické bity; to znamená, že sa nedá úplne „čítať“,
- veta o neklonovaní, ktorá zabraňuje kopírovaniu ľubovoľného qubitu,
- no-deleting teorém, ktorý zabraňuje vymazaniu ľubovoľného qubitu,
- teorém o zákaze vysielania, ktorý zabraňuje doručeniu ľubovoľného qubitu viacerým príjemcom, hoci ho možno preniesť z miesta na miesto (napr. prostredníctvom kvantovej teleportácie),
- no-hiding teorém, ktorý demonštruje zachovanie kvantovej informácie.Tieto vety dokazujú, že kvantová informácia vo vesmíre je zachovaná a otvárajú jedinečné možnosti v kvantovom spracovaní informácií.
Kvantové spracovanie informácií
Stav qubitu obsahuje všetky jeho informácie. Tento stav je často vyjadrený ako vektor na Blochovej sfére. Tento stav je možné zmeniť aplikáciou lineárnych transformácií alebo kvantových brán. Tieto unitárne transformácie sú opísané ako rotácie na Blochovej sfére. Zatiaľ čo klasické brány zodpovedajú známym operáciám booleovskej logiky, kvantové brány sú fyzické jednotné operátory.
Kvôli volatilite kvantových systémov a nemožnosti kopírovania stavov je ukladanie kvantovej informácie oveľa náročnejšie ako ukladanie klasickej informácie. Napriek tomu s použitím kvantovej korekcie chýb môžu byť kvantové informácie v princípe stále spoľahlivo uložené. Existencia kódov na opravu kvantových chýb tiež viedla k možnosti kvantového výpočtu odolného voči chybám.
Klasické bity môžu byť zakódované a následne získané z konfigurácií qubitov pomocou kvantových brán. Samotný qubit môže poskytnúť najviac jeden bit prístupnej klasickej informácie o jeho príprave. Toto je Holevova veta. Avšak v superhustom kódovaní môže odosielateľ pôsobením na jeden z dvoch zapletených qubitov sprostredkovať dva bity prístupných informácií o ich spoločnom stave do prijímača.
Kvantové informácie sa môžu pohybovať v kvantovom kanáli, analogicky s konceptom klasického komunikačného kanála. Kvantové správy majú konečnú veľkosť, meranú v qubitoch; kvantové kanály majú konečnú kapacitu kanála, meranú v qubitoch za sekundu.
Kvantové informácie a zmeny v kvantových informáciách je možné kvantitatívne merať pomocou analógu Shannonovej entropie, nazývaného von Neumannova entropia.
V niektorých prípadoch môžu byť kvantové algoritmy použité na vykonávanie výpočtov rýchlejšie ako v akomkoľvek známom klasickom algoritme. Najznámejším príkladom je Shorov algoritmus, ktorý dokáže počítať čísla v polynomiálnom čase v porovnaní s najlepšími klasickými algoritmami, ktoré využívajú sub-exponenciálny čas. Keďže faktorizácia je dôležitou súčasťou bezpečnosti šifrovania RSA, Shorov algoritmus podnietil novú oblasť postkvantovej kryptografie, ktorá sa snaží nájsť šifrovacie schémy, ktoré zostanú bezpečné, aj keď sú v hre kvantové počítače. Medzi ďalšie príklady algoritmov, ktoré demonštrujú kvantovú prevahu, patrí Groverov vyhľadávací algoritmus, kde kvantový algoritmus poskytuje kvadratické zrýchlenie oproti najlepšiemu možnému klasickému algoritmu. Trieda zložitosti problémov efektívne riešiteľných kvantovým počítačom je známa ako BQP.
Kvantová distribúcia kľúčov (QKD) umožňuje bezpodmienečne bezpečný prenos klasických informácií na rozdiel od klasického šifrovania, ktoré sa dá v princípe vždy prelomiť, ak nie v praxi. Všimnite si, že o určitých jemných bodoch týkajúcich sa bezpečnosti QKD sa stále intenzívne diskutuje.
Štúdium všetkých vyššie uvedených tém a rozdielov zahŕňa kvantovú teóriu informácie.
Vzťah ku kvantovej mechanike
Kvantová mechanika je veda o tom, ako sa v prírode dynamicky menia mikroskopické fyzikálne systémy. V oblasti kvantovej teórie informácie sú študované kvantové systémy abstrahované od akéhokoľvek náprotivku v reálnom svete. Qubit môže byť napríklad fyzicky fotón v lineárnom optickom kvantovom počítači, ión v zachytenom iónovom kvantovom počítači alebo to môže byť veľká zbierka atómov ako v supravodivom kvantovom počítači. Bez ohľadu na fyzickú implementáciu platia limity a vlastnosti qubitov, ktoré implikuje kvantová teória informácie, pretože všetky tieto systémy sú matematicky opísané rovnakým aparátom matíc hustoty nad komplexnými číslami. Ďalším dôležitým rozdielom v porovnaní s kvantovou mechanikou je to, že zatiaľ čo kvantová mechanika často študuje systémy s nekonečnými rozmermi, ako je harmonický oscilátor, kvantová teória informácie sa týka systémov spojitých premenných a systémov s konečnou veľkosťou.
Kvantový výpočet
Kvantové počítanie je typ výpočtu, ktorý na vykonávanie výpočtov využíva kolektívne vlastnosti kvantových stavov, ako je superpozícia, interferencia a zapletenie. Zariadenia, ktoré vykonávajú kvantové výpočty, sú známe ako kvantové počítače.: I-5 Hoci súčasné kvantové počítače sú príliš malé na to, aby prekonali bežné (klasické) počítače pre praktické aplikácie, verí sa, že sú schopné riešiť určité výpočtové problémy, ako je faktorizácia na celé číslo. (ktorý je základom šifrovania RSA), podstatne rýchlejšie ako klasické počítače. Štúdium kvantových počítačov je podoblasťou kvantovej informačnej vedy.
Kvantové výpočty sa začali v roku 1980, keď fyzik Paul Benioff navrhol kvantovo-mechanický model Turingovho stroja. Richard Feynman a Yuri Manin neskôr navrhli, že kvantový počítač má potenciál simulovať veci, ktoré klasický počítač reálne nedokáže. V roku 1994 Peter Shor vyvinul kvantový algoritmus na faktorizáciu celých čísel s potenciálom dešifrovať komunikáciu šifrovanú RSA. V roku 1998 Isaac Chuang, Neil Gershenfeld a Mark Kubinec vytvorili prvý dvojqubitový kvantový počítač, ktorý dokázal vykonávať výpočty. Napriek pokračujúcemu experimentálnemu pokroku od konca 1990. rokov 23. storočia väčšina vedcov verí, že „kvantové výpočty odolné voči chybám sú stále dosť vzdialeným snom“. V posledných rokoch vzrástli investície do kvantového výpočtového výskumu vo verejnom aj súkromnom sektore. Dňa 2019. októbra XNUMX spoločnosť Google AI v spolupráci s americkým Národným úradom pre letectvo a vesmír (NASA) tvrdila, že vykonala kvantový výpočet, ktorý bol nerealizovateľný na žiadnom klasickom počítači, ale či toto tvrdenie bolo alebo stále platí, je témou aktívny výskum.
Existuje niekoľko typov kvantových počítačov (známych aj ako kvantové počítačové systémy), vrátane modelu kvantového obvodu, kvantového Turingovho stroja, adiabatického kvantového počítača, jednosmerného kvantového počítača a rôznych kvantových bunkových automatov. Najpoužívanejším modelom je kvantový obvod založený na kvantovom bite alebo „qubit“, ktorý je trochu analogický s bitom v klasickom výpočte. Qubit môže byť v kvantovom stave 1 alebo 0 alebo v superpozícii stavov 1 a 0. Pri meraní je však vždy 0 alebo 1; pravdepodobnosť jedného výsledku závisí od kvantového stavu qubitu bezprostredne pred meraním.
Úsilie o vybudovanie fyzického kvantového počítača sa zameriava na technológie, ako sú transmóny, iónové pasce a topologické kvantové počítače, ktorých cieľom je vytvárať vysokokvalitné qubity.: 2–13 Tieto qubity môžu byť navrhnuté odlišne v závislosti od výpočtového modelu úplného kvantového počítača, či už kvantové logické hradlá, kvantové žíhanie alebo adiabatické kvantové výpočty. V súčasnosti existuje množstvo významných prekážok pri konštrukcii užitočných kvantových počítačov. Je obzvlášť ťažké udržiavať kvantové stavy qubitov, pretože trpia kvantovou dekoherenciou a vernosťou stavu. Kvantové počítače preto vyžadujú opravu chýb.
Akýkoľvek výpočtový problém, ktorý dokáže vyriešiť klasický počítač, dokáže vyriešiť aj kvantový počítač. A naopak, každý problém, ktorý dokáže vyriešiť kvantový počítač, môže byť vyriešený aj klasickým počítačom, aspoň v zásade s dostatočným časom. Inými slovami, kvantové počítače sa riadia Church-Turingovou tézou. To znamená, že zatiaľ čo kvantové počítače neposkytujú žiadne ďalšie výhody oproti klasickým počítačom z hľadiska vypočítateľnosti, kvantové algoritmy pre určité problémy majú výrazne nižšiu časovú zložitosť ako zodpovedajúce známe klasické algoritmy. Predovšetkým sa verí, že kvantové počítače sú schopné rýchlo vyriešiť určité problémy, ktoré žiadny klasický počítač nedokáže vyriešiť v akomkoľvek prijateľnom čase – výkon známy ako „kvantová nadradenosť“. Štúdium výpočtovej zložitosti problémov s ohľadom na kvantové počítače je známe ako teória kvantovej zložitosti.
Prevládajúci model kvantového výpočtu popisuje výpočet v podmienkach siete kvantových logických brán. Tento model si možno predstaviť ako abstraktné lineárne-algebraické zovšeobecnenie klasického obvodu. Keďže tento model obvodu sa riadi kvantovou mechanikou, kvantový počítač schopný efektívne prevádzkovať tieto obvody sa považuje za fyzicky realizovateľný.
Pamäť pozostávajúca z n bitov informácií má 2^n možných stavov. Vektor reprezentujúci všetky stavy pamäte má teda 2^n záznamov (jeden pre každý stav). Tento vektor sa považuje za vektor pravdepodobnosti a predstavuje skutočnosť, že pamäť sa nachádza v určitom stave.
V klasickom pohľade by jeden záznam mal hodnotu 1 (tj 100% pravdepodobnosť, že bude v tomto stave) a všetky ostatné záznamy by boli nula.
V kvantovej mechanike možno vektory pravdepodobnosti zovšeobecniť na operátory hustoty. Kvantový stavový vektorový formalizmus sa zvyčajne zavádza ako prvý, pretože je koncepčne jednoduchší a pretože ho možno použiť namiesto formalizmu matice hustoty pre čisté stavy, kde je známy celý kvantový systém.
kvantový výpočet možno opísať ako sieť kvantových logických brán a meraní. Akékoľvek meranie však môže byť odložené na koniec kvantového výpočtu, hoci toto odloženie môže byť spojené s výpočtovými nákladmi, takže väčšina kvantových obvodov zobrazuje sieť pozostávajúcu iba z kvantových logických brán a bez meraní.
Akýkoľvek kvantový výpočet (čo je vo vyššie uvedenom formalizme akákoľvek unitárna matica nad n qubitmi) môže byť reprezentovaný ako sieť kvantových logických brán z pomerne malej rodiny brán. Voľba rodiny brán, ktorá umožňuje túto konštrukciu, je známa ako sada univerzálnych brán, keďže počítač, ktorý môže spúšťať takéto obvody, je univerzálny kvantový počítač. Jedna spoločná takáto sada obsahuje všetky jedno-qubitové brány, ako aj bránu CNOT zhora. To znamená, že akýkoľvek kvantový výpočet možno vykonať vykonaním sekvencie jedno-qubitových brán spolu s bránami CNOT. Hoci je táto množina brán nekonečná, možno ju nahradiť množinou konečných brán odvolaním sa na Solovay-Kitaevovu vetu.
Kvantové algoritmy
Pokrok pri hľadaní kvantových algoritmov sa zvyčajne zameriava na tento model kvantového obvodu, hoci existujú výnimky, ako je kvantový adiabatický algoritmus. Kvantové algoritmy možno zhruba kategorizovať podľa typu zrýchlenia dosiahnutého v porovnaní s príslušnými klasickými algoritmami.
Kvantové algoritmy, ktoré ponúkajú viac než len polynomické zrýchlenie oproti najznámejšiemu klasickému algoritmu, zahŕňajú Shorov algoritmus na faktorizáciu a súvisiace kvantové algoritmy na počítanie diskrétnych logaritmov, riešenie Pellovej rovnice a všeobecnejšie riešenie skrytého problému podgrupy pre abelovské konečné grupy. Tieto algoritmy závisia od primitíva kvantovej Fourierovej transformácie. Nebol nájdený žiadny matematický dôkaz, ktorý by dokazoval, že rovnako rýchly klasický algoritmus nemožno objaviť, aj keď sa to považuje za nepravdepodobné.[vlastne publikovaný zdroj?] Určité problémy veštcov, ako je Simonov problém a Bernstein-Vaziraniho problém, poskytujú preukázateľné zrýchlenie, hoci toto je v modeli kvantového dotazovania, čo je obmedzený model, kde sa spodné hranice oveľa ľahšie dokazujú a nemusí sa nevyhnutne premietnuť do zrýchlenia praktických problémov.
Iné problémy, vrátane simulácie kvantových fyzikálnych procesov z chémie a fyziky pevných látok, aproximácia určitých Jonesových polynómov a kvantový algoritmus pre lineárne systémy rovníc, majú kvantové algoritmy, zdá sa, že poskytujú zrýchlenie super-polynómov a sú úplné BQP. Pretože tieto problémy sú úplné BQP, rovnako rýchly klasický algoritmus pre ne by znamenal, že žiadny kvantový algoritmus neposkytuje super-polynomiálne zrýchlenie, čo sa považuje za nepravdepodobné.
Niektoré kvantové algoritmy, ako je Groverov algoritmus a zosilnenie amplitúdy, poskytujú polynómové zrýchlenie oproti zodpovedajúcim klasickým algoritmom. Hoci tieto algoritmy poskytujú porovnateľne mierne kvadratické zrýchlenie, sú široko použiteľné, a teda poskytujú zrýchlenie pre širokú škálu problémov. Mnoho príkladov preukázateľných kvantových zrýchlení pri problémoch s dotazmi súvisí s Groverovým algoritmom, vrátane Brassardovho, Høyerovho a Tappovho algoritmu na nájdenie kolízií vo funkciách dva ku jednej, ktorý používa Groverov algoritmus, a Farhiho, Goldstoneovho a Gutmannovho algoritmu na vyhodnotenie NAND. stromy, čo je variant problému vyhľadávania.
Kryptografické aplikácie
Významnou aplikáciou kvantových výpočtov sú útoky na kryptografické systémy, ktoré sa v súčasnosti používajú. Faktorizácia celých čísel, ktorá je základom bezpečnosti kryptografických systémov s verejným kľúčom, sa považuje za výpočtovo neuskutočniteľnú s bežným počítačom pre veľké celé čísla, ak sú súčinom niekoľkých prvočísel (napr. súčin dvoch 300-ciferných prvočísiel). Na porovnanie, kvantový počítač by mohol efektívne vyriešiť tento problém pomocou Shorovho algoritmu na nájdenie jeho faktorov. Táto schopnosť by umožnila kvantovému počítaču prelomiť mnohé dnes používané kryptografické systémy v tom zmysle, že by existoval polynomiálny časový (v počte číslic celého čísla) algoritmus na vyriešenie problému. Najmä väčšina populárnych šifier s verejným kľúčom je založená na obtiažnosti faktoringu celých čísel alebo na probléme diskrétneho logaritmu, pričom oboje možno vyriešiť pomocou Shorovho algoritmu. Najmä algoritmy RSA, Diffie–Hellman a eliptická krivka Diffie–Hellman by mohli byť porušené. Používajú sa na ochranu zabezpečených webových stránok, šifrovaných e-mailov a mnohých ďalších typov údajov. Ich porušenie by malo významné dôsledky pre elektronické súkromie a bezpečnosť.
Identifikácia kryptografických systémov, ktoré môžu byť zabezpečené proti kvantovým algoritmom, je aktívne skúmanou témou v oblasti postkvantovej kryptografie. Niektoré algoritmy verejného kľúča sú založené na problémoch iných ako celočíselná faktorizácia a problémy s diskrétnym logaritmom, na ktoré sa vzťahuje Shorov algoritmus, ako napríklad McElieceov kryptosystém založený na probléme v teórii kódovania. O kryptosystémoch založených na mriežke tiež nie je známe, že by ich kvantové počítače prelomili, a nájdenie polynomiálneho časového algoritmu na riešenie problému dihedrálnej skrytej podskupiny, ktorý by zlomil mnohé kryptosystémy založené na mriežke, je dobre preštudovaný otvorený problém. Bolo dokázané, že aplikácia Groverovho algoritmu na prelomenie symetrického (tajného kľúča) algoritmu hrubou silou si vyžaduje čas, ktorý sa rovná približne 2n/2 vyvolaniam základného kryptografického algoritmu, v porovnaní s približne 2n v klasickom prípade, čo znamená, že dĺžky symetrického kľúča sú efektívne polovičné: AES-256 by mal rovnaké zabezpečenie proti útoku pomocou Groverovho algoritmu, aké má AES-128 proti klasickému hľadaniu hrubou silou (pozri Veľkosť kľúča).
Kvantová kryptografia by potenciálne mohla plniť niektoré funkcie kryptografie s verejným kľúčom. Kvantové kryptografické systémy by preto mohli byť bezpečnejšie ako tradičné systémy proti kvantovému hackingu.
Problémy s vyhľadávaním
Najznámejším príkladom problému pripúšťajúceho polynomické kvantové zrýchlenie je neštruktúrované vyhľadávanie, nájdenie označenej položky zo zoznamu n položiek v databáze. Dá sa to vyriešiť Groverovým algoritmom pomocou O(sqrt(n)) dotazov do databázy, čo je kvadraticky menej ako Omega(n) dotazov vyžadovaných pre klasické algoritmy. V tomto prípade je výhoda nielen preukázateľná, ale aj optimálna: ukázalo sa, že Groverov algoritmus poskytuje maximálnu možnú pravdepodobnosť nájdenia požadovaného prvku pre ľubovoľný počet vyhľadávaní veštcov.
Problémy, ktoré je možné vyriešiť pomocou Groverovho algoritmu, majú nasledujúce vlastnosti:
- V kolekcii možných odpovedí neexistuje žiadna vyhľadávateľná štruktúra,
- Počet možných odpovedí na kontrolu je rovnaký ako počet vstupov do algoritmu a
- Existuje boolovská funkcia, ktorá vyhodnotí každý vstup a určí, či je to správna odpoveď
Pre problémy so všetkými týmito vlastnosťami je čas chodu Groverovho algoritmu na kvantovom počítači škálovaný ako druhá odmocnina počtu vstupov (alebo prvkov v databáze), na rozdiel od lineárneho škálovania klasických algoritmov. Všeobecnou triedou problémov, na ktoré možno použiť Groverov algoritmus, je booleovský problém splniteľnosti, kde databáza, cez ktorú algoritmus iteruje, je databáza všetkých možných odpovedí. Príkladom a (možnou) aplikáciou tohto je cracker hesiel, ktorý sa pokúša uhádnuť heslo. Symetrické šifry ako Triple DES a AES sú obzvlášť zraniteľné voči tomuto druhu útoku. [pochvalné znenie] Táto aplikácia kvantových výpočtov je hlavným záujmom vládnych agentúr.
Simulácia kvantových systémov
Keďže chémia a nanotechnológia sa spoliehajú na pochopenie kvantových systémov a takéto systémy nie je možné efektívne simulovať klasicky, mnohí veria, že kvantová simulácia bude jednou z najdôležitejších aplikácií kvantových počítačov. Kvantová simulácia by sa mohla použiť aj na simuláciu správania atómov a častíc za neobvyklých podmienok, ako sú reakcie vo vnútri zrážača. Kvantové simulácie by sa mohli použiť na predpovedanie budúcich dráh častíc a protónov pod superpozíciou v experimente s dvojitou štrbinou.[potrebný odkaz] Asi 2 % ročného globálneho energetického výstupu sa použijú na fixáciu dusíka na výrobu amoniaku pre Haberov proces v poľnohospodárstve priemysel hnojív, zatiaľ čo prirodzene sa vyskytujúce organizmy tiež produkujú amoniak. Kvantové simulácie môžu byť použité na pochopenie tohto procesu zvyšujúceho produkciu.
Kvantové žíhanie a adiabatická optimalizácia
Kvantové žíhanie alebo adiabatický kvantový výpočet sa pri vykonávaní výpočtov spolieha na adiabatickú vetu. Systém sa umiestni do základného stavu pre jednoduchý hamiltonián, ktorý sa pomaly vyvíja na komplikovanejší hamiltonián, ktorého základný stav predstavuje riešenie daného problému. Adiabatická veta hovorí, že ak je vývoj dostatočne pomalý, systém zostane počas celého procesu vo svojom základnom stave.
Strojové učenie
Keďže kvantové počítače dokážu produkovať výstupy, ktoré klasické počítače nedokážu efektívne produkovať, a keďže kvantové výpočty sú v podstate lineárne algebraické, niektorí vyjadrujú nádej na vývoj kvantových algoritmov, ktoré môžu urýchliť úlohy strojového učenia. Napríklad sa verí, že kvantový algoritmus pre lineárne systémy rovníc alebo „HHL Algorithm“, pomenovaný po jeho objaviteľoch Harrow, Hassidim a Lloyd, poskytuje zrýchlenie oproti klasickým náprotivkom. Niektoré výskumné skupiny nedávno skúmali využitie hardvéru na kvantové žíhanie na tréning Boltzmannových strojov a hlbokých neurónových sietí.
Výpočtová biológia
V oblasti výpočtovej biológie zohrala kvantová výpočtová technika veľkú úlohu pri riešení mnohých biologických problémov. Jedným z dobre známych príkladov by bola výpočtová genomika a to, ako výpočtová technika drasticky skrátila čas na sekvenovanie ľudského genómu. Vzhľadom na to, ako výpočtová biológia využíva modelovanie a ukladanie generických údajov, očakáva sa, že sa objavia aj jej aplikácie vo výpočtovej biológii.
Počítačom podporovaný dizajn liekov a generatívna chémia
Modely hlbokej generatívnej chémie sa javia ako silné nástroje na urýchlenie objavovania liekov. Obrovská veľkosť a zložitosť štrukturálneho priestoru všetkých možných molekúl podobných liekom však predstavuje značné prekážky, ktoré by v budúcnosti mohli prekonať kvantové počítače. Kvantové počítače sú prirodzene dobré na riešenie zložitých kvantových problémov s mnohými telesami, a preto môžu byť nápomocné pri aplikáciách zahŕňajúcich kvantovú chémiu. Preto možno očakávať, že kvantovo vylepšené generatívne modely vrátane kvantových GAN sa nakoniec môžu vyvinúť na konečné algoritmy generatívnej chémie. Hybridné architektúry kombinujúce kvantové počítače s hlbokými klasickými sieťami, ako sú Quantum Variational Autoencoders, už možno trénovať na komerčne dostupných žíhadlách a použiť na generovanie nových molekulárnych štruktúr podobných liekom.
Vývoj fyzikálnych kvantových počítačov
Výzvy
Pri budovaní rozsiahleho kvantového počítača existuje množstvo technických výziev. Fyzik David DiVincenzo uviedol tieto požiadavky na praktický kvantový počítač:
- Fyzicky škálovateľné na zvýšenie počtu qubitov,
- Qubity, ktoré možno inicializovať na ľubovoľné hodnoty,
- Kvantové brány, ktoré sú rýchlejšie ako dekoherenčný čas,
- Univerzálna súprava brány,
- Qubits, ktoré sa dajú ľahko prečítať.
Získavanie dielov pre kvantové počítače je tiež veľmi ťažké. Mnoho kvantových počítačov, ako sú tie skonštruované spoločnosťami Google a IBM, potrebuje hélium-3, vedľajší produkt jadrového výskumu, a špeciálne supravodivé káble vyrobené iba japonskou spoločnosťou Coax Co.
Riadenie multi-qubitových systémov vyžaduje generovanie a koordináciu veľkého počtu elektrických signálov s pevným a deterministickým časovým rozlíšením. To viedlo k vývoju kvantových ovládačov, ktoré umožňujú prepojenie s qubitmi. Škálovanie týchto systémov na podporu rastúceho počtu qubitov je ďalšou výzvou.
Kvantová dekoherencia
Jednou z najväčších výziev spojených s konštrukciou kvantových počítačov je kontrola alebo odstránenie kvantovej dekoherencie. To zvyčajne znamená izoláciu systému od jeho prostredia, pretože interakcie s vonkajším svetom spôsobujú dekoherenciu systému. Existujú však aj iné zdroje dekoherencie. Príklady zahŕňajú kvantové brány a mriežkové vibrácie a termonukleárne spiny na pozadí fyzického systému používaného na implementáciu qubitov. Dekoherencia je nezvratná, pretože je v skutočnosti nejednotná a zvyčajne je to niečo, čo by sa malo prísne kontrolovať, ak sa tomu ani vyhnúť. Časy dekoherencie najmä pre kandidátske systémy, čas priečnej relaxácie T2 (pre technológiu NMR a MRI, tiež nazývaný čas dephasingu), sa zvyčajne pohybuje medzi nanosekundami a sekundami pri nízkej teplote. V súčasnosti niektoré kvantové počítače vyžadujú, aby ich qubity boli ochladené na 20 milikelvinov (zvyčajne pomocou riediacej chladničky), aby sa zabránilo výraznej dekoherencii. Štúdia z roku 2020 tvrdí, že ionizujúce žiarenie, ako napríklad kozmické žiarenie, môže napriek tomu spôsobiť, že určité systémy sa v priebehu milisekúnd rozložia.
V dôsledku toho môžu časovo náročné úlohy spôsobiť nefunkčnosť niektorých kvantových algoritmov, pretože udržiavanie stavu qubitov počas dostatočne dlhého trvania nakoniec poškodí superpozície.
Tieto problémy sú zložitejšie pre optické prístupy, pretože časové rámce sú rádovo kratšie a často citovaným prístupom k ich prekonaniu je tvarovanie optických impulzov. Chybovosť je zvyčajne úmerná pomeru prevádzkového času k času dekoherencie, a preto musí byť každá operácia dokončená oveľa rýchlejšie ako čas dekoherencie.
Ako je opísané v kvantovej prahovej vete, ak je chybovosť dostatočne malá, predpokladá sa, že je možné použiť kvantovú korekciu chýb na potlačenie chýb a dekoherencie. To umožňuje, aby bol celkový čas výpočtu dlhší ako čas dekoherencie, ak schéma opravy chýb dokáže opraviť chyby rýchlejšie, ako ich dekoherencia zavedie. Často citovaný údaj pre požadovanú chybovosť v každom bráne pre výpočet odolný voči chybám je 10-3 za predpokladu, že šum je depolarizovaný.
Splnenie tejto podmienky škálovateľnosti je možné pre širokú škálu systémov. Použitie opravy chýb však so sebou prináša náklady na výrazne zvýšený počet požadovaných qubitov. Číslo potrebné na faktorenie celých čísel pomocou Shorovho algoritmu je stále polynóm a predpokladá sa, že je medzi L a L2, kde L je počet číslic v čísle, ktoré sa má rozdeliť; algoritmy na opravu chýb by zvýšili toto číslo o ďalší faktor L. Pre 1000-bitové číslo to znamená potrebu asi 104 bitov bez korekcie chýb. S opravou chýb by sa toto číslo zvýšilo na približne 107 bitov. Čas výpočtu je približne L2 alebo približne 107 krokov a pri 1 MHz približne 10 sekúnd.
Veľmi odlišným prístupom k problému dekoherencie stability je vytvorenie topologického kvantového počítača s ľubovoľnými, kvázi časticami používanými ako vlákna a spoliehaním sa na teóriu vrkoča na vytvorenie stabilných logických brán.
Kvantová nadradenosť
Kvantová nadradenosť je termín vytvorený Johnom Preskillom, ktorý odkazuje na inžiniersky čin demonštrovať, že programovateľné kvantové zariadenie môže vyriešiť problém, ktorý presahuje možnosti najmodernejších klasických počítačov. Problém nemusí byť užitočný, takže niektorí považujú test kvantovej nadradenosti len za potenciálne budúce kritérium.
V októbri 2019 sa spoločnosť Google AI Quantum s pomocou NASA stala prvou, ktorá tvrdila, že dosiahla kvantovú prevahu vykonávaním výpočtov na kvantovom počítači Sycamore viac ako 3,000,000 XNUMX XNUMX-krát rýchlejšie, než by sa dalo urobiť na Summite, ktorý je všeobecne považovaný za najrýchlejší na svete. počítač. Toto tvrdenie bolo následne spochybnené: IBM uviedla, že Summit dokáže vykonávať vzorky oveľa rýchlejšie, ako sa tvrdilo, a výskumníci odvtedy vyvinuli lepšie algoritmy pre problém vzorkovania, ktorý sa používa na tvrdenie o kvantovej nadradenosti, čím sa výrazne zmenšila alebo uzavrela medzera medzi Sycamore a Sycamore. klasické superpočítače.
V decembri 2020 skupina v USTC implementovala typ bozónového vzorkovania na 76 fotónoch pomocou fotonického kvantového počítača Jiuzhang, aby demonštrovala kvantovú prevahu. Autori tvrdia, že klasický súčasný superpočítač by potreboval výpočtový čas 600 miliónov rokov na vygenerovanie množstva vzoriek, ktoré ich kvantový procesor dokáže vygenerovať za 20 sekúnd. Dňa 16. novembra 2021 na summite o kvantovej výpočtovej technike IBM predstavila 127-qubitový mikroprocesor s názvom IBM Eagle.
Fyzické implementácie
Na fyzickú implementáciu kvantového počítača sa hľadá mnoho rôznych kandidátov, medzi nimi (odlíšených fyzickým systémom použitým na realizáciu qubitov):
- Supravodivé kvantové výpočty (qubit implementovaný stavom malých supravodivých obvodov, Josephsonove spojenia)
- Zachytený iónový kvantový počítač (qubit implementovaný vnútorným stavom zachytených iónov)
- Neutrálne atómy v optických mriežkach (qubit implementovaný vnútornými stavmi neutrálnych atómov zachytených v optickej mriežke)
- Quantum dot computer, spin-based (napr. Loss-DiVincenzo kvantový počítač) (qubit daný spinovými stavmi zachytených elektrónov)
- Počítač s kvantovou bodkou, priestorový (qubit daný polohou elektrónu v dvojitej kvantovej bodke)
- Kvantové výpočty využívajúce skonštruované kvantové studne, ktoré by v princípe mohli umožniť konštrukciu kvantových počítačov, ktoré pracujú pri izbovej teplote
- Spojený kvantový drôt (qubit implementovaný párom kvantových drôtov spojených kvantovým bodovým kontaktom)
- Kvantový počítač nukleárnej magnetickej rezonancie (NMRQC) implementovaný pomocou nukleárnej magnetickej rezonancie molekúl v roztoku, kde qubity sú poskytované jadrovými spinmi v rozpustenej molekule a sondované rádiovými vlnami
- Pevné NMR Kaneove kvantové počítače (qubit realizovaný stavom jadrového spinu donorov fosforu v kremíku)
- Kvantové počítače elektróny na héliu (qubit je elektrónový spin)
- Kvantová elektrodynamika dutín (CQED) (qubit poskytovaný vnútorným stavom zachytených atómov spojených s veľmi jemnými dutinami)
- Molekulový magnet (qubit daný stavmi rotácie)
- Kvantový počítač ESR založený na fulerénoch (qubit založený na elektronickom spine atómov alebo molekúl obalených vo fullerénoch)
- Nelineárny optický kvantový počítač (qubity realizované spracovaním stavov rôznych režimov svetla prostredníctvom lineárnych aj nelineárnych prvkov)
- Lineárny optický kvantový počítač (qubity realizované spracovaním stavov rôznych režimov svetla prostredníctvom lineárnych prvkov, napr. zrkadiel, rozdeľovačov lúčov a fázových posúvačov)
- Kvantový počítač na báze diamantu (qubit realizovaný elektronickým alebo nukleárnym spinom centier dusíka v diamante)
- Kvantový počítač založený na Bose-Einsteinovom kondenzáte
- Kvantový počítač na báze tranzistorov – strunové kvantové počítače so strhávaním kladných dier pomocou elektrostatickej pasce
- Kvantové počítače na báze anorganických kryštálov dopovaných kovmi vzácnych zemín (qubit realizovaný vnútorným elektronickým stavom dopantov v optických vláknach)
- Kvantové počítače na báze uhlíkových nanoguľôčok podobných kovu
- Veľký počet kandidátov ukazuje, že kvantová výpočtová technika je napriek rýchlemu pokroku stále v plienkach.
Existuje množstvo kvantových výpočtových modelov, ktoré sa vyznačujú základnými prvkami, v ktorých je výpočet rozložený. Pre praktické implementácie sú štyri relevantné modely výpočtu:
- Kvantové hradlové pole (výpočet rozložený na sekvenciu niekoľkých qubitových kvantových brán)
- Jednosmerný kvantový počítač (výpočet rozložený na sekvenciu jedno-qubitových meraní aplikovaných na vysoko zapletený počiatočný stav alebo stav klastra)
- Adiabatický kvantový počítač, založený na kvantovom žíhaní (výpočet rozložený na pomalú kontinuálnu transformáciu počiatočného hamiltoniánu na konečný hamiltonián, ktorého základné stavy obsahujú riešenie)
- Topologický kvantový počítač (výpočet rozložený na opletenie anyonov v 2D mriežke)
Kvantový Turingov stroj je teoreticky dôležitý, ale fyzická implementácia tohto modelu nie je uskutočniteľná. Všetky štyri modely výpočtu sa ukázali ako ekvivalentné; každý môže simulovať ten druhý s nie viac ako polynómovou réžiou.
Aby ste sa podrobne oboznámili s certifikačným učebným plánom, môžete rozšíriť a analyzovať tabuľku nižšie.
Certifikačný učebný plán EITC/QI/QIF Quantum Information Fundamentals Certification Curriculum odkazuje na didaktické materiály s otvoreným prístupom vo forme videa. Učebný proces je rozdelený na štruktúru krok za krokom (programy -> lekcie -> témy), ktorá pokrýva príslušné časti kurikula. Poskytuje sa aj neobmedzené poradenstvo s odborníkmi na domény.
Podrobnosti o kontrole postupu certifikácie Ako funguje CBD Factum Pet Solution?.
Poznámky k hlavnej prednáške
Poznámky k prednáške U. Vazirani:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Podporné poznámky z prednášok
L. Jačák a kol. poznámky z prednášok (s doplnkovými materiálmi):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Hlavná podporná učebnica
Učebnica Quantum Computation & Quantum Information (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Doplňujúce poznámky k prednáške
Poznámky k prednáške J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
Poznámky k prednáške A. Childsa:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Poznámky k prednáške S. Aaronsona:
https://scottaaronson.blog/?p=3943
Poznámky k prednáške R. de Wolfa:
https://arxiv.org/abs/1907.09415
Ďalšie odporúčané učebnice
Klasické a kvantové výpočty (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Kvantové výpočty od čias Demokrita (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Teória kvantovej informácie (vodnatá)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Kvantová teória informácie (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Stiahnite si kompletné offline samovzdelávacie prípravné materiály pre program EITC/QI/QIF Quantum Information Fundamentals v súbore PDF
Prípravné materiály EITC/QI/QIF – štandardná verzia
Prípravné materiály EITC/QI/QIF – rozšírená verzia o recenzné otázky