Kvantové výpočty - Quantum computing

Tento článek je tón nebo styl nemusí odrážet encyklopedický tón použitý na Wikipedii. Viz Wikipedia průvodce psaním lepších článků pro návrhy. (Listopadu 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Kvantové výpočty používá určité algebraické metody k vývoji algoritmů pro výpočty, přičemž tyto algebraické metody jsou ty, které jsou paralelní s těmi, které se používají v kvantové mechanice. „Konceptuální“ počítač, který dokáže tyto algoritmy implementovat, je kvantový počítač.^[1]:I-5.

V jistém smyslu je termín kvantové výpočty nesprávným pojmenováním, protože má tendenci naznačovat význam nějaké technologie, která má být vyvinuta pomocí fyzikálních principů, zatímco ve skutečnosti jde o aplikovanou matematiku výpočtů. (Možná je lepší převzít smysluplnější název, jako je výpočet metodou vektorových prostorů, lineární výpočetní prostory, lineární algebraické výpočty nebo dokonce lineární výpočty apod., S náležitým respektem k matematikovi.)

Kvantová mechanika se snaží popsat jevy, které nelze vysvětlit klasickou fyzikou - pohyb částic, který se vzpírá jakémukoli intuitivnímu vysvětlení. Přesto byly v kvantové mechanice vyvinuty matematické metody, ze kterých lze dělat smysluplné předpovědi. Pomocí podobných (nebo paralelních) matematických metod je možné přijít s výpočetními algoritmy s hlubokými schopnostmi, jako je ten, který najde celočíselná faktorizace (který je základem Šifrování RSA ) podstatně rychlejší než klasické. Jelikož však nevíme, jak přesně příroda ovlivňuje kvantové jevy, zůstává dodnes neznámé, jak přesně by tyto algoritmy mohly být fyzicky implementovány. Kvantový počítač tedy dnes není realitou.

Bez ohledu na to, zda existuje kvantový počítač, či nikoli, toto odvětví aplikované matematiky známé jako kvantové výpočty pokračuje ve studiu vývoje algoritmů paralelně s matematickými metodami používanými v kvantové mechanice.

Studium kvantové výpočetní techniky je dílčím polem kvantová informační věda.

Kvantové výpočty začaly počátkem 80. let, kdy byl fyzik Paul Benioff navrhl a kvantově mechanické model Turingův stroj.^[2] Richard Feynman aYuri Manin později navrhl, že kvantový počítač měl potenciál simulovat věci, které a klasický počítač nemohl.^[3][4] V roce 1994 Peter Shor vyvinuli kvantum algoritmus pro factoringová celá čísla který měl potenciál dešifrovat RSA -šifrovaná komunikace.^[5] Přes pokračující experimentální pokrok od konce 90. let se většina vědců domnívá, že „tolerantní k chybám kvantové výpočty [jsou] stále dost vzdáleným snem. “^[6] V posledních letech vzrostly investice do výzkumu kvantové výpočetní techniky ve veřejném i soukromém sektoru.^[7][8] Dne 23. října 2019, Google AI, ve spolupráci s americkým Národním úřadem pro letectví a vesmír (NASA ), tvrdil, že provedl kvantový výpočet, který je nemožné na jakémkoli klasickém počítači.^[9]

Existuje několik modelů kvantových počítačů (nebo spíše kvantových výpočetních systémů), včetně model kvantového obvodu, kvantový Turingův stroj, adiabatický kvantový počítač, jednosměrný kvantový počítač a různé kvantové celulární automaty. Nejpoužívanějším modelem je kvantový obvod. Kvantové obvody jsou založeny na kvantovém bitu, nebo "qubit ", což je poněkud analogické s bit v klasickém výpočtu. Qubits mohou být v 1 nebo 0 kvantový stav nebo mohou být v superpozice stavů 1 a 0. Když se však měří qubits, výsledkem měření je vždy buď 0 nebo 1; the pravděpodobnosti z těchto dvou výsledků závisí na kvantový stav že qubits byli v bezprostředně před měřením.

Například existují různé přístupy k implementaci kvantových počítačů kvantová simulace, kvantové žíhání a adiabatický kvantový výpočet. Technologie jako transmons, iontové pasti a topologické kvantové počítače použití kvantové logické brány pro jejich výpočty. Všechny tyto přístupy používají qubits.^[1]:2–13 V současné době existuje řada významných překážek ve způsobu konstrukce užitečných kvantových počítačů. Zejména je obtížné udržovat kvantové stavy qubitů, kterými trpí kvantová dekoherence a věrnost státu. Kvantové počítače proto vyžadují oprava chyb.^[10][11]

Žádný výpočetní problém které lze vyřešit klasickým počítačem, lze také vyřešit kvantovým počítačem. Naopak, kvantové počítače se řídí Církev – Turingova teze; to znamená, že jakýkoli problém, který lze vyřešit kvantovým počítačem, lze vyřešit také klasickým počítačem, alespoň v zásadě s dostatečným časem. I když to znamená, že kvantové počítače neposkytují oproti klasickým počítačům žádné další výhody vypočítatelnost, umožňují návrh algoritmů pro určité problémy, které mají výrazně nižší úroveň časové složitosti než známé klasické algoritmy. Je pozoruhodné, že kvantové počítače jsou schopny rychle vyřešit určité problémy, které žádný klasický počítač nedokázal vyřešit v jakémkoli proveditelném čase—Výkon známý jako „kvantová nadvláda "Studie výpočetní složitost problémů týkajících se kvantových počítačů je známá jako teorie kvantové složitosti.

Kvantové operace

Převládající model kvantového výpočtu popisuje výpočet z hlediska sítě kvantové logické brány.^[12]

Paměť skládající se z ${extstyle n}$ kousky informace mají ${extstyle 2 ^ {n}}$ možné stavy. Vektor představující všechny stavy paměti tedy má ${extstyle 2 ^ {n}}$ položky (jeden pro každý stát). Tento vektor je považován za a vektor pravděpodobnosti a představuje skutečnost, že paměť se nachází v určitém stavu.

V klasickém pohledu by jedna položka měla hodnotu 1 (tj. 100% pravděpodobnost, že bude v tomto stavu) a všechny ostatní položky by byly nulové. V kvantové mechanice jsou pravděpodobnostní vektory zobecněny na operátory hustoty. To je technicky přísné matematický základ pro kvantové logické brány, ale přechodný kvantový stavový vektorový formalismus se obvykle zavádí jako první, protože je koncepčně jednodušší. Tento článek se zaměřuje na formalismus vektorového kvantového stavu pro jednoduchost.

Začneme uvažováním o jednoduché paměti skládající se pouze z jednoho bitu. Tuto paměť lze najít v jednom ze dvou stavů: nulový stav nebo jeden stav. Můžeme představovat stav této paměti pomocí Diracova notace aby

Kvantovou paměť lze poté nalézt v jakékoli kvantové superpozici ${extstyle | psi úhel}$ dvou klasických států ${extstyle | 0angle}$ a ${extstyle | 1angle}$:Obecně platí, že koeficienty ${extstyle alfa}$ a ${extstyle eta}$ jsou komplexní čísla. V tomto scénáři jeden qubit informace se říká, že jsou zakódovány do kvantové paměti. Stát ${extstyle | psi úhel}$ není sám o sobě vektorem pravděpodobnosti, ale může být spojen s vektorem pravděpodobnosti prostřednictvím operace měření. Pokud se měří kvantová paměť, aby se zjistilo, zda je stav ${extstyle | 0angle}$ nebo ${extstyle | 1angle}$ (toto se nazývá výpočetní bázové měření), bude nulový stav pozorován s pravděpodobností ${extstyle | alfa | ^ {2}}$ a jeden stát s pravděpodobností ${extstyle | eta | ^ {2}}$. Čísla ${extstyle alfa}$ a ${extstyle eta}$ jsou nazývány kvantové amplitudy.

Stav této qubitové kvantové paměti lze manipulovat aplikací kvantové logické brány, analogicky s tím, jak lze manipulovat s klasickou pamětí klasické logické brány. Jednou důležitou branou pro klasický i kvantový výpočet je brána NOT, kterou lze reprezentovat a matice

Matematicky je modelována aplikace takové logické brány na vektor kvantového stavu násobení matic. Tím pádem ${extstyle X | 0angle = | 1angle}$ a ${extstyle X | 1angle = | 0angle}$.

Matematiku bran s jedním qubitem lze rozšířit tak, aby fungovala na vícequbitových kvantových pamětí dvěma důležitými způsoby. Jedním ze způsobů je jednoduše vybrat qubit a použít tuto bránu na cílový qubit, přičemž zbývající část paměti zůstane nedotčena. Dalším způsobem je použít bránu na její cíl pouze v případě, že je jiná část paměti v požadovaném stavu. Tyto dvě možnosti lze ilustrovat na jiném příkladu. Možné stavy dvoubitové kvantové paměti jsou

Bránu CNOT lze poté reprezentovat pomocí následující matice:Jako matematický důsledek této definice ${extstyle CNOT | 00angle = | 00angle}$, ${extstyle CNOT | 01angle = | 01angle}$, ${extstyle CNOT | 10angle = | 11angle}$, a ${extstyle CNOT | 11angle = | 10angle}$. Jinými slovy, CNOT použije bránu NOT (${extstyle X}$ from before) to the second qubit if and only if the first qubit is in the state ${extstyle | 1angle}$. Pokud je první qubit ${extstyle | 0angle}$, ani jednomu qubitu se nic nedělá.

Stručně řečeno, kvantový výpočet lze popsat jako síť kvantových logických bran a měření. Jakékoli měření lze odložit na konec kvantového výpočtu, i když toto odložení může mít výpočetní cenu. Z důvodu této možnosti odložit měření, většina kvantové obvody znázorňují síť skládající se pouze z kvantových logických bran a bez měření. Více informací naleznete v následujících článcích: univerzální kvantový počítač, Shorův algoritmus, Groverův algoritmus, Algoritmus Deutsch – Jozsa, amplitudová amplifikace, kvantová Fourierova transformace, kvantová brána, kvantový adiabatický algoritmus a kvantová korekce chyb.

Jakýkoli kvantový výpočet lze reprezentovat jako síť kvantových logických bran z poměrně malé rodiny bran. Výběr rodiny bran, která umožňuje tuto konstrukci, je znám jako sada univerzálních bran. Jedna běžná taková sada zahrnuje všechny brány single-qubit i bránu CNOT shora. To znamená, že jakýkoli kvantový výpočet lze provést provedením sekvence bran s jedním qubitem společně s branami CNOT. Ačkoli je tato brána nekonečná, lze ji nahradit sadou konečných bran odvoláním na Solovay-Kitaevova věta. Reprezentaci více qubitů lze zobrazit jako Qsphere.

Potenciální aplikace

Kryptografie

Faktorizace celého čísla, která podporuje bezpečnost kryptografický veřejný klíč systémy, je považován za výpočetně neproveditelný s běžným počítačem pro velká celá čísla, pokud jsou produktem několika prvočísla (např. produkty dvou 300místných prvočísel).^[13] Pro srovnání by kvantový počítač mohl tento problém efektivně vyřešit pomocí Shorův algoritmus najít jeho faktory. Tato schopnost by umožnila kvantovému počítači rozbít mnoho z kryptografické dnes používané systémy v tom smyslu, že by existovalo polynomiální čas (v počtu číslic celého čísla) algoritmus pro řešení úlohy. Zejména většina z populárních šifry veřejného klíče jsou založeny na obtížnosti faktoringu celých čísel nebo diskrétní logaritmus problém, který lze vyřešit Shorovým algoritmem. Zejména RSA, Diffie – Hellman, a eliptická křivka Diffie – Hellman algoritmy by mohly být porušeny. Používají se k ochraně zabezpečených webových stránek, šifrovaného e-mailu a mnoha dalších typů dat. Jejich porušení by mělo značné důsledky pro elektronické soukromí a bezpečnost.

Nicméně, další kryptografické algoritmy nezdá se, že by byly těmito algoritmy porušeny.^[14][15] Některé algoritmy veřejného klíče jsou založeny na jiných problémech než je celočíselná faktorizace a problémech diskrétního logaritmu, na které se vztahuje Shorův algoritmus, například Kryptosystém McEliece na základě problému v teorie kódování.^[14][16] Mřížové kryptosystémy není také známo, že by byly přerušeny kvantovými počítači, a hledání polynomiálního časového algoritmu pro řešení vzepětí skrytý problém s podskupinou, který by rozbil mnoho kryptosystémů založených na mřížce, je dobře prostudovaný otevřený problém.^[17] Bylo prokázáno, že použití Groverova algoritmu k rozbití a symetrický (tajný klíč) algoritmus hrubou silou vyžaduje čas rovný zhruba 2^{n / 2} vyvolání základního kryptografického algoritmu ve srovnání s přibližně 2ⁿ v klasickém případě,^[18] což znamená, že délky symetrických klíčů jsou účinně sníženy na polovinu: AES-256 by měl stejné zabezpečení proti útoku pomocí Groverova algoritmu, který má AES-128 proti klasickému vyhledávání hrubou silou (viz Velikost klíče ).

Kvantová kryptografie může potenciálně plnit některé funkce kryptografie veřejného klíče. Kvantové kryptografické systémy by proto mohly být proti kvantovému hackování bezpečnější než tradiční systémy.^[19]

Kvantové vyhledávání

Kromě faktorizace a diskrétních logaritmů byly pro několik problémů nalezeny kvantové algoritmy nabízející více než polynomiální zrychlení oproti nejznámějšímu klasickému algoritmu,^[20] včetně simulace kvantových fyzikálních procesů z chemie a fyziky pevných látek, aproximace Jonesovy polynomy a řešení Pellova rovnice. Nebyl nalezen žádný matematický důkaz, který ukazuje, že nelze najít stejně rychlý klasický algoritmus, i když je to považováno za nepravděpodobné.^[21] Kvantové počítače však pro některé problémy nabízejí zrychlení polynomů. Nejznámějším příkladem toho je vyhledávání kvantové databáze, které lze vyřešit pomocí Groverův algoritmus pomocí kvadraticky méně dotazů do databáze, než kolik je vyžadováno klasickými algoritmy. V tomto případě je výhoda nejen prokazatelná, ale také optimální, bylo prokázáno, že Groverův algoritmus poskytuje maximální možnou pravděpodobnost nalezení požadovaného prvku pro libovolný počet vyhledávacích dotazů Oracle. Následně bylo objeveno několik dalších příkladů prokazatelného kvantového zrychlení problémů s dotazy, například hledání kolizí ve funkcích dva na jednoho a vyhodnocení stromů NAND.^{[Citace je zapotřebí ]}

Problémy, se kterými se lze vypořádat Groverův algoritmus mají následující vlastnosti:^{[Citace je zapotřebí ]}

1. Ve sbírce možných odpovědí není prohledávatelná struktura,
2. Počet možných odpovědí na kontrolu je stejný jako počet vstupů do algoritmu a
3. Existuje booleovská funkce, která hodnotí každý vstup a určuje, zda se jedná o správnou odpověď

U problémů se všemi těmito vlastnostmi je doba běhu Groverův algoritmus na kvantovém počítači bude měřítko jako druhá odmocnina počtu vstupů (nebo prvků v databázi), na rozdíl od lineárního škálování klasických algoritmů. Obecná třída problémů Groverův algoritmus lze použít^[22] je Booleovský problém uspokojivosti. V tomto případě databáze iterací algoritmu je algoritmus všech možných odpovědí. Příkladem (a možným) uplatněním tohoto je a cracker hesel který se pokouší uhodnout heslo nebo tajný klíč pro šifrované soubor nebo systém. Symetrické šifry jako Triple DES a AES jsou obzvláště zranitelní vůči tomuto druhu útoku.^{[Citace je zapotřebí ]} Tato aplikace kvantového výpočtu je hlavním zájmem vládních agentur.^[23]

Kvantová simulace

Protože chemie a nanotechnologie se spoléhají na porozumění kvantovým systémům a tyto systémy nelze klasicky efektivně simulovat, mnozí věří kvantová simulace bude jednou z nejdůležitějších aplikací kvantové práce na počítači.^[24] Kvantovou simulaci lze také použít k simulaci chování atomů a částic za neobvyklých podmínek, jako jsou reakce uvnitř a urychlovač.^[25]

Kvantové žíhání a adiabatická optimalizace

Kvantové žíhání nebo Adiabatický kvantový výpočet při provádění výpočtů se spoléhá na adiabatickou větu. Systém je umístěn v základním stavu pro jednoduchý Hamiltonian, který se pomalu vyvinul do komplikovanějšího Hamiltonian, jehož základní stav představuje řešení daného problému. Adiabatická věta uvádí, že pokud je evoluce dostatečně pomalá, systém během procesu zůstane vždy v základním stavu.

Řešení lineárních rovnic

The Kvantový algoritmus pro lineární systémy rovnic „Algoritmus HHL“, pojmenovaný po objevitelích Harrowovi, Hassidimovi a Lloydovi, by měl zajistit zrychlení oproti klasickým protějškům.^[26]

Kvantová nadvláda

John Preskill zavedl termín kvantová nadvláda odkazovat na hypotetickou výhodu zrychlení, kterou by měl kvantový počítač nad klasickým počítačem v určitém poli.^[27] Google v roce 2017 oznámila, že očekává dosažení kvantové nadvlády do konce roku, ačkoli se tak nestalo. IBM v roce 2018 uvedl, že nejlepší klasické počítače budou poraženy při praktickém úkolu zhruba do pěti let a zkoušku kvantové nadřazenosti považuje pouze za potenciální budoucí měřítko.^[28] Ačkoli skeptici mají rádi Gil Kalai pochybuji, že bude někdy dosaženo kvantové nadvlády,^[29][30] v říjnu 2019, a Procesor Sycamore vytvořený ve spolupráci s Google AI Quantum údajně dosáhl kvantové nadvlády,^[31] s výpočty více než 3 000 000krát rychlejšími než výpočty z Summit, obecně považován za nejrychlejší počítač na světě.^[32] Bill Unruh v článku publikovaném v roce 1994 pochyboval o praktičnosti kvantových počítačů.^[33] Paul Davies tvrdil, že 400kbitový počítač by se dokonce dostal do konfliktu s kosmologickými informacemi vázanými implicitně holografický princip.^[34]

Překážky

Při stavbě velkého kvantového počítače existuje řada technických výzev.^[35] Fyzik David DiVincenzo uvedl následující požadavky pro praktický kvantový počítač:^[36]

• Fyzicky škálovatelné, aby se zvýšil počet qubitů
• Qubits, které lze inicializovat na libovolné hodnoty
• Kvantové brány, které jsou rychlejší než dekoherence čas
• Sada univerzálních bran
• Qubits, které lze snadno číst

Sourcing dílů pro kvantové počítače je také velmi obtížný. Mnoho kvantových počítačů, jako ty, které postavil Google a IBM potřeba Hélium-3, a jaderný vedlejší produkt výzkumu a speciální supravodivé kabely, které vyrábí pouze japonská společnost Coax Co.^[37]

Řízení vícebitových systémů vyžaduje generování a koordinaci velkého počtu elektrických signálů s těsným a deterministickým časovacím rozlišením. To vedlo k rozvoji kvantové regulátory které umožňují propojení qubitu. Škálování těchto systémů na podporu rostoucího počtu qubitů je další výzvou při škálování kvantových počítačů.^{[Citace je zapotřebí ]}

Kvantová dekoherence

Jednou z největších výzev při konstrukci kvantových počítačů je ovládání nebo odstraňování kvantová dekoherence. To obvykle znamená izolovat systém od jeho prostředí, protože interakce s vnějším světem způsobují jeho dekódování. Existují však i jiné zdroje dekoherence. Jako příklady lze uvést kvantové brány a mřížkové vibrace a termonukleární rotaci pozadí fyzického systému použitého k implementaci qubits. Dekoherence je nevratná, protože je ve skutečnosti nejednotná a je obvykle něčím, co by mělo být vysoce kontrolováno, pokud se mu nezabrání. Doby dekoherence zejména pro kandidátské systémy, příčná relaxační doba T₂ (pro NMR a MRI technologie, nazývaná také dešifrovací čas), obvykle se pohybují mezi nanosekundami a sekundami při nízké teplotě.^[38] V současné době některé kvantové počítače vyžadují, aby jejich qubity byly ochlazeny na 20 milikelvinů, aby se zabránilo významné dekoherenci.^[39] Studie z roku 2020 to tvrdí ionizující radiace jako kosmické paprsky může přesto způsobit dekódování určitých systémů během milisekund.^[40]

Výsledkem může být, že časově náročné úkoly způsobí nefunkčnost některých kvantových algoritmů, protože udržování stavu qubitů po dostatečně dlouhou dobu nakonec superpozice poškodí.^[41]

Tyto problémy jsou pro optické přístupy obtížnější, protože časové rámce jsou o řádově kratší a často citovaný přístup k jejich překonání je optický tvarování pulzu. Míry chyb jsou obvykle úměrné poměru provozní doby k době oddělování, a proto musí být jakákoli operace dokončena mnohem rychleji než doba oddělování.

Jak je popsáno v Věta o kvantové prahové hodnotě, 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 zavede. Často citovaný údaj pro požadovanou chybovost v každé bráně pro výpočet odolný proti chybám je 10⁻³, za předpokladu, že hluk 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 výrazně zvýšený počet požadovaných qubitů. Počet potřebný k výpočtu celých čísel pomocí Shorova algoritmu je stále polynomický a předpokládá se, že je mezi L a L², kde L je počet qubitů v počtu, který má být započítán; Algoritmy pro opravu chyb by tento údaj nafoukly o další faktor L. Pro 1000bitové číslo z toho vyplývá potřeba asi 10⁴ bity bez opravy chyb.^[42] S opravou chyb by se číslo zvýšilo na přibližně 10⁷ bity. Čas výpočtu je asi L² nebo asi 10⁷ kroky a při 1 MHz asi 10 sekund.

Velmi odlišným přístupem k problému stability a oddělování je vytvoření a topologický kvantový počítač s kdokoli, kvazi-částice používá se jako vlákna a spoléhá se na teorie opletení k vytvoření stabilních logických bran.^[43][44]

Fyzik Michail Dyakonov vyjádřil skepsi kvantového výpočtu takto:

„Takže počet spojitých parametrů popisujících stav tak užitečného kvantového počítače v daném okamžiku musí být ... asi 10³⁰⁰... Mohli bychom se někdy naučit ovládat více než 10?³⁰⁰ spojitě proměnné parametry definující kvantový stav takového systému? Moje odpověď je jednoduchá. Ne, nikdy."^[45][46]

Vývoj

Kvantové výpočetní modely

Existuje celá řada kvantových výpočetních modelů, které se vyznačují základními prvky, ve kterých je výpočet rozložen. Čtyři hlavní modely praktického významu jsou:

• Kvantové hradlové pole (výpočet se rozložil na posloupnost několika qubitů kvantové brány )
• Jednosměrný kvantový počítač (výpočet rozložený na posloupnost jednokbitových měření aplikovaných na vysoce zapletený počáteční stav nebo stav klastru )
• Adiabatický kvantový počítač, na základě kvantové žíhání (výpočet se rozložil na pomalou kontinuální transformaci iniciály Hamiltonian do finálního Hamiltonianu, jehož základní stavy obsahují řešení)^[47]
• Topologický kvantový počítač^[48] (výpočet se rozložil na opletení kdokoli ve 2D mřížce)

The kvantový Turingův stroj je teoreticky důležitá, ale fyzická implementace tohoto modelu není proveditelná. Ukázalo se, že všechny čtyři modely výpočtu jsou rovnocenné; každý může simulovat druhého s více než polynomiální režií.

Fyzické realizace

Pro fyzickou implementaci kvantového počítače je sledováno mnoho různých kandidátů, mezi nimi (odlišených fyzickým systémem použitým k realizaci qubits):

• Supravodivé kvantové výpočty^[49][50] (qubit realizovaný stavem malých supravodivých obvodů (Josephson křižovatky )
• Zachycený iontový kvantový počítač (qubit implementovaný vnitřním stavem zachycených iontů)
• Neutrální atomy v Optické mřížky (qubit implementovaný vnitřními stavy neutrálních atomů zachycených v optické mřížce)^[51][52]
• Kvantová tečka počítač, spin-based (např Kvantový počítač Loss-DiVincenzo^[53]) (qubit daný stavem rotace zachycených elektronů)
• Počítač s kvantovou tečkou, prostorový (qubit daný polohou elektronu ve dvojité kvantové tečce)^[54]
• Kvantové výpočty využívající upravené kvantové jámy, které by v zásadě mohly umožnit konstrukci kvantových počítačů pracujících při pokojové teplotě^[55][56]
• Spojený Kvantový drát (qubit implementovaný dvojicí Quantum Wires spojených s a Kontakt kvantového bodu )^[57][58][59]
• Kvantový počítač s nukleární magnetickou rezonancí (NMRQC) implementován s nukleární magnetická rezonance molekul v roztoku, kde qubits poskytuje jaderné zatočení uvnitř rozpuštěné molekuly a sondovány rádiovými vlnami
• NMR v pevné fázi Kane kvantové počítače (qubit realizovaný stavem jaderného spinu v fosfor dárci v křemík )
• Elektrony nahélium kvantové počítače (qubit je elektronová rotace)
• Dutinová kvantová elektrodynamika (CQED) (qubit poskytovaný vnitřním stavem zachycených atomů spojených s vysoce jemnými dutinami)
• Molekulární magnet^[60] (qubit daný stavy rotace)
• Fulleren -na základě ESR kvantový počítač (qubit na základě elektronického spinu o atomy nebo molekuly uzavřené ve fullerenech )^[61]
• Nelineární optický kvantový počítač (qubits realizované zpracováním stavů různých režimy světla skrz lineární i nelineární elementy)^[62][63]
• Lineární optický kvantový počítač (qubits realizované zpracováním stavů různých režimy světla přes lineární prvky, např. zrcadla, rozdělovače paprsků a fázové měniče )^[64]
• Kvantový počítač založený na diamantech^[65][66][67] (qubit realizovaný elektronickou nebo jadernou rotací centra pro uvolňování dusíku v diamantu)
• Bose-Einsteinův kondenzát - kvantový počítač na bázi^[68]
• Tranzistorový kvantový počítač - řetězec kvantových počítačů s unášením kladných děr pomocí elektrostatické pasti
• Kvantové počítače na bázi anorganických krystalů dopované vzácnými zeminami kovy ionty^[69][70] (qubit realizovaný interním elektronickým stavem dopující látky v optická vlákna )
• Kovové podobné uhlíkové nanosféry založené na kvantových počítačích^[71]

Velký počet kandidátů ukazuje, že kvantový výpočet je navzdory rychlému pokroku stále v plenkách.^{[Citace je zapotřebí ]}

Vztah k vypočítatelnosti a teorii složitosti

Teorie vypočítatelnosti

Žádný výpočetní problém řešitelný klasickým počítačem je řešitelný také kvantovým počítačem.^[72] Intuitivně je to proto, že se věří, že všechny fyzikální jevy, včetně provozu klasických počítačů, lze popsat pomocí kvantová mechanika, který je základem činnosti kvantových počítačů.

Naopak jakýkoli problém řešitelný kvantovým počítačem je řešitelný také klasickým počítačem; nebo více formálně, jakýkoli kvantový počítač lze simulovat pomocí a Turingův stroj. Jinými slovy, kvantové počítače neposkytují v porovnání s klasickými počítači žádnou další energii vypočítatelnost. To znamená, že kvantové počítače nemohou vyřešit nerozhodnutelné problémy jako zastavení problému a existence kvantových počítačů nevyvrací Církev – Turingova teze.^[73]

Kvantové počítače dosud nesplňují silná církevní teze. Zatímco hypotetické stroje byly realizovány, univerzální kvantový počítač ještě musí být fyzicky sestaven. Silná verze teze Církve vyžaduje fyzický počítač, a proto neexistuje kvantový počítač, který by přesto splňoval silnou tezi Církve.

Teorie kvantové složitosti

Zatímco kvantové počítače nemohou vyřešit žádné problémy, které již klasické počítače nemohou vyřešit, existuje podezření, že mohou vyřešit mnoho problémů rychleji než klasické počítače. Například je známo, že kvantové počítače mohou efektivně celá čísla faktoru, i když to není považováno za případ klasických počítačů. Schopnost kvantových počítačů zrychlovat klasické algoritmy má však přísné horní hranice a drtivou většinu klasických výpočtů nelze pomocí kvantových počítačů urychlit.^[74]

Třída problémy který lze efektivně vyřešit kvantovým počítačem s omezenou chybou BQP, pro „omezenou chybu, kvantum, polynomiální čas“. Formálněji je BQP třída problémů, které lze vyřešit polynomiálním časem kvantový Turingův stroj s pravděpodobností chyby nejvýše 1/3. Jako třída pravděpodobnostních problémů je BQP kvantovým protějškem BPP ("ohraničená chyba, pravděpodobnostní, polynomiální čas"), třída problémů, které lze vyřešit polynomiálním časem pravděpodobnostní Turingovy stroje s omezenou chybou.^[75] Je známo, že BPP${displaystyle subseteq}$BQP a existuje široké podezření, že BQP${displaystyle subseteq}$BPP, což by intuitivně znamenalo, že kvantové počítače jsou z hlediska časové složitosti výkonnější než klasické počítače.^[76]

Přesný vztah BQP k P, NP, a PSPACE není známo. Je však známo, že P${displaystyle subseteq}$BQP${displaystyle subseteq}$PSPACE; to znamená, že všechny problémy, které lze efektivně vyřešit pomocí deterministického klasického počítače, lze také efektivně vyřešit pomocí kvantového počítače a všechny problémy, které lze efektivně vyřešit pomocí kvantového počítače, lze také vyřešit pomocí deterministického klasického počítače s prostředky polynomiálního prostoru . Dále se předpokládá, že BQP je přísná nadmnožina P, což znamená, že existují problémy, které jsou efektivně řešitelné kvantovými počítači, které nejsou efektivně řešitelné deterministickými klasickými počítači. Například, celočíselná faktorizace a problém diskrétního logaritmu je známo, že jsou v BQP a existuje podezření, že jsou mimo P. O vztahu BQP k NP je známo jen málo, kromě toho, že některé problémy NP, o nichž se předpokládá, že nejsou v P, jsou také v BQP (celočíselná faktorizace a problém diskrétního logaritmu jsou například v NP). Je podezření, že NP${displaystyle subseteq}$BQP; to je, to je věřil, že tam jsou účinně kontrolovatelné problémy, které nejsou účinně řešitelné kvantovým počítačem. Přímým důsledkem této víry je také podezření, že BQP je disjunktní ze třídy NP-kompletní problémy (pokud by byl NP-úplný problém v BQP, pak by to vyplývalo z NP-tvrdost že všechny problémy v NP jsou v BQP).^[78]

Vztah BQP k základním klasickým třídám složitosti lze shrnout takto:

${displaystyle {mathsf {Psubseteq BPPsubseteq BQPsubseteq PPsubseteq PSPACE}}}$

Je také známo, že BQP je obsažen ve třídě složitosti #P (nebo přesněji v přidružené třídě rozhodovacích problémů P^#P),^[78] což je podtřída PSPACE.

Spekulovalo se, že další pokrok ve fyzice by mohl vést k ještě rychlejším počítačům. Například se ukázalo, že nelokální skrytá proměnná kvantového počítače vychází z Bohmian mechanika mohl implementovat vyhledávání ${displaystyle N}$-položka databáze maximálně ${displaystyle O ({sqrt [{3}] {N}})}$ kroky, mírné zrychlení Groverův algoritmus, který běží dovnitř ${displaystyle O ({sqrt {N}})}$ kroky. Všimněte si však, že ani jedna metoda hledání neumožňuje kvantovým počítačům vyřešit NP-kompletní problémy v polynomiálním čase.^[79] Teorie kvantová gravitace, jako M-teorie a smyčková kvantová gravitace, může umožňovat stavbu ještě rychlejších počítačů. Definování výpočtu v těchto teoriích je však otevřeným problémem kvůli problém času; to znamená, že v rámci těchto fyzických teorií v současné době neexistuje žádný zřejmý způsob, jak popsat, co pro pozorovatele znamená odeslat vstup do počítače v jednom okamžiku a poté přijmout výstup v pozdějším okamžiku.^[80][81]

Viz také

Reference

Další čtení

Učebnice

• Nielsen, Michael; Chuang, Isaac (2000). Kvantové výpočty a kvantové informace. Cambridge: Cambridge University Press. ISBN  978-0-521-63503-5. OCLC  174527496.
• Mermin, N. David (2007). Quantum Computer Science: An Introduction. Cambridge University Press. ISBN  978-0-521-87658-2.
• Akama, Seiki (2014). Elements of Quantum Computing: History, Theories and Engineering Applications. Springer International Publishing. ISBN  978-3-319-08284-4.
• Benenti, Giuliano (2004). Principles of Quantum Computation and Information Volume 1. New Jersey: World Scientific. ISBN  978-981-238-830-8. OCLC  179950736.
• Stolze, Joachim; Suter, Dieter (2004). Quantum Computing. Wiley-VCH. ISBN  978-3-527-40438-4.
• Wichert, Andreas (2014). Principles of Quantum Artificial Intelligence. World Scientific Publishing Co. ISBN  978-981-4566-74-2.
• Hiroshi, Imai; Masahito, Hayashi (2006). Quantum Computation and Information. Berlín: Springer. ISBN  978-3-540-33132-2.
• Jaeger, Gregg (2006). Quantum Information: An Overview. Berlín: Springer. ISBN  978-0-387-35725-6. OCLC  255569451.

Akademické práce

• Abbot, Derek; Doering, Charles R.; Caves, Carlton M.; Lidar, Daniel M.; Brandt, Howard E.; Hamilton, Alexander R.; Ferry, David K.; Gea-Banacloche, Julio; Bezrukov, Sergey M.; Kish, Laszlo B. (2003). "Dreams versus Reality: Plenary Debate Session on Quantum Computing". Kvantové zpracování informací. 2 (6): 449–472. arXiv:quant-ph/0310130. doi:10.1023/B:QINP.0000042203.24782.9a. hdl:2027.42/45526. S2CID  34885835.
• DiVincenzo, David P. (2000). "The Physical Implementation of Quantum Computation". Fortschritte der Physik. 48 (9–11): 771–783. arXiv:quant-ph/0002077. Bibcode:2000ForPh..48..771D. doi:10.1002/1521-3978(200009)48:9/11<771::AID-PROP771>3.0.CO;2-E.
• Berthiaume, Andre (1997). "Quantum Computation".
• DiVincenzo, David P. (1995). "Quantum Computation". Věda. 270 (5234): 255–261. Bibcode:1995Sci...270..255D. CiteSeerX  10.1.1.242.2165. doi:10.1126/science.270.5234.255. S2CID  220110562. Table 1 lists switching and dephasing times for various systems.
• Feynman, Richard (1982). "Simulating physics with computers". International Journal of Theoretical Physics. 21 (6–7): 467–488. Bibcode:1982IJTP...21..467F. CiteSeerX  10.1.1.45.9310. doi:10.1007/BF02650179. S2CID  124545445.
• Mitchell, Ian (1998). "Computing Power into the 21st Century: Moore's Law and Beyond".
• Simon, Daniel R. (1994). "On the Power of Quantum Computation". Institute of Electrical and Electronic Engineers Computer Society Press.

externí odkazy

• Stanfordská encyklopedie filozofie: "Quantum Computing " by Amit Hagar and Michael E. Cuffaro.
• "Quantum computation, theory of", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Quantum computing for the very curious by Andy Matuschak and Michael Nielsen

Přednášky

• Quantum computing for the determined – 22 video lectures by Michael Nielsen
• Video přednášky podle David Deutsch
• Lectures at the Institut Henri Poincaré (slides and videos)
• Online lecture on An Introduction to Quantum Computing, Edward Gerjuoy (2008)
• Lomonaco, Sam. Four Lectures on Quantum Computing given at Oxford University in July 2006