EITC/QI/QIF Quantum Information Fundamentals je evropský certifikační program IT zaměřený na teoretické a praktické aspekty kvantových informací a kvantových výpočtů, založený na zákonech kvantové fyziky spíše než na klasické fyzice a nabízející kvalitativní výhody oproti jejich klasickým protějškům.
Učební plán EITC/QI/QIF Quantum Information Fundamentals zahrnuje úvod do kvantové mechaniky (včetně zvážení experimentu s dvojitou štěrbinou a interference vln hmoty), úvod do kvantové informace (qubity a jejich geometrické znázornění), polarizaci světla, princip neurčitosti, kvantové zapletení, EPR paradox, porušení Bellovy nerovnosti, opuštění místního realismu, kvantové zpracování informací (včetně unitární transformace, jedno-qubitových a dvouqubitových hradel), neklonovací teorém, kvantová teleportace, kvantové měření, kvantové výpočty (včetně úvodu do multi -qubitové systémy, univerzální rodina hradel, reverzibilita výpočtu), kvantové algoritmy (včetně Quantum Fourier Transform, Simonův algoritmus, rozšířená Churhova-Turingova teze, Shor'qův kvantový faktoringový algoritmus, Groverův kvantový vyhledávací algoritmus), kvantové pozorovatelné veličiny, Shrodingerova rovnice qubitové implementace, kvantová teorie složitosti, adiabatický kvantový výpočet ion, BQP, úvod do spinu, v rámci následující struktury, zahrnující komplexní videodidaktický obsah jako reference pro tuto certifikaci EITC.
Kvantová informace je informace o stavu kvantového systému. Je to základní entita studia v kvantové teorii informace a lze s ním manipulovat pomocí technik kvantového zpracování informací. Kvantová informace se vztahuje jak na technickou definici z hlediska Von Neumannovy entropie, tak na obecný výpočetní termín.
Kvantová informace a výpočty je interdisciplinární obor, který zahrnuje mimo jiné kvantovou mechaniku, informatiku, teorii informace, filozofii a kryptografii. Jeho studium je také relevantní pro obory, jako jsou kognitivní vědy, psychologie a neurovědy. Jeho hlavním zaměřením je získávání informací z hmoty v mikroskopickém měřítku. Pozorování ve vědě je základním osobitým kritériem reality a jedním z nejdůležitějších způsobů získávání informací. Pro kvantifikaci pozorování je tedy nutné měření, což je pro vědeckou metodu zásadní. V kvantové mechanice, kvůli principu neurčitosti, non-commuting observables nemohou být přesně měřeny současně, jako eigenstate v jednom základu není eigenstate v jiný základ. Protože obě proměnné nejsou současně dobře definovány, kvantový stav nemůže nikdy obsahovat definitivní informace o obou proměnných. Vzhledem k této základní vlastnosti měření v kvantové mechanice lze tuto teorii obecně charakterizovat jako nedeterministickou na rozdíl od klasické mechaniky, která je plně deterministická. Indeterminismus kvantových stavů charakterizuje informace definované jako stavy kvantových systémů. Z matematického hlediska jsou tyto stavy v superpozicích (lineárních kombinacích) stavů klasických systémů.
Protože je informace vždy zakódována ve stavu fyzického systému, je fyzická sama o sobě. Zatímco kvantová mechanika se zabývá zkoumáním vlastností hmoty na mikroskopické úrovni, kvantová informační věda se zaměřuje na získávání informací z těchto vlastností a kvantové výpočty manipulují a zpracovávají kvantové informace – provádějí logické operace – pomocí technik kvantového zpracování informací.
Kvantové informace, stejně jako klasické informace, lze zpracovávat pomocí počítačů, přenášet z jednoho místa na druhé, manipulovat s nimi pomocí algoritmů a analyzovat pomocí informatiky a matematiky. Stejně jako základní jednotkou klasické informace je bit, kvantová informace se zabývá qubity, které mohou existovat v superpozici 0 a 1 (současně jsou poněkud pravdivé a nepravdivé). Kvantová informace může také existovat v tzv. provázaných stavech, které ve svých měřeních projevují čistě neklasické nelokální korelace, což umožňuje aplikace, jako je kvantová teleportace. Úroveň zapletení lze měřit pomocí Von Neumannovy entropie, která je také měřítkem kvantové informace. V poslední době se oblast kvantových počítačů stala velmi aktivní oblastí výzkumu kvůli možnosti narušit moderní výpočty, komunikaci a kryptografii.
Historie kvantové informace začala na přelomu 20. století, kdy došlo k převratu klasické fyziky do kvantové fyziky. Teorie klasické fyziky předpovídaly absurdity, jako je ultrafialová katastrofa nebo elektrony ve spirále do jádra. Nejprve byly tyto problémy smeteny stranou přidáním ad hoc hypotézy ke klasické fyzice. Brzy se ukázalo, že musí být vytvořena nová teorie, aby tyto absurdity daly smysl, a zrodila se teorie kvantové mechaniky.
Kvantová mechanika byla formulována Schrödingerem pomocí vlnové mechaniky a Heisenbergem pomocí maticové mechaniky. Ekvivalence těchto metod byla prokázána později. Jejich formulace popisovaly dynamiku mikroskopických systémů, ale měly několik neuspokojivých aspektů při popisu procesů měření. Von Neumann formuloval kvantovou teorii pomocí operátorové algebry způsobem, který popisoval měření i dynamiku. Tyto studie zdůrazňovaly spíše filozofické aspekty měření než kvantitativní přístup k získávání informací prostřednictvím měření.
V 1960. letech Stratonovich, Helstrom a Gordon navrhli formulaci optické komunikace pomocí kvantové mechaniky. Toto byl první historický výskyt kvantové teorie informace. Studovali především pravděpodobnosti chyb a komunikační kapacity kanálů. Později Holevo získalo horní hranici komunikační rychlosti při přenosu klasické zprávy přes kvantový kanál.
V 1970. letech XNUMX. století se začaly vyvíjet techniky manipulace s kvantovými stavy jednoho atomu, jako je atomová past a skenovací tunelový mikroskop, které umožňují izolovat jednotlivé atomy a uspořádat je do polí. Před tímto vývojem nebyla přesná kontrola nad jednotlivými kvantovými systémy možná a experimenty využívaly hrubší, současnou kontrolu nad velkým počtem kvantových systémů. Vývoj životaschopných jednostavových manipulačních technik vedl ke zvýšenému zájmu o oblast kvantových informací a počítání.
V 1980. letech se objevil zájem o to, zda by bylo možné použít kvantové efekty k vyvrácení Einsteinovy teorie relativity. Pokud by bylo možné naklonovat neznámý kvantový stav, bylo by možné použít propletené kvantové stavy k přenosu informace rychleji než je rychlost světla, což vyvrací Einsteinovu teorii. Avšak teorém o neklonování ukázal, že takové klonování je nemožné. Věta byla jedním z prvních výsledků kvantové teorie informace.
Vývoj z kryptografie
Přes veškeré vzrušení a zájem o studium izolovaných kvantových systémů a snahu najít způsob, jak obejít teorii relativity, výzkum kvantové teorie informace v 1980. letech ustrnul. Zhruba ve stejnou dobu se však do kvantových informací a výpočtů začala pouštět jiná cesta: kryptografie. V obecném smyslu je kryptografie problémem provádění komunikace nebo výpočtů zahrnujících dvě nebo více stran, které si navzájem nedůvěřují.
Bennett a Brassard vyvinuli komunikační kanál, na kterém je nemožné odposlouchávat, aniž by byl detekován, způsob tajné komunikace na velké vzdálenosti pomocí kvantového kryptografického protokolu BB84. Klíčovou myšlenkou bylo použití základního principu kvantové mechaniky, že pozorování ruší pozorované, a zavedení odposlechu do zabezpečené komunikační linky okamžitě umožní dvěma stranám, které se snaží komunikovat, vědět o přítomnosti odposlechu.
Vývoj z informatiky a matematiky
S příchodem revolučních myšlenek Alana Turinga o programovatelném počítači nebo Turingově stroji ukázal, že jakýkoli výpočet v reálném světě lze převést na ekvivalentní výpočet zahrnující Turingův stroj. Toto je známé jako Church-Turingova teze.
Brzy byly vyrobeny první počítače a počítačový hardware rostl tak rychlým tempem, že tento růst byl díky zkušenostem s výrobou kodifikován do empirického vztahu zvaného Moorův zákon. Tento „zákon“ je projektivní trend, který říká, že počet tranzistorů v integrovaném obvodu se každé dva roky zdvojnásobí. Jak se tranzistory začaly zmenšovat a zmenšovat, aby naplnily více energie na plochu, začaly se v elektronice objevovat kvantové efekty, což mělo za následek neúmyslné rušení. To vedlo k nástupu kvantových počítačů, které využívaly kvantovou mechaniku k navrhování algoritmů.
V tomto bodě kvantové počítače slibovaly, že budou mnohem rychlejší než klasické počítače pro určité specifické problémy. Jeden takový příklad problému vyvinuli David Deutsch a Richard Jozsa, známý jako Deutsch–Jozsův algoritmus. Tento problém se však prakticky nevyužívá až vůbec. Peter Shor v roce 1994 přišel s velmi důležitým a praktickým problémem, jedním z hledání prvočísel celého čísla. Problém diskrétního logaritmu, jak byl nazýván, mohl být efektivně vyřešen na kvantovém počítači, ale ne na klasickém počítači, což ukazuje, že kvantové počítače jsou výkonnější než Turingovy stroje.
Vývoj z teorie informace
Přibližně v době, kdy počítačová věda prováděla revoluci, stejně jako teorie informací a komunikace prostřednictvím Clauda Shannona. Shannon vyvinul dva základní teorémy teorie informace: teorém o kódování bezhlučného kanálu a teorém o kódování šumového kanálu. Ukázal také, že k ochraně odesílaných informací lze použít kódy pro opravu chyb.
Kvantová teorie informace také sledovala podobnou trajektorii, Ben Schumacher v roce 1995 vytvořil analogii k Shannonově větě o nehlučném kódování pomocí qubit. Také se vyvinula teorie opravy chyb, která umožňuje kvantovým počítačům provádět efektivní výpočty bez ohledu na šum a provádět spolehlivou komunikaci přes hlučné kvantové kanály.
Qubity a teorie informace
Kvantová informace se výrazně liší od klasické informace, ztělesněné bitem, mnoha pozoruhodnými a neznámými způsoby. Zatímco základní jednotkou klasické informace je bit, nejzákladnější jednotkou kvantové informace je qubit. Klasická informace se měří pomocí Shannonovy entropie, zatímco kvantově mechanickou analogií je Von Neumannova entropie. Statistický soubor kvantově mechanických systémů je charakterizován maticí hustoty. Mnoho měření entropie v klasické teorii informace lze také zobecnit na kvantový případ, jako je Holevova entropie a podmíněná kvantová entropie.
Na rozdíl od klasických digitálních stavů (které jsou diskrétní) má qubit spojitou hodnotu, kterou lze popsat směrem na Blochově sféře. Navzdory tomu, že je qubit takto průběžně ohodnocován, je nejmenší možnou jednotkou kvantové informace, a přestože je stav qubitu kontinuálně ohodnocen, není možné hodnotu přesně změřit. Pět slavných teorémů popisuje limity manipulace s kvantovou informací:
- teorém o neteleportaci, který říká, že qubit nelze (zcela) převést na klasické bity; to znamená, že jej nelze plně „číst“,
- neklonovací teorém, který zabraňuje zkopírování libovolného qubitu,
- no-deleting teorém, který zabraňuje smazání libovolného qubitu,
- teorém o zákazu vysílání, který zabraňuje doručení libovolného qubitu více příjemcům, i když jej lze přenést z místa na místo (např. pomocí kvantové teleportace),
- no-hiding teorém, který demonstruje zachování kvantové informace.Tyto teorémy dokazují, že kvantová informace ve vesmíru je zachována a otevírají jedinečné možnosti v kvantovém zpracování informace.
Kvantové zpracování informací
Stav qubitu obsahuje všechny jeho informace. Tento stav je často vyjádřen jako vektor na Blochově sféře. Tento stav lze změnit aplikací lineárních transformací nebo kvantových hradel. Tyto unitární transformace jsou popsány jako rotace na Blochově sféře. Zatímco klasická hradla odpovídají známým operacím booleovské logiky, kvantová hradla jsou fyzické jednotné operátory.
Kvůli volatilitě kvantových systémů a nemožnosti kopírování stavů je ukládání kvantové informace mnohem obtížnější než ukládání klasických informací. Nicméně s použitím kvantové korekce chyb lze kvantovou informaci v principu stále spolehlivě uložit. Existence kódů pro opravu kvantových chyb také vedla k možnosti kvantového výpočtu odolného vůči chybám.
Klasické bity lze zakódovat a následně získat z konfigurací qubitů pomocí kvantových hradel. Jediný qubit sám o sobě může zprostředkovat maximálně jeden bit dostupné klasické informace o jeho přípravě. Toto je Holevova věta. V superhustém kódování však může odesílatel tím, že působí na jeden ze dvou zapletených qubitů, předat dva bity přístupných informací o jejich společném stavu do přijímače.
Kvantová informace se může pohybovat v kvantovém kanálu, analogicky ke konceptu klasického komunikačního kanálu. Kvantové zprávy mají konečnou velikost, měřenou v qubitech; kvantové kanály mají konečnou kapacitu kanálu, měřenou v qubitech za sekundu.
Kvantová informace a změny v kvantové informaci mohou být kvantitativně měřeny pomocí analogu Shannonovy entropie, nazývané von Neumannova entropie.
V některých případech mohou být kvantové algoritmy použity k provádění výpočtů rychleji než v jakémkoli známém klasickém algoritmu. Nejznámějším příkladem je Shorův algoritmus, který dokáže faktorizovat čísla v polynomiálním čase, ve srovnání s nejlepšími klasickými algoritmy, které využívají sub-exponenciální čas. Protože faktorizace je důležitou součástí bezpečnosti šifrování RSA, Shorův algoritmus podnítil novou oblast postkvantové kryptografie, která se snaží najít šifrovací schémata, která zůstanou bezpečná, i když jsou ve hře kvantové počítače. Mezi další příklady algoritmů, které demonstrují kvantovou nadřazenost, patří Groverův vyhledávací algoritmus, kde kvantový algoritmus poskytuje kvadratické zrychlení oproti nejlepšímu možnému klasickému algoritmu. Třída složitosti problémů efektivně řešitelných kvantovým počítačem je známá jako BQP.
Quantum key distribution (QKD) umožňuje bezpodmínečně bezpečný přenos klasických informací, na rozdíl od klasického šifrování, které lze v principu vždy prolomit, ne-li v praxi. Všimněte si, že některé jemné body týkající se bezpečnosti QKD jsou stále žhavě diskutovány.
Studium všech výše uvedených témat a rozdílů zahrnuje kvantovou teorii informace.
Vztah ke kvantové mechanice
Kvantová mechanika je studium toho, jak se mikroskopické fyzikální systémy v přírodě dynamicky mění. V oblasti kvantové teorie informace jsou studované kvantové systémy abstrahovány od jakéhokoli protějšku v reálném světě. Qubit může být například fyzicky foton v lineárním optickém kvantovém počítači, iont v zachyceném iontovém kvantovém počítači nebo to může být velká sbírka atomů jako v supravodivém kvantovém počítači. Bez ohledu na fyzickou implementaci platí limity a rysy qubitů implikované kvantovou teorií informace, protože všechny tyto systémy jsou matematicky popsány stejným aparátem matic hustoty přes komplexní čísla. Dalším důležitým rozdílem od kvantové mechaniky je to, že zatímco kvantová mechanika často studuje nekonečněrozměrné systémy, jako je harmonický oscilátor, kvantová teorie informace se zabývá jak systémy spojitých proměnných, tak systémy konečných rozměrů.
Kvantový výpočet
Kvantové počítání je typ výpočtu, který využívá k provádění výpočtů kolektivní vlastnosti kvantových stavů, jako je superpozice, interference a zapletení. Zařízení, která provádějí kvantové výpočty, jsou známá jako kvantové počítače.: I-5 Přestože jsou současné kvantové počítače příliš malé na to, aby překonaly běžné (klasické) počítače pro praktické aplikace, má se za to, že jsou schopné řešit určité výpočetní problémy, jako je faktorizace na celé číslo. (který je základem šifrování RSA), podstatně rychlejší než klasické počítače. Studium kvantových počítačů je podoborem kvantové informační vědy.
Kvantové výpočty začaly v roce 1980, kdy fyzik Paul Benioff navrhl kvantově mechanický model Turingova stroje. Richard Feynman a Yuri Manin později navrhli, že kvantový počítač má potenciál simulovat věci, které klasický počítač nemůže uskutečnit. V roce 1994 Peter Shor vyvinul kvantový algoritmus pro faktorizaci celých čísel s potenciálem dešifrovat komunikaci šifrovanou RSA. V roce 1998 Isaac Chuang, Neil Gershenfeld a Mark Kubinec vytvořili první dvouqubitový kvantový počítač, který mohl provádět výpočty. Navzdory pokračujícímu experimentálnímu pokroku od konce 1990. let 23. století většina výzkumníků věří, že „kvantové výpočty odolné vůči chybám jsou stále spíše vzdáleným snem“. V posledních letech vzrostly investice do kvantového výpočetního výzkumu ve veřejném i soukromém sektoru. Dne 2019. října XNUMX společnost Google AI ve spolupráci s americkým Národním úřadem pro letectví a vesmír (NASA) tvrdila, že provedla kvantový výpočet, který nebyl proveditelný na žádném klasickém počítači, ale zda toto tvrzení bylo nebo stále platí, je tématem aktivní výzkum.
Existuje několik typů kvantových počítačů (také známých jako kvantové výpočetní systémy), včetně modelu kvantového obvodu, kvantového Turingova stroje, adiabatického kvantového počítače, jednosměrného kvantového počítače a různých kvantových buněčných automatů. Nejrozšířenějším modelem je kvantový obvod, založený na kvantovém bitu, neboli „qubit“, který je poněkud analogický bitu v klasickém počítání. Qubit může být v kvantovém stavu 1 nebo 0 nebo v superpozici stavů 1 a 0. Když se však měří, je vždy 0 nebo 1; pravděpodobnost jednoho výsledku závisí na kvantovém stavu qubit bezprostředně před měřením.
Úsilí o vybudování fyzického kvantového počítače se zaměřuje na technologie, jako jsou transmony, iontové pasti a topologické kvantové počítače, jejichž cílem je vytvářet vysoce kvalitní qubity.: 2–13 Tyto qubity mohou být navrženy odlišně v závislosti na výpočetním modelu úplného kvantového počítače, zda kvantová logická hradla, kvantové žíhání nebo adiabatické kvantové výpočty. V současné době existuje řada významných překážek pro konstrukci užitečných kvantových počítačů. Je obzvláště obtížné udržovat kvantové stavy qubitů, protože trpí kvantovou dekoherencí a stavovou věrností. Kvantové počítače proto vyžadují opravu chyb.
Jakýkoli výpočetní problém, který lze vyřešit klasickým počítačem, může být vyřešen i kvantovým počítačem. A naopak, jakýkoli problém, který lze vyřešit kvantovým počítačem, může být vyřešen i počítačem klasickým, alespoň v zásadě s dostatkem času. Jinými slovy, kvantové počítače se řídí Church-Turingovou tezí. To znamená, že zatímco kvantové počítače neposkytují žádné další výhody oproti klasickým počítačům z hlediska vyčíslitelnosti, kvantové algoritmy pro určité problémy mají výrazně nižší časovou složitost než odpovídající známé klasické algoritmy. Je pozoruhodné, že se věří, že kvantové počítače jsou schopny rychle vyřešit určité problémy, které žádný klasický počítač nevyřeší v žádném možném čase – výkon známý jako „kvantová nadřazenost“. Studium výpočetní složitosti problémů s ohledem na kvantové počítače je známé jako teorie kvantové složitosti.
Převládající model kvantového výpočtu popisuje výpočet v podmínkách sítě kvantových logických hradel. Tento model lze považovat za abstraktní lineárně-algebraické zobecnění klasického obvodu. Protože se tento model obvodu řídí kvantovou mechanikou, kvantový počítač schopný efektivně provozovat tyto obvody se považuje za fyzicky realizovatelný.
Paměť skládající se z n bitů informace má 2^n možných stavů. Vektor reprezentující všechny stavy paměti má tedy 2^n záznamů (jeden pro každý stav). Tento vektor je chápán jako pravděpodobnostní vektor a představuje skutečnost, že paměť se nachází v určitém stavu.
V klasickém zobrazení by jeden záznam měl hodnotu 1 (tj. 100% pravděpodobnost, že bude v tomto stavu) a všechny ostatní záznamy by byly nulové.
V kvantové mechanice lze vektory pravděpodobnosti zobecnit na operátory hustoty. Kvantový stavový vektorový formalismus je obvykle představen jako první, protože je koncepčně jednodušší a protože jej lze použít místo formalismu matice hustoty pro čisté stavy, kde je znám celý kvantový systém.
kvantový výpočet lze popsat jako síť kvantových logických hradel a měření. Jakékoli měření však může být odloženo na konec kvantového výpočtu, i když toto odložení může přijít s výpočetními náklady, takže většina kvantových obvodů zobrazuje síť sestávající pouze z kvantových logických hradel a bez měření.
Jakýkoli kvantový výpočet (což je ve výše uvedeném formalismu jakákoliv unitární matice přes n qubitů) může být reprezentován jako síť kvantových logických hradel z poměrně malé rodiny hradel. Volba rodiny hradel, která umožňuje tuto konstrukci, je známá jako univerzální sada hradel, protože počítač, který může provozovat takové obvody, je univerzální kvantový počítač. Jedna společná taková sada obsahuje všechna jedno-qubitová hradla a také hradlo CNOT shora. To znamená, že jakýkoli kvantový výpočet lze provést provedením sekvence jedno-qubitových hradel spolu s hradly CNOT. Ačkoli je tato množina bran nekonečná, lze ji nahradit množinou konečných bran pomocí Solovay-Kitaevova teorému.
Kvantové algoritmy
Pokrok v hledání kvantových algoritmů se obvykle zaměřuje na tento model kvantového obvodu, ačkoli existují výjimky, jako je kvantový adiabatický algoritmus. Kvantové algoritmy lze zhruba kategorizovat podle typu zrychlení dosaženého oproti odpovídajícím klasickým algoritmům.
Kvantové algoritmy, které nabízejí více než jen polynomiální zrychlení oproti nejznámějšímu klasickému algoritmu, zahrnují Shorův algoritmus pro faktoring a související kvantové algoritmy pro výpočet diskrétních logaritmů, řešení Pellovy rovnice a obecněji řešení skrytého problému podgrupy pro abelovské konečné grupy. Tyto algoritmy závisí na primitivu kvantové Fourierovy transformace. Nebyl nalezen žádný matematický důkaz, který by ukázal, že stejně rychlý klasický algoritmus nelze objevit, ačkoli se to považuje za nepravděpodobné.[vlastně publikovaný zdroj?] Určité věštecké problémy, jako je Simonův problém a Bernstein-Vaziraniho problém, poskytují prokazatelné zrychlení, i když toto je v modelu kvantového dotazu, což je omezený model, kde je mnohem snazší dokázat spodní hranice a nemusí se nutně překládat jako zrychlení praktických problémů.
Jiné problémy, včetně simulace kvantových fyzikálních procesů z chemie a fyziky pevných látek, aproximace určitých Jonesových polynomů a kvantový algoritmus pro lineární systémy rovnic, mají kvantové algoritmy, které se zdají být super-polynomiálními zrychleními a jsou BQP-úplné. Protože tyto problémy jsou BQP-úplné, stejně rychlý klasický algoritmus pro ně by znamenal, že žádný kvantový algoritmus neposkytuje super-polynomiální zrychlení, což je považováno za nepravděpodobné.
Některé kvantové algoritmy, jako je Groverův algoritmus a zesílení amplitudy, poskytují polynomiální zrychlení oproti odpovídajícím klasickým algoritmům. Ačkoli tyto algoritmy poskytují srovnatelně mírné kvadratické zrychlení, jsou široce použitelné, a proto poskytují zrychlení pro širokou škálu problémů. Mnoho příkladů prokazatelných kvantových zrychlení pro problémy s dotazy souvisí s Groverovým algoritmem, včetně Brassardova, Høyerova a Tappova algoritmu pro hledání kolizí ve funkcích dva ku jedné, který používá Groverův algoritmus, a Farhiho, Goldstoneova a Gutmannova algoritmu pro vyhodnocování NAND stromy, což je varianta vyhledávacího problému.
Kryptografické aplikace
Pozoruhodná aplikace kvantového počítání je pro útoky na kryptografické systémy, které se v současnosti používají. Faktorizace celých čísel, která podporuje bezpečnost kryptografických systémů s veřejným klíčem, se považuje za výpočetně neproveditelná s běžným počítačem pro velká celá čísla, pokud jsou součinem několika prvočísel (např. součin dvou 300místných prvočísel). Pro srovnání, kvantový počítač by mohl efektivně vyřešit tento problém pomocí Shorova algoritmu k nalezení jeho faktorů. Tato schopnost by kvantovému počítači umožnila rozbít mnoho dnes používaných kryptografických systémů v tom smyslu, že by existoval polynomiální časový (v počtu číslic celého čísla) algoritmus pro vyřešení problému. Zejména většina populárních šifer s veřejným klíčem je založena na obtížnosti faktorizace celých čísel nebo problému diskrétního logaritmu, přičemž obojí lze vyřešit Shorovým algoritmem. Zejména by mohly být porušeny algoritmy RSA, Diffie–Hellman a eliptická křivka Diffie–Hellman. Používají se k ochraně zabezpečených webových stránek, šifrovaných e-mailů a mnoha dalších typů dat. Jejich porušení by mělo významné důsledky pro elektronické soukromí a bezpečnost.
Identifikace kryptografických systémů, které mohou být zabezpečené proti kvantovým algoritmům, je aktivně zkoumaným tématem v oblasti postkvantové kryptografie. Některé algoritmy veřejného klíče jsou založeny na problémech jiných než celočíselná faktorizace a problémy s diskrétním logaritmem, na které se vztahuje Shorův algoritmus, jako je McElieceův kryptosystém založený na problému v teorii kódování. Také není známo, že by kvantové počítače dokázaly rozbít kryptosystémy založené na mřížkách, a nalezení polynomiálního časového algoritmu pro řešení problému dihedrální skryté podskupiny, který by rozbil mnoho kryptosystémů založených na mřížce, je dobře prostudovaný otevřený problém. Bylo prokázáno, že použití Groverova algoritmu k prolomení symetrického (tajného klíče) algoritmu hrubou silou vyžaduje čas rovnající se zhruba 2n/2 vyvolání základního kryptografického algoritmu ve srovnání se zhruba 2n v klasickém případě, což znamená, že délky symetrických klíčů jsou efektivně poloviční: AES-256 by měl stejné zabezpečení proti útoku pomocí Groverova algoritmu jako AES-128 proti klasickému vyhledávání hrubou silou (viz Velikost klíče).
Kvantová kryptografie by mohla potenciálně plnit některé funkce kryptografie s veřejným klíčem. Kvantové kryptografické systémy by proto mohly být bezpečnější než tradiční systémy proti kvantovému hackování.
Problémy s vyhledáváním
Nejznámějším příkladem problému připouštějícího polynomiální kvantové zrychlení je nestrukturované vyhledávání, hledání označené položky ze seznamu n položek v databázi. To lze vyřešit Groverovým algoritmem pomocí O(sqrt(n)) dotazů do databáze, což je kvadraticky méně než Omega(n) dotazy vyžadované pro klasické algoritmy. V tomto případě je výhoda nejen prokazatelná, ale také optimální: ukázalo se, že Groverův algoritmus poskytuje maximální možnou pravděpodobnost nalezení požadovaného prvku pro libovolný počet věšteckých vyhledávání.
Problémy, které lze řešit pomocí Groverova algoritmu, mají následující vlastnosti:
- Ve sbírce možných odpovědí neexistuje žádná prohledávatelná struktura,
- Počet možných odpovědí ke kontrole je stejný jako počet vstupů do algoritmu a
- Existuje booleovská funkce, která vyhodnotí každý vstup a určí, zda je to správná odpověď
Pro problémy se všemi těmito vlastnostmi je doba běhu Groverova algoritmu na kvantovém počítači škálována jako druhá odmocnina z počtu vstupů (nebo prvků v databázi), na rozdíl od lineárního škálování klasických algoritmů. Obecnou třídou problémů, na které lze Groverův algoritmus použít, je Booleovský problém splnitelnosti, kde databáze, kterou algoritmus iteruje, je databáze všech možných odpovědí. Příkladem a (možnou) aplikací toho je cracker hesel, který se pokouší uhodnout heslo. Symetrické šifry jako Triple DES a AES jsou obzvláště zranitelné vůči tomuto druhu útoku. [pochvalná zmínka potřebovaný] Tato aplikace kvantového počítání je hlavním zájmem vládních agentur.
Simulace kvantových systémů
Vzhledem k tomu, že chemie a nanotechnologie spoléhají na pochopení kvantových systémů a takové systémy není možné klasicky efektivně simulovat, mnozí věří, že kvantová simulace bude jednou z nejdůležitějších aplikací kvantového počítání. Kvantová simulace by mohla být také použita k simulaci chování atomů a částic za neobvyklých podmínek, jako jsou reakce uvnitř urychlovače. Kvantové simulace by mohly být použity k předpovědi budoucích drah částic a protonů pod superpozicí v experimentu s dvojitou štěrbinou.[pochvalná zmínka potřebovaný] Asi 2 % ročního globálního energetického výkonu se spotřebuje na fixaci dusíku k výrobě čpavku pro Haberův proces v zemědělství. průmysl hnojiv, zatímco přirozeně se vyskytující organismy také produkují amoniak. K pochopení tohoto procesu zvyšujícího produkci lze použít kvantové simulace.
Kvantové žíhání a adiabatická optimalizace
Kvantové žíhání nebo adiabatické kvantové výpočty se při provádění výpočtů spoléhají na adiabatický teorém. Systém je umístěn do základního stavu pro jednoduchý hamiltonián, který se pomalu vyvíjí na komplikovanější hamiltonián, jehož základní stav představuje řešení daného problému. Adiabatický teorém říká, že pokud je evoluce dostatečně pomalá, systém zůstane ve svém základním stavu po celou dobu procesu.
Strojové učení
Protože kvantové počítače mohou produkovat výstupy, které klasické počítače nedokážou efektivně produkovat, a protože kvantové počítání je v zásadě lineární algebraické, někteří vyjadřují naději na vývoj kvantových algoritmů, které mohou urychlit úlohy strojového učení. Například se předpokládá, že kvantový algoritmus pro lineární soustavy rovnic neboli „HHL Algorithm“, pojmenovaný po svých objevitelích Harrowovi, Hassidimovi a Lloydovi, poskytuje zrychlení oproti klasickým protějškům. Některé výzkumné skupiny nedávno prozkoumaly použití hardwaru pro kvantové žíhání pro trénink Boltzmannových strojů a hlubokých neuronových sítí.
Výpočetní biologie
V oblasti výpočetní biologie sehrály kvantové výpočty velkou roli při řešení mnoha biologických problémů. Jedním z dobře známých příkladů by byla výpočetní genomika a to, jak výpočetní technika drasticky zkrátila čas na sekvenování lidského genomu. Vzhledem k tomu, jak výpočetní biologie využívá generické datové modelování a ukládání, očekává se, že se objeví i její aplikace ve výpočetní biologii.
Počítačem podporovaný návrh léčiv a generativní chemie
Hluboké modely generativní chemie se objevují jako mocné nástroje k urychlení objevu léků. Nesmírná velikost a složitost strukturního prostoru všech možných molekul podobných lékům však staví značné překážky, které by v budoucnu mohly překonat kvantové počítače. Kvantové počítače jsou přirozeně dobré pro řešení složitých kvantových mnohotělesných problémů, a proto mohou být nápomocné v aplikacích zahrnujících kvantovou chemii. Proto lze očekávat, že kvantově vylepšené generativní modely včetně kvantových GAN mohou být nakonec vyvinuty do konečných algoritmů generativní chemie. Hybridní architektury kombinující kvantové počítače s hlubokými klasickými sítěmi, jako jsou Quantum Variational Autoencoders, již lze trénovat na komerčně dostupných žíhacích zařízeních a použít je k vytváření nových molekulárních struktur podobných lékům.
Vývoj fyzikálních kvantových počítačů
Výzvy
Při budování rozsáhlého kvantového počítače existuje řada technických problémů. Fyzik David DiVincenzo uvedl tyto požadavky na praktický kvantový počítač:
- Fyzicky škálovatelné pro zvýšení počtu qubitů,
- Qubity, které lze inicializovat na libovolné hodnoty,
- Kvantové brány, které jsou rychlejší než dekoherenční čas,
- Univerzální sada brány,
- Qubits, které lze snadno číst.
Sourcing dílů pro kvantové počítače je také velmi obtížné. Mnoho kvantových počítačů, jako jsou ty zkonstruované Googlem a IBM, potřebuje helium-3, vedlejší produkt jaderného výzkumu, a speciální supravodivé kabely vyrobené pouze japonskou společností Coax Co.
Řízení multi-qubitových systémů vyžaduje generování a koordinaci velkého množství elektrických signálů s pevným a deterministickým časovým rozlišením. To vedlo k vývoji kvantových regulátorů, které umožňují propojení s qubity. Škálování těchto systémů na podporu rostoucího počtu qubitů je další výzvou.
Kvantová dekoherence
Jednou z největších výzev spojených s konstrukcí kvantových počítačů je kontrola nebo odstranění kvantové dekoherence. To obvykle znamená izolovat systém od jeho prostředí, protože interakce s vnějším světem způsobují dekoherenci systému. Existují však i jiné zdroje dekoherence. Příklady zahrnují kvantová hradla a vibrace mřížky a termonukleární spin na pozadí fyzického systému používaného k implementaci qubitů. Dekoherence je nevratná, protože je fakticky nejednotná a obvykle je to něco, co by mělo být přísně kontrolováno, ne-li se mu vyhýbat. Zejména doby dekoherence pro kandidátské systémy, čas příčné relaxace T2 (pro technologii NMR a MRI, také nazývaný čas dephasing), se typicky pohybuje mezi nanosekundami a sekundami při nízké teplotě. V současné době některé kvantové počítače vyžadují, aby jejich qubity byly ochlazeny na 20 milikelvinů (obvykle pomocí zřeďovací chladničky), aby se zabránilo výrazné dekoherenci. Studie z roku 2020 tvrdí, že ionizující záření, jako je kosmické záření, může přesto způsobit dekoherenci určitých systémů během milisekund.
V důsledku toho mohou časově náročné úkoly způsobit nefunkčnost některých kvantových algoritmů, protože udržování stavu qubitů po dostatečně dlouhou dobu nakonec poškodí superpozice.
Tyto problémy jsou pro optické přístupy obtížnější, protože časové osy jsou řádově kratší a často citovaným přístupem k jejich překonání je optické tvarování pulzů. Četnost chyb je obvykle úměrná poměru provozní doby k době dekoherence, takže jakákoli operace musí být dokončena mnohem rychleji než doba dekoherence.
Jak je popsáno ve větě o kvantovém prahu, pokud je chybovost dostatečně malá, předpokládá se, že je možné použít kvantovou korekci chyb k potlačení chyb a dekoherence. To umožňuje, aby celková doba výpočtu byla delší než doba dekoherence, pokud schéma opravy chyb dokáže opravit chyby rychleji, než je dekoherence zavádí. Často citovaný údaj pro požadovanou chybovost v každém hradle pro výpočet odolný proti chybám je 10−3, za předpokladu, že šum je depolarizující.
Splnění této podmínky škálovatelnosti je možné pro širokou škálu systémů. Použití opravy chyb však s sebou přináší náklady na značně zvýšený počet požadovaných qubitů. Číslo požadované k faktoru celých čísel pomocí Shorova algoritmu je stále polynomiální a předpokládá se, že je mezi L a L2, kde L je počet číslic v čísle, které má být faktorizováno; algoritmy pro opravu chyb by toto číslo zvýšily o další faktor L. Pro 1000bitové číslo to znamená potřebu asi 104 bitů bez opravy chyb. S opravou chyb by číslo vzrostlo na asi 107 bitů. Doba výpočtu je asi L2 nebo asi 107 kroků a při 1 MHz asi 10 sekund.
Velmi odlišným přístupem k problému stability a dekoherence je vytvoření topologického kvantového počítače s anyony, kvazičásticemi používanými jako vlákna a spoléhání se na teorii opletení k vytvoření stabilních logických hradel.
Kvantová nadřazenost
Kvantová nadřazenost je termín vytvořený Johnem Preskillem, který odkazuje na inženýrský výkon, kterým je demonstrovat, že programovatelné kvantové zařízení může vyřešit problém přesahující možnosti nejmodernějších klasických počítačů. Problém nemusí být užitečný, takže někteří považují test kvantové převahy pouze za potenciální budoucí měřítko.
V říjnu 2019 se Google AI Quantum s pomocí NASA stal první, kdo tvrdil, že dosáhl kvantové převahy prováděním výpočtů na kvantovém počítači Sycamore více než 3,000,000 XNUMX XNUMXkrát rychleji, než by bylo možné provést na Summitu, který je obecně považován za nejrychlejší na světě. počítač. Toto tvrzení bylo následně zpochybněno: IBM uvedla, že Summit může provádět vzorky mnohem rychleji, než se tvrdilo, a výzkumníci od té doby vyvinuli lepší algoritmy pro problém vzorkování používaného k tvrzení o kvantové nadřazenosti, což poskytuje podstatné snížení nebo uzavření propasti mezi Sycamore a Sycamore. klasické superpočítače.
V prosinci 2020 skupina v USTC implementovala typ bosonového vzorkování na 76 fotonech pomocí fotonického kvantového počítače Jiuzhang, aby demonstrovala kvantovou nadřazenost. Autoři tvrdí, že klasický současný superpočítač by vyžadoval výpočetní čas 600 milionů let, aby vygeneroval počet vzorků, které jejich kvantový procesor dokáže vygenerovat za 20 sekund. Dne 16. listopadu 2021 představila společnost IBM na summitu o kvantových počítačích 127-qubitový mikroprocesor s názvem IBM Eagle.
Fyzické implementace
Pro fyzickou implementaci kvantového počítače se hledá mnoho různých kandidátů, mezi nimiž (rozlišují se podle fyzického systému použitého k realizaci qubitů):
- Supravodivé kvantové výpočty (qubit implementovaný stavem malých supravodivých obvodů, Josephsonovy spoje)
- Zachycený iontový kvantový počítač (qubit implementovaný vnitřním stavem zachycených iontů)
- Neutrální atomy v optických mřížkách (qubit implementovaný vnitřními stavy neutrálních atomů zachycených v optické mřížce)
- Počítač s kvantovou tečkou, založený na spinu (např. kvantový počítač Loss-DiVincenzo) (qubit daný spinovými stavy zachycených elektronů)
- Počítač s kvantovou tečkou, prostorový (qubit daný pozicí elektronu ve dvojité kvantové tečce)
- Kvantové výpočty využívající inženýrské kvantové studny, které by v zásadě mohly umožnit konstrukci kvantových počítačů, které pracují při pokojové teplotě
- Vázaný kvantový drát (qubit implementovaný dvojicí kvantových drátů spojených kvantovým bodovým kontaktem)
- Kvantový počítač nukleární magnetické rezonance (NMRQC) implementovaný s nukleární magnetickou rezonancí molekul v roztoku, kde qubity jsou poskytovány jadernými spiny v rozpuštěné molekule a sondovány rádiovými vlnami
- Pevné NMR Kaneovy kvantové počítače (qubit realizovaný jaderným spinovým stavem dárců fosforu v křemíku)
- Kvantové počítače elektrony na héliu (qubit je elektronový spin)
- Dutinová kvantová elektrodynamika (CQED) (qubit poskytovaný vnitřním stavem zachycených atomů spojených s vysoce jemnými dutinami)
- Molekulární magnet (qubit daný spinovými stavy)
- Kvantový počítač ESR založený na fulerenu (qubit založený na elektronickém spinu atomů nebo molekul uzavřených ve fullerenech)
- Nelineární optický kvantový počítač (qubity realizované zpracováním stavů různých režimů světla prostřednictvím lineárních i nelineárních prvků)
- Lineární optický kvantový počítač (qubity realizované zpracováním stavů různých režimů světla prostřednictvím lineárních prvků, např. zrcadel, děličů paprsků a fázových posuvníků)
- Kvantový počítač na bázi diamantu (qubit realizovaný elektronickým nebo nukleárním spinem center dusíkové vakance v diamantu)
- Bose-Einsteinův kvantový počítač založený na kondenzátu
- Kvantový počítač na bázi tranzistoru – strunové kvantové počítače se strháváním kladných děr pomocí elektrostatické pasti
- Kvantové počítače na bázi anorganických krystalů dopovaných kovy vzácných zemin (qubit realizovaný vnitřním elektronickým stavem dopantů v optických vláknech)
- Kvantové počítače založené na uhlíkových nanokuličkách podobných kovu
- Velký počet kandidátů ukazuje, že kvantové výpočty jsou navzdory rychlému pokroku stále v plenkách.
Existuje řada kvantových výpočetních modelů, které se liší základními prvky, ve kterých je výpočet rozložen. Pro praktické implementace jsou čtyři relevantní modely výpočtu:
- Kvantové hradlové pole (výpočet rozložený do sekvence několika qubitových kvantových hradel)
- Jednosměrný kvantový počítač (výpočet rozložený do sekvence jedno-qubitových měření aplikovaných na vysoce zapletený počáteční stav nebo stav clusteru)
- Adiabatický kvantový počítač, založený na kvantovém žíhání (výpočet rozložený na pomalou kontinuální transformaci počátečního hamiltoniánu na konečný hamiltonián, jehož základní stavy obsahují řešení)
- Topologický kvantový počítač (výpočet rozložený do opletení anyonů ve 2D mřížce)
Kvantový Turingův stroj je teoreticky důležitý, ale fyzická implementace tohoto modelu není proveditelná. Všechny čtyři modely výpočtu se ukázaly být ekvivalentní; každý z nich může simulovat ten druhý s ne více než polynomiální režií.
Chcete-li se podrobně seznámit s certifikačním kurikulem, můžete rozšířit a analyzovat níže uvedenou tabulku.
Certifikační kurikulum základů kvantových informací EITC/QI/QIF odkazuje na didaktické materiály s otevřeným přístupem ve formě videa. Učební proces je rozdělen do struktury krok za krokem (programy -> lekce -> témata) pokrývající příslušné části kurikula. Poskytujeme také neomezené poradenství s odborníky na domény.
Podrobnosti o kontrole certifikačního postupu Jak to funguje.
Hlavní poznámky k přednášce
Poznámky k přednášce U. Vazirani:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Podpůrné poznámky k přednášce
L. Jačák a kol. poznámky k přednášce (s doplňkovými materiály):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Hlavní podpůrná učebnice
Učebnice Quantum Computation & Quantum Information (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Další poznámky k přednášce
Poznámky k přednášce J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
Poznámky k přednášce A. Childse:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Poznámky k přednášce S. Aaronson:
https://scottaaronson.blog/?p=3943
Poznámky k přednášce R. de Wolf:
https://arxiv.org/abs/1907.09415
Další doporučené učebnice
Klasické a kvantové výpočty (Kitaev, Shen, Vjalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Quantum Computing od Demokrita (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Teorie kvantové informace (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Kvantová informační teorie (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Stáhněte si kompletní offline samoučící se přípravné materiály pro program EITC/QI/QIF Quantum Information Fundamentals v souboru PDF
Přípravné materiály EITC/QI/QIF – standardní verze
Přípravné materiály EITC/QI/QIF – rozšířená verze o recenzní otázky