Wikipedista:JozumBjada/Pískoviště

článek "Kvantové počítání"

Související informace naleznete také na stránce Kvantový počítač.

Jako kvantové počítání (anglicky quantum computing) se souhrně označují výpočetní algoritmy a techniky pro zpracování informace, které pro zefektivnění výpočtu využívají jevů kvantové fyziky. Zatímco klasické počítače provádějí algoritmy založené na zpracování informace uložené ve formě bitů, tedy nul a jedniček, dokážou algoritmy kvantové nakládat s obecnějšími jednotkami informace, označovanými jako qubity nebo kvantové bity. Tyto qubity vykazují vlastnosti známé z kvantové fyziky. Jedním z nejzásadnějších rozdílů oproti klasickému zpracování informace je možnost využití jevu kvantové superpozice. Nosič informace se totiž může nacházet ve stavu, který není ani 0 ani 1, ale v jistém smyslu "mezi" těmito hraničními hodnotami. Způsobů, jakými může být "mezi" je přitom velké množství a každý z nich má trochu odlišné vlastnosti, jež lze využít pro urychlení výpočtu.

Tato stránka se věnuje teorii kvantového počítání. Pro podrobnější popis konkrétních technických řešení pro sestrojení kvantového počítače, viz stránku kvantový počítač.

Kvantově výpočetní algoritmy lze účinně využít pouze na kvantových počítačích, jejichž vývoj je od 10. let 20. století předmětem velmi aktivního výzkumu. I přes velký pokrok zatím však plnohodnotný a průmyslově využitelný kvantový počítač nebyl sestrojen. Hlavní překážkou je především ne zcela zvládnutá technologie umožňující odstínit kvantové bity a hradla od rušivého vlivu prostředí, jehož vlivem dochází velmi rychle ke ztrátě koherence a tedy kvantových vlastností nosičů informace. Z tohoto důvodu se část výzkumu zaměřuje i na kvantové simulátory, což jsou zařízení určená pro specifický účel s jednodušší strukturou, která nejsou schopná narozdíl od počítačů provádět univerzální výpočty. V současné době se vývoj kvantových počítačů pro vysoké náklady soustřeďuje kromě několika experimentálních laboratoří především do vývojových oddělení nadnárodních firem jako Google či IBM, vývoj nových kvantových algoritmů pak probíhá i na univerzitách a na vědeckých ústavech...

Spolu s kvantovou komunikací a kvantovou informatikou tvoří kvantové počítání jedno z odvětví, které se snaží využít poznatků kvantové fyziky pro efektivnější přenos a zpracování informace. Souhrně se tato odvětví někdy označují jako kvantové technologie.

kvantové počítače a kvantové simulátory

kolik qubitů třeba, aby to začalo dělat něco zajímavýho

Historie

Za první zmínku o využití kvantové fyziky pro provádění výpočtů je považována přednáška ... amerického fyzika Richarda Feynmana, ve které nastínil ... Zhruba ve stejné době publikoval "Benioff" článek, ve kterém prezentoval kvantovou obdobu Turingova stroje, univerzálního abstraktního výpočetního zařízení... Schopnosti tehdejší technologie byly nicméně ...

V roce ... prezentoval David Deutsch kvantový algoritmus, který vyžadoval jedno vyhodnocení pro vyřešení problému, pro jehož řešení by klasický algoritmus potřeboval vyhodnocení dvě. Jeho myšlenka byla zobecněna Jozsou a dnes je tato upravená verze známá jako Deutsch-Jozsův algoritmus. Ačkoli tento algoritmus představuje konkrétní úlohu, kde kvantová fyzika umožňuje řešení mnohokrát efektivněji než je to možné klasicky, jedná se stále jen o vykonstruovanou úlohu, která nemá žádný praktický dosah. To změnil v roce ... Peter Shor, který ukázal, jak lze kvantový algoritmus využít pro faktorizaci prvočísel a výpočet diskrétního logaritmu. Tento algoritmus je exponenciálně rychlejší než dosud nejrychlejší známé klasické algoritmy a pokud by se podařilo sestrojit dostatečně výkonný kvantový počítač, lze Shorův algoritmus použít pro prolomení moderních šifer založených na metodě RSA. Shorovy objevy vedly k vlně zájmu o kvantové počítání obecně. V roce ... následoval objev Groverova algoritmu, který umožňuje optimální prohledávání databází a poskytuje kvadratické zrychlení oproti klasickým algoritmům.

první experimentální ... ...Od roku ... se vývojem kvantových počítačů začínají zabývat i komerční společnosti. Tahouny jsou především společnosti Google a IBM, jež vývíjejí univerzální kvantové počítače založené na supravodivých čipech. Vývoji kvantových simulátorů se dlouhodobě věnují například firmy D-Wave či ...

Dosud sestrojené kvantové počítače mají jen velmi malý výkon, kde je hlavním omezením především ne zcela vyvinutá technologie. V dohledné době se proto výzkum věnuje především vývoji tak zvaných NISQ zařízení (z anglického anglicky noisy intermediate-scale quantum devices, neboli kvantová zařízení středního měřítka se šumem). Tato zařízení ještě nedosahují kvality, velikosti a výkonu skutečných kvantových počítačů, ale jsou již schopna v některých ohledech provádět operace, které klasické počítače v rozumné době nedokážou. Jedním z hlavních cílů současného výzkumu je dosažení tak zvané kvantové nadřazenosti (anglicky quantum supremacy) či kvantové výhody (anglicky quantum advantage), což je označejí pro stav, kdy již kvantové počítače dokážou svým výkonem předčít moderní klasické superpočítače. Firma Google již v roce ... ohlásila dosažení kvantové nadřazenosti, když na svém počítači provedla testy metodou náhodných algoritmů. Výsledky byly nicméně záhy po ohlášení zpochybňovány.... V roce ... pak dosažení kvantové nadřazenosti ohlásila čínská výzkumná skupina..., kde byl v laboratoři sestrojena aparatura pro provádění algoritmu zvaného boson sampling. I přes slibné výsledky je ale i tato metoda zajímavá spíše z akademického pohledu a dosud nenalezla skutečně praktické využití.

Vývoj kvantových počítačů zažívá v ... strmý vzestup. Počet firem a start-upů zabývajících se vývojem kvantových počítačů rok od roku stoupá a spolu s tím i objem investic, které v roce ... přesáhly... a do roku ... se počítá s investicemi ... V této souvislosti byly již vzneseny obavy, že se jedná svým způsobem o bublinu, kdy očekávání vysoko přesahují možnosti této nové technologie, což může v konečném důsledku vést k opadnutí zájmu a zbrždění vývoje...

Feynman, "Benioff"... Deutsch-Jozsův algoritmus Shor Grover první experimentální ... komerční společnosti v roce ... kvantová nadřazenost Googlem; v roce ... kvant. nad. kvantové počítače NISQ (z anglického anglicky noisy intermediate-scale quantum)... kvantová nadřazenost (anglicky quantum supramacy) či kvantová výhoda (anglicky quantum advantage)

Kvantové vs klasické počítání

Hlavní myšlenkou kvantového počítání je využití kvantových jevů pro urychlení a zefektivnění výpočtů, jinak prováděných na klasických počítačích. Takovými jevy může být například kvantová superpozice či kvantové provázání, viz níže. Zatímco klasické výpočty probíhají tak, že se sada bitů posílá v daném pořadí do různých logických hradel, je v kvantovém počítači zasílána sada kvantových bitů, tak zvaných qubitů, do kvantových hradel. Jednotka informace v klasickém počítání, bit, může nabývat dvou stavů, 0 a 1. Naproti tomu se může kvantový bit nacházet obecně v libovolné kvantové superpozici dvou stavů, |0> a |1>. Při provádění operací na qubitech může docházet ke vzniku provázaných stavů, kdy se sada qubitů chová v podstatě jako jeden jediný fyzikální systém s netriviálními vlastnostmi.

Klasický bit může být fyzikálně reprezentován třeba různě velkým elektrickým napětím na vývodech elektrické součátky. Naproti tomu qubity mohou být reprezentovány například jako různé energetické hladiny atomů, apod.

Využití kvantových jevů slibuje nové možnosti při zpracování informace. Současně to nicméně neznamená, že kvantová varianta daného klasického algoritmu je nutně rychlejší než původní verze. Nalézt kvantový algoritmus, který předčí libovolnou klasickou alternativu, je velmi obtížné a dosud bylo objeveno jen několik málo tříd algoritmů, které tuto podmínku splňují. Přísně vzato není dodnes známo, zda kvantové počítání vůbec představuje výkonější způsob počítání, než jaký dovolují současné klasické počítače. To je zaviněno skutečností, že dosud nebyla potvrzena či vyvrácena hypotéza ... To, že jsou již nalezené rychlé kvantové algoritmy mnohonásobně rychlejší než současné klasické algoritmy totiž ještě nevylučuje fakt, že bude v budoucnu objeven lepší klasický algoritmus... Současný výzkum je tak spíše založen na naději, že kvantové počítače skutečně ty klasické předčí, a to i na principiální úrovni. Současně s tím se však již nyní ví, že ani kvantové počítače nedokážou vyřešit všechno. Existuje třída výpočetních problémů, označovaná jako ..., pro kterou lze matematicky dokázat, že ani využití kvantových jevů nevede k jejich efektivnímu řešení.

Kvantový počítač jako technický pojem lze chápat dvěma způsoby. Jednak jako skutečné zařízení, na kterém lze provádět výpočty, jednak jako teoretický koncept, s jehož pomocí lze vymýšlet kvantové algoritmy. Podobně jako není třeba pro vynalezení klasického algoritmu pro danou úlohu disponovat skutečným počítačem, není ani pro vynalezení kvantového algoritmu disponovat počítačem kvantovým. Je ale třeba vědět, jaké operace lze na hypotetickém kvantovém počítači provádět. Když se v současnosti hovoří o kvantovém počítači, je stále myšlen spíše jen tento teoretický koncept. Sestrojit skutečný kvantový počítač je totiž na naprosté hranici současných technologických možností a i přes znatelný technologický pokrok dosud žádný dostatečně výkonný kvantový počítač sestrojen nebyl. Pro vyjádření výkonu klasických počítačů se běžně používají měřítka jako počet operací za vteřinu, velikost operační paměti či velikost paměti na pevném disku. Sestrojit kvantovou paměť je extrémně náročné a výzkum je v tomto ohledu na samotném začátku. Počet operací za sekundu je pro změnu limitován počtem proveditelných operací. V současnosti totiž kvantový hardware naráží na limity dané kvalitou kvantových hradel. Měřítky pro popis kvantových počítačů tak v současnosti jsou spíše počet qubitů a tak zvaná koherenční doba, která v podstatě říká, jak dlouho lze s qubity manipulovat, než tyto ztratí svůj kvantový charakter vlivem dekoherence.

škálování exponenciálně s počtem qubitů - rozdíl oproti klasickým počítačům???

dodnes se neví, zda je kvantové počítání vážně lepší

už teď se ví, že ani kvant. počítač nedokáže řešit efektivně jistou třídu problémů

current hype about quantum computers and its consequences...

kolik qubitů třeba, aby to začalo dělat něco zajímavýho

Základní stavební bloky

Kvantový popis

Související informace naleznete také na stránce Braketový formalizmus.

PŘEPSAT TO TAK, ABY TO NEUPŘEDNOSTŇOVALO QUANTUM CIRCUIT PICTURE S HRADLY

Kvantové počítání využívá ke zpracování informace fyzikální systémy, které vykazují kvantové jevy. Pro popis takovýchto systémů je tedy nutno použít kvantovou teorii a s ní související formalizmus. V naprosté obecnosti je časový vývoj izolovaného kvantového systému popsán tak zvanou unitární operací. Provádění výpočtu odpovídá speciálně navrženému časovému vývoji a tak i algoritmus samotný lze (s výjimkou měření, viz dále) vyjádřit pomocí unitární transformace. Tuto transformaci lze rozložit do součinu většího počtu jednoduchých elementárních unitárních transformací, kterým se po vzoru logických hradel říká kvantová hradla.

Mluvíme-li o časovém vývoji kvantového systému, máme především na mysli vývoj jeho kvantového stavu. Kvantový stav je soubor veškerých znalostí, které lze o daném systému získat pomocí kvantových měření. Kvantové stavy lze v zásadě rozdělit do dvou skupin na stavy čisté a stavy smíšené. Čisté stavy lze reprezentovat vektorem ve vektorovém prostoru, zatímco pro popis smíšených stavů je nutno použít pokročilejší aparát matic hustoty . V následujícím výklady jsou uvažovány pouze čisté stavy, jež jsou popsány braketovým formalizmem. Kvantový systém je na počátku vytvořen v jistém kvantovém stavu a tento stav se mění v závislosti na tom, jakými hradly daný kvantový systém prochází nebo kterým hradlům je vystavem. Na konci výpočtu je systém vystaven kvantovému měření a ze získaných naměřených hodnot lze vyčíst výsledek výpočtu. V mnoha případech je přitom potřeba nechat daný algoritmus proběhnout vícekrát, protože může být naměřený výsledek pokaždé trochu jiný, a to i když je výpočet prováděn na těchže vstupních datech. Důvodem tohoto chování jsou vlastnosti kvantových stavů a jejich měření, které vykazuje jistou míru náhodnosti, které se nelze zbavit. Ze získaných výsledků lze nicméně statistickými metodami odhadnout správný výsledek. Mnoho kvantových algoritmů je tak stochastických.

Kvantové bity

Podrobnější informace naleznete na stránce Qubit.

...bit, qubit, ebit...

ebit je jednotkou provázání, která je definována jako provázání jednoho páru maximálně provázaných qubitů (technicky vzato je provázání dvou qubitů rovno x ebitům, je-li von Neumannova entropie jednotlivých qubitů rovna x, kde je v entropii za základ logaritmu vzato číslo 2.)

Základním a dosud nejčastěji používaným kvantovým systémem je tak zvaný qubit neboli kvantový bit. Jedná se o fyzikální systém, který se může nacházet ve dvou různých hraničních stavech, běžně označovaných jako $|0\rangle$ a $|1\rangle$, či v kterékoli jejich superpozici. Obecný stav $|\psi \rangle$ qubitu tak lze zapsat ve tvaru

$|\psi \rangle =\alpha |0\rangle +\beta |1\rangle ,$

kde $\alpha$ a $\beta$ jsou komplexní čísla zvaná amplitudy pravděpodobnosti, která splňují normovací podmínku $|\angle |^{2}+|\beta |^{2}=$ a která udávají pravděpodobnosti naměření stavu $|0\rangle$ či stavu $|1\rangle$. V reálném případě může být qubitem například atom, který se může nacházet buď v základním stavu, excitovaném stavu, či v jejich superpozici. Jinou experimentální realizací qubitu pak může být například foton, jehož polarizace může být horizántální, vertikální, anebo superpozice těchto dvou polarizací.

Qubity jsou často popisovány jako kvantová varianta bitů známých z klasických informačních technologií, kde může qubit, na rozdíl od bitu klasického, nabývat nejen hodnot 0 a 1, ale i hodnot mezi. I přes značnou blízkou a analogii s klasickými bity mají qubity nicméně velmi odlišné vlastnosti. Tak například vektory $|0\rangle$ a $|1\rangle$ nemají žádné výsadní postavení a tentýž stav qubitu lze napsat mnoha různými způsoby. Pokud vytvoříme novou ortonormální bázi qubitu z vektorů $|+\rangle$ a $|-\rangle$, tak lze stav $|\psi \rangle$, vypsaný výše, vyjádřit stejně dobře v této nové bázi. Šlo by tedy poté říci, že qubit se může nacházet buď ve stavu $|+\rangle$, stavu $|-\rangle$ a nebo v nějaké jejich superpozici. Podobná změna báze není pro klasické bity možná. Změna báze není přitom pouze formální změna popisu téhož vektoru. Při měření daného qubitu v různých bázích se obdrží obecně různé výsledky, jak plyne z Bornova pravidla.

Podobně jako běžný počítač pracuje naráz s velkým množstvím bitů, počítač kvantový pro svoji efektivní práci potřebuje velký počet qubitů. Komplexnost možných kvantových stavů přitom roste exponenciálně s počtem zpracovávaných qubitů. Qubity lze i shlukovat do skupin, které se jako celek mohou chovat jako jeden velký qubit. Této techniky je využíváno například pro zvýšení odolnosti kvantového výpočtu vůči šumu a rušení způsobeného nedokonalým hardwarem. Takovému velkému qubitu se říká logický qubit, přičemž každá jeho jednotlivá složka se nazývá fyzikální qubit. Máme-li například tři fyzikální qubity ve formě tří atomů, lze z nich vytvořit jeden logický qubit následujícím způsobem

$|\psi _{\text{log}}\rangle =\alpha |0\rangle _{\text{fyz 1}}\otimes |0\rangle _{\text{fyz 2}}\otimes |0\rangle _{\text{fyz 3}}+\beta |1\rangle _{\text{fyz 1}}\otimes |1\rangle _{\text{fyz 2}}\otimes |1\rangle _{\text{fyz 3}},$

kde $\otimes$ označuje tenzorový součin, $|0\rangle _{\text{fyz 1}}$ označuje stav $|0\rangle$ prvního fyzikálního systému atd. Takovýto složitější stav tří atomů má tu výhodu, že pokud se vlivem prostředí nechtěně jeden atom "přepne" z $|0\rangle$ na $|1\rangle$ (a naopak), lze stále z výsledného stavu zrekonstruovat stav původní. Po takové záměně, například na třetím atomu, vypadá stav najednou

$|\psi _{\text{log}}\rangle =\alpha |0\rangle _{\text{fyz 1}}\otimes |0\rangle _{\text{fyz 2}}\otimes |1\rangle _{\text{fyz 3}}+\beta |1\rangle _{\text{fyz 1}}\otimes |1\rangle _{\text{fyz 2}}\otimes |0\rangle _{\text{fyz 3}}.$

Stále ale v obou ketech převažují správné stavy a vhodnou transformací lze převést stav do původního tvaru.

Kvantová superpozice a provázání

Podrobnější informace naleznete na stránkách Kvantová superpozice a Kvantové provázání.

kvantové superpozice -> kvantový paralelizmus - to je ale kompenzováno tím, že lze změřit jen jeden výsledek - lze to však obejít... kvantové provázání

kvantová hradla... - lze ukázat, že každý výpočet lze rozložit do jednoqubitových a dvouqubitových hradel ...-Kitaev theorem o tom, že lze aproximovat každou unitární operaci efektivně použitím fixní sady univerzálních hradel

Clifford group...;

univerzální hradla - CNOT, Fredkin, ...Toffoli...

kvantové paměti

fyzický qubit vs logický qubit

kvantové superpozice -> kvantový paralelizmus - to je ale kompenzováno tím, že lze změřit jen jeden výsledek - lze to však obejít... kvantové provázání škálování exponenciálně s počtem qubitů - rozdíl oproti klasickým počítačům???

kvantová hradla... - lze ukázat, že každý výpočet lze rozložit do jednoqubitových a dvouqubitových hradel ...-Kitaev theorem o tom, že lze aproximovat každou unitární operaci efektivně použitím fixní sady univerzálních hradel

Clifford group...;

univerzální hradla - CNOT, Fredkin, ...Toffoli...

Algoritmy

Deutsch-Jozsův algoritmus

jen toy example...

Shorův algoritmus

diskrétní logaritmus, nacházení prvočinitelů

aplikace v kryptografii

exponenciální zrychlení

Groverův algoritmus

procházení databází

kvadratické zrychlení

Kvantové strojové učení

mnoho různých technik

Random circuits

Google used to show supremacy

Architektury

Kvantové obvody

Patrně nejpoužívanější architekturou pro popis kvantových algoritmů jsou kvantové obvody (anglicky quantum circuits), kde je výpočet rozčleněn do jednotlivých základních bloků, zvaných kvantová hradla (anglicky quantum gates). Jedná se o kvantová zobecnění logických hradel známých z klasických výpočetních architektur. Výpočet je vyjádřen jako časový vývoj daného počtu qubitů, z nichž každý je na diagramu představován vodorovnou čarou, kde čas plyne zleva doprava. Jednotlivé qubity pak podstupují vývoj zadaný jednak jednoqubitovými hradly jednak vícequbitovými hradly, která umožňují interakci dvou a více qubitů.

příklad... klasická notace pro CNOT atd.

quantum circuits

rozdělení výpočtu do jednotlivých kvantových hradel (quantum gate)

příklad... klasická notace pro CNOT atd.

Počítání založené na měření

measurement-based quantum computation

Briegels návrh návrh Chuanga založený na teleportaci

blind quantum computing

Adiabatické počítání

...

KLM schéma

Fotony představují výborné kvantové nosiče informace, protože jsou málo náchylné na rušivé vlivy okolí. Ze stejného důvodu je nicméně obtížné přinutit fotony, aby interagovaly. V principu by šlo toho dosáhnout tak, že dva fotony vlétnou současně do nelineárního prostředí, kde interakce jednoho fotonu s prostředí změní stav prostředí, které posléze interaguje s fotonem druhým. Pro praktické využití by však bylo potřeba dosáhnout nelinearity výrazně převyšující současné technologické limity. Altenativní přístup poskytuje kvantové měření, které do vývoje fotonů vnáší nelinearitu uměle. Jak v roce 2001 teoreticky ukázaly Knill, Laflamme a Millburn , lze s pomocí jednoduchých optických operací a měření sestrojit univerzální kvantový počítač využívající fotony jako nosiče informace. I přes tento průlomový objev je počet fotonů nicméně stále v rozmezích nedosažitelných současnou technologií.

princip fungování...

Kvantová oprava chyb

Velkou kapitolu v oblasti kvantového počítání tvoří techniky, díky nimž lze buď zcela elimininovat či alespoň zmenšit dopad nejrůznějších chyb vznikajících během výpočtu. Za chyby se v tomto kontextu považují náhodné a nepředvídatelné změny v kvantovém stavu qubitů, které vznikají například vlivem technických nedokonalostí kvantového počítače. Pokud se tyto chyby ignorují, dochází velmi rychle k jejich akumulaci a výsledný výpočet je tak nepoužitelný. Technikám, které umožňují detekovat a následně opravit vzniklé chyby se anglicky říká quantum error correction, což lze přeložit jako oprava kvantových chyb. Pokud stačí v dané aplikaci povolit jistou nízkou úroveň chyb, lze použít jiné techniky, kolektivně anglicky označované jako quantum error mitigation, tedy zmírnění kvantových chyb.

quantum mitigation (viz NISQ)

Shor codes...

surface code, topological quantum computation, anyons, ...

stabilizer formalism

Odkazy

Literatura

• ...Nielsen and Chuang...

Související články

• Počítání
• Kvantový počítač
• Kvantová informatika
• Kvantová nadřazenost
• Qubit
• NISQ
• Kvantová superpozice
• Kvantové provázání
• Foton