Blochova sféra představuje qubit, základní stavební prvek kvantových počítačů.
Kvantový počítač je jakékoliv výpočetní zařízení, které k provádění operací s daty přímo využívá výrazně kvantově mechanické jevy, jako je superpozice a provázanost. V klasickém (nebo konvenčním) počítači se množství dat měří v bitech; v kvantovém počítači se data měří v qubitech. Základním principem kvantových výpočtů je, že kvantové vlastnosti částic lze využít k reprezentaci a strukturování dat a že lze navrhnout a vytvořit kvantové mechanismy pro provádění operací s těmito daty.
Ačkoli je kvantová výpočetní technika stále v plenkách, byly provedeny experimenty, při nichž byly kvantové výpočetní operace prováděny na velmi malém počtu qubitů. Výzkum v teoretických i praktických oblastech pokračuje zběsilým tempem a mnoho národních vládních a vojenských finančních agentur podporuje výzkum kvantových počítačů s cílem vyvinout kvantové počítače pro civilní i národní bezpečnostní účely, jako je například kryptoanalýza.
(Podrobnosti o současném i minulém pokroku naleznete v části Časová osa kvantové výpočetní techniky.)
Základ kvantové výpočetní techniky
V kvantové mechanice je stav fyzikálního systému (například elektronu nebo fotonu) popsán vektorem v matematickém objektu zvaném Hilbertův prostor. Realizace Hilbertova prostoru závisí na konkrétním systému. Například v případě systému jedné částice ve třech rozměrech lze stav popsat komplexně vyjádřenou funkcí definovanou na R3 (třírozměrný prostor), která se nazývá vlnová funkce. Jak je popsáno v článku o kvantové mechanice, tato funkce má pravděpodobnostní interpretaci; zvláště důležité je, že kvantové stavy mohou být v superpozici základních stavů. Předpokládá se, že časový vývoj stavového vektoru systému je unitární, což znamená, že je vratný.
Klasický počítač má paměť složenou z bitů, kde každý bit obsahuje buď jedničku, nebo nulu. Zařízení počítá manipulací s těmito bity, tj. přenášením těchto bitů z paměti do (případně do sady) logických hradel a zpět. Kvantový počítač udržuje vektor qubitů. V qubitu může být jednička, nula nebo jejich superpozice. Kvantový počítač pracuje tak, že manipuluje s těmito qubity, tj. přenáší tyto bity z paměti do (případně do sady) kvantových logických hradel a zpět.
Základní aspekty kvantových počítačů najdete v článku o kvantových obvodech.
Uvažujme nejprve klasický počítač, který pracuje s 3bitovým registrem. V každém okamžiku jsou bity v registru v určitém stavu, například 101. V kvantovém počítači však mohou být qubity v superpozici všech klasicky přípustných stavů. Ve skutečnosti je registr popsán vlnovou funkcí:
kde koeficienty , , , … jsou komplexní čísla, jejichž amplitudy na druhou jsou pravděpodobnosti měření qubitů v jednotlivých stavech. Z toho vyplývá, že je pravděpodobnost změřit registr ve stavu 010. Je důležité, že tato čísla jsou komplexní, a to z toho důvodu, že fáze čísel mohou navzájem konstruktivně a destruktivně interferovat; to je důležitá vlastnost pro kvantové algoritmy.
Pro n qubitový kvantový registr vyžaduje záznam stavu registru 2n komplexních čísel (3qubitový registr vyžaduje 23 = 8 čísel). V důsledku toho počet klasických stavů zakódovaných v kvantovém registru roste exponenciálně s počtem qubitů. Pro n=300 je to zhruba 1090, tedy více stavů, než je atomů ve známém vesmíru. Všimněte si, že všechny koeficienty nejsou nezávislé, protože pravděpodobnosti musí být v součtu 1. Reprezentace je také (pro většinu praktických případů) nejedinečná, protože neexistuje způsob, jak fyzikálně rozlišit mezi konkrétním kvantovým registrem a podobným registrem, kde byly všechny amplitudy vynásobeny stejnou fází, jako je -1, i nebo obecně jakékoli číslo na komplexním jednotkovém kruhu.
Lze ukázat, že rozměr množiny stavů n qubitového registru je 2n+1 – 2. Viz Blochova sféra.
Inicializace, provádění a ukončení
V našem příkladu si lze obsah qubitových registrů představit jako osmirozměrný komplexní vektor. Algoritmus pro kvantový počítač musí tento vektor inicializovat v nějakém specifikovaném tvaru (závislém na konstrukci kvantového počítače). V každém kroku algoritmu je tento vektor modifikován vynásobením jednotkovou maticí. Tato matice je určena fyzikou zařízení. Unitární charakter matice zajišťuje, že matice je invertibilní (takže každý krok je reverzibilní).
Po ukončení algoritmu musí být osmirozměrný komplexní vektor uložený v registru nějakým způsobem odečten z qubitového registru pomocí kvantového měření. Podle zákonů kvantové mechaniky však toto měření poskytne náhodný tříbitový řetězec (a zničí i uložený stav). Tento náhodný řetězec lze použít při výpočtu hodnoty funkce, protože (podle návrhu) je pravděpodobnostní rozdělení naměřeného výstupního bitového řetězce zkreslené ve prospěch správné hodnoty funkce. Opakovaným spuštěním kvantového počítače a měřením výstupu lze s vysokou pravděpodobností určit správnou hodnotu většinovým výběrem výstupů. Stručně řečeno, kvantové výpočty jsou pravděpodobnostní, přesnější formulace viz kvantový obvod.
Kvantový algoritmus je realizován vhodnou posloupností jednotkových operací. Všimněte si, že pro daný algoritmus budou operace vždy provedeny v přesně stejném pořadí. Neexistuje žádný příkaz „IF THEN“, který by měnil pořadí, protože neexistuje žádný způsob, jak přečíst stav qubitu před konečným měřením. Existují však podmíněné operace hradel, jako je řízené hradlo NOT neboli CNOT.
Podrobnější informace o posloupnostech operací používaných pro různé algoritmy naleznete v článcích univerzální kvantový počítač, Shorův algoritmus, Groverův algoritmus, Deutsch-Jozsaův algoritmus, kvantová Fourierova transformace, kvantové hradlo, kvantový adiabatický algoritmus a kvantová oprava chyb. Viz také rostoucí oblast kvantového programování.
Síla kvantových počítačů
Existují některá schémata digitálního podpisu, která jsou považována za bezpečná proti kvantovým počítačům. Viz například Lamportovy podpisy.
Možná není tak překvapivé, že kvantové počítače by mohly být užitečné i pro simulace kvantové mechaniky. Tato myšlenka pochází od Richarda Feynmana (1982), který si všiml, že není znám žádný algoritmus pro simulaci kvantových systémů na klasickém počítači, a navrhl studovat využití kvantových počítačů pro tento účel. Zrychlení dosažené pomocí kvantových počítačů by mohlo být stejně velké jako u faktoringu. To by mohlo být velkým přínosem pro fyziku, chemii, materiálové vědy, nanotechnologie, biologii a medicínu, které jsou dnes omezeny pomalou rychlostí kvantově mechanických simulací. Například některé moderní simulace, které superpočítači IBM Blue Gene trvají roky, by kvantovému počítači zabraly jen několik sekund.
Tato dramatická výhoda kvantových počítačů byla zatím objevena pouze u těchto tří problémů: faktoringu, diskrétního logaritmu a simulací kvantové fyziky. Neexistuje však žádný důkaz, že tato výhoda je skutečná: stejně rychlý klasický algoritmus může být ještě objeven (i když to někteří považují za nepravděpodobné). Existuje ještě jeden problém, kde mají kvantové počítače menší, i když značnou (kvadratickou) výhodu. Jedná se o kvantové vyhledávání v databázích, které lze řešit Groverovým algoritmem. V tomto případě je výhoda prokazatelná. Tím je nade vší pochybnost prokázáno, že (ideální) kvantové počítače mají přinejmenším v jednom problému přednost před klasickými počítači.
Příkladem může být program na prolamování hesel, který se pokouší uhodnout heslo k zašifrovanému souboru (za předpokladu, že heslo má maximální možnou délku).
U úloh se všemi čtyřmi vlastnostmi bude k nalezení odpovědi pomocí klasického počítače potřeba v průměru (n + 1)/2 odhadu. Doba řešení kvantovým počítačem bude úměrná druhé odmocnině z n. To může znamenat velmi velké zrychlení, které některé problémy zkrátí z let na sekundy. Toho lze využít k útoku na symetrické šifry, jako jsou Triple DES a AES, a to tak, že se pokusíme uhodnout tajný klíč. Lze se však proti němu také snadno bránit, a to zdvojnásobením velikosti tohoto klíče. Existují i složitější metody bezpečné komunikace, například pomocí kvantové kryptografie.
Bez ohledu na to, zda se podaří prokázat, že některý z těchto problémů má na kvantovém počítači výhodu, bude mít vždy tu výhodu, že je vynikajícím nástrojem pro studium kvantově mechanických interakcí, což je samo o sobě pro vědeckou komunitu nesmírně cenné.
V současné době nejsou známy žádné jiné praktické problémy, u kterých by kvantové počítače poskytovaly velké zrychlení oproti klasickým počítačům. Výzkum pokračuje a je možné, že budou nalezeny další problémy.
Problémy a praktické otázky
Sestavení kvantového počítače naráží na řadu praktických problémů a kvantové počítače zatím řeší pouze triviální problémy. David DiVincenzo z IBM uvedl následující požadavky na praktický kvantový počítač:
Shrneme-li tento problém z pohledu inženýra, je třeba vyřešit problém sestrojení systému, který je izolován od všeho kromě mechanismu měření a manipulace. Dále je třeba umět vypnout vazbu qubitů na měření, aby nedošlo k dekoherenci qubitů při provádění operací na nich.
Jedním z hlavních problémů je udržet součásti počítače v koherentním stavu, protože sebemenší interakce s vnějším světem by způsobila rozpad systému. Tento efekt způsobuje porušení unitárního charakteru (a přesněji řečeno invertibility) kvantových výpočetních kroků. Dekoherenční časy kandidátních systémů, zejména příčná relaxační doba T2 (terminologie používaná v technologii NMR a MRI, nazývaná také doba odfázování), se při nízké teplotě obvykle pohybují mezi nanosekundami a sekundami. Problém u optických přístupů je obtížnější, protože tyto časy jsou řádově nižší a často uváděný přístup k jeho překonání využívá přístup optického tvarování pulzů. Míra chybovosti je obvykle úměrná poměru operační doby a doby dekoherence, proto musí být jakákoli operace dokončena mnohem rychleji, než je doba dekoherence.
Pokud je chybovost dostatečně malá, je možné použít kvantovou korekci chyb, která opravuje chyby způsobené dekoherencí, a tím umožňuje, aby celková doba výpočtu byla delší než doba dekoherence. Často uváděný (ale spíše arbitrární) údaj pro požadovanou chybovost v každém hradle je 10-4. To znamená, že každé hradlo musí být schopno plnit svůj úkol 10 000krát rychleji, než je dekoherenční doba systému.
Splnění této podmínky škálovatelnosti je možné pro celou řadu systémů. Použití korekce chyb však s sebou nese náklady na značně zvýšený počet potřebných qubitů. Počet potřebný k faktorizaci celých čísel pomocí Shorova algoritmu je stále polynomiální a předpokládá se, že se pohybuje mezi L4 a L6, kde L je počet bitů v čísle, které má být faktorováno. Pro 1000bitové číslo to znamená potřebu 1012 až 1018 qubitů. Výroba a řízení tak velkého počtu qubitů není triviální pro žádný z navrhovaných návrhů.
Zásadnější je, že fyzikální realističnost navrhovaných schémat kvantové opravy chyb byla zpochybněna, protože jejich teoretická analýza předpokládá dostupnost pomocných qubitů, které jsou samy o sobě bezchybné, navzdory nenulovému odfázování, které musí nastat v každém procesu, který trvá nenulový čas. Stálou výzvou pro teoretiky je specifikovat z hlediska qubitů a sekvencí operací proces, který by udržoval stav jediného qubitu, aniž by předpokládal dostupnost idealizovaných qubitů nebo operací.
Zcela odlišným přístupem k problému stability a deherence je vytvoření topologického kvantového počítače s anyony, kvazičásticemi používanými jako vlákna a spoléhajícími se na teorii uzlů pro vytvoření stabilních logických hradel.
Existuje řada kandidátů na kvantové výpočty, mimo jiné:
V roce 2005 sestrojili vědci z Michiganské univerzity polovodičový čip, který fungoval jako iontová past. Taková zařízení vyrobená standardními litografickými technikami mohou ukázat cestu ke škálovatelným kvantovým výpočetním nástrojům. V roce 2006 byla vyrobena vylepšená verze.
Společnost D-Wave Systems Inc. (dwavesys.com) o sobě tvrdí, že je prvním a jediným poskytovatelem kvantových výpočetních systémů na světě určených pro komerční aplikace. Dne 13. února 2007 provedla první demonstraci svého kvantového výpočetního systému Orion, který je postaven na 16qubitovém supravodivém adiabatickém kvantovém počítačovém procesoru. Očekávají se další demonstrace.
Kvantové výpočty v teorii výpočetní složitosti
Předpokládaný vztah BQP k jiným problémovým prostorům
V této části je uveden přehled současných matematických poznatků o výkonu kvantových počítačů. Popisuje známé výsledky z teorie výpočetní složitosti a teorie výpočtů zabývající se kvantovými počítači.
Třída problémů, které lze efektivně řešit kvantovými počítači, se nazývá BQP, což znamená „omezená chyba, kvantový, polynomiální čas“. Kvantové počítače spouštějí pouze náhodné algoritmy, takže BQP na kvantových počítačích je obdobou BPP na klasických počítačích. Je definován jako množina problémů řešitelných algoritmem s polynomiálním časem, jehož pravděpodobnost chyby je ohraničena od jedné čtvrtiny (Nielsen & Chuang 2000). O kvantovém počítači se říká, že „vyřeší“ problém, jestliže pro každou instanci bude jeho odpověď správná s vysokou pravděpodobností. Pokud toto řešení probíhá v polynomiálním čase, pak je tento problém v BQP.
Předpokládá se, že BQP je disjunktní s NP-úplnou a striktní nadmnožinou P, ale to není známo. Jak celočíselná faktorizace, tak diskrétní log jsou v BQP. Oba tyto problémy jsou NP problémy, o nichž se předpokládá, že jsou mimo BPP, a tedy i mimo P. O obou se předpokládá, že nejsou NP-úplné. Existuje rozšířená mylná představa, že kvantové počítače mohou řešit NP-úplné problémy v polynomiálním čase. Není známo, že by to byla pravda, a obecně se předpokládá, že je to nepravda.
Operátor pro kvantový počítač si lze představit jako změnu vektoru vynásobením určitou maticí. Násobení maticí je lineární operace. Daniel S. Abrams a Seth Lloyd ukázali, že pokud by bylo možné navrhnout kvantový počítač s nelineárními operátory, pak by mohl řešit NP-úplné problémy v polynomiálním čase. Mohl by tak dokonce řešit #P-úplné problémy. Nevěří však, že je takový stroj možný.
Ačkoli jsou kvantové počítače někdy rychlejší než klasické, výše popsané typy počítačů nedokážou řešit žádné problémy, které by nedokázaly řešit klasické počítače, pokud by měly dostatek času a paměti (i když možná takové množství, které by se nikdy nedalo prakticky využít). Turingův stroj může tyto kvantové počítače simulovat, takže takový kvantový počítač by nikdy nemohl vyřešit nerozhodnutelný problém, jako je problém zastavení. Existence „standardních“ kvantových počítačů nevyvrací Churchovu-Turingovu tezi (Nielsen a Chuang 2000).
V nedávné době se mnoho výzkumníků začalo zabývat možností využití kvantové mechaniky pro hyperpočítače – tedy řešení nerozhodnutelných problémů. Taková tvrzení se setkala se značnou skepsí ohledně toho, zda je to vůbec teoreticky možné; více informací naleznete v článku o hyperpočítání.
. arXiv:quant-ph/9508027
.
. arXiv:quant-ph/9605043
.
. arXiv:quant-ph/0102078
.
. arXiv:quant-ph/9605011
.
Umělá inteligence – Keramické inženýrství – Výpočetní technika – Elektronika – Energie – Skladování energie – Inženýrská fyzika – Technologie ochrany životního prostředí – Materiálové vědy a inženýrství – Mikrotechnologie – Nanotechnologie – Jaderná technologie – Optické inženýrství – Zoografie
Komunikace – Grafika – Hudební technologie – Rozpoznávání řeči – Vizuální technologie
Stavebnictví – Finanční inženýrství – Výroba – Strojírenství – Těžba – Podniková informatika
Bomby – Zbraně a munice – Vojenská technika a vybavení – Námořní technika
Domácí spotřebiče – Domácí technika – Vzdělávací technika – Potravinářská technika
Letectví a kosmonautika – Zemědělství – Architektura – Bioinženýrství – Biochemie – Biomedicína – Keramika – Chemie – Stavebnictví – Počítače – Konstrukce – Kryogenní – Elektrika – Elektronika – Životní prostředí – Potravinářství – Průmysl – Materiály – Mechanika – Mechatronika – Metalurgie – Hornictví – Námořní doprava – Jaderná energetika – Ropa – Software – Konstrukce – Systémy – Textil – Tkáně
Biomedicínské inženýrství – Bioinformatika – Biotechnologie – Chemická informatika – Technika požární ochrany – Zdravotnické technologie – Farmaceutika – Bezpečnostní inženýrství – Sanitární inženýrství
Letectví a kosmonautika – Letecké a kosmické inženýrství – Námořní inženýrství – Motorová vozidla – Kosmické technologie – Doprava