Úvodní stránka | Tato stránka v originále

Kvantový počítač

kvantový počítač zařízení, které vypočítá používá superpozice kvantových stavů. Malé kvantové počítače nedávno byly postavené a pokrok je pokračující. Mnoho vlády a vojenská těla takový jak NATO financuje univerzity a kvantová počítačová výzkumná centra, vyvinout počítač pro kryptografii a dozor, tj. vojenská výzvědná služba účely.

To je široce podezříval to jestliže rozsáhlé kvantové počítače mohou být stavěny, oni budou schopní vyřešit jisté problémy rychleji než nějaký klasický počítač. Kvantové počítače jsou odlišné od klasických počítačů takový jako DNA počítače a počítače založili na tranzistorech, ačkoli tito používají quantum mechanické účinky jiný než říkají superpozice.

Tabulka s obsahem
1 struktura kvantových počítačů
2 síla kvantových počítačů
3 jak kvantové počítače pracují
4 praktické kvantové počítače
5 kandidátů
6 kvantové práce na počítači ve výpočetní složitosti teorie
7 vidět také

Struktura kvantových počítačů

V kvantové mechanice, to je možné pro částečku být ve dvou místech najednou, nebo ve dvou státech najednou. Tento účinek je často popisoval, jak používá Schrödinger kočku myslel si experiment, který zahrnuje kočku, která je oba živý a mrtvý současně. Tato schopnost být v rozmanitých státech současně je nazývána superpozicí.

Klasický počítač má paměť tvořenou kousků. Každý kousek myslí si jeden jeden nebo nula. Zařízení vypočítá tím, že manipuluje s těmi kousky. Kvantový počítač udržuje soubor qubits. Qubit může držet jeden, nebo nula, nebo superpozice jeden a nulový. Jinými slovy, to může držet oba jeden a nula zároveň. Kvantový počítač vypočítá tím, že manipuluje s těmi qubits.

Kvantový počítač může být uskutečněn používat nějakou malou částečku, která může mít dva státy. Kvantové počítače by mohly být stavěny od atomů, které jsou jak rozrušené tak nerozrušené současně. Oni by mohli být postavení od fotonů světla to být ve dvou místech zároveň. Oni by mohli být postavení od protonů a neutronů, které mají rotaci “nahoru” a “dole” současně.

Mikroskopická molekula může obsahovat mnoho tisíců protonů a neutronů. To by mohlo být používáno jako kvantový počítač s mnoha tisíci qubits.

Síla kvantových počítačů

To může jít velmi obtížně vzít velké číslo a najít všechny jeho primární faktory. Tento factorization celého čísla problém je věřil být obtížný pro obyčejný počítač. Kvantový počítač mohl vyřešit tento problém velmi rychle. Jestliže číslo má n kousky (je n číslice dlouho když zapsaný binární číslice systém), pak kvantový počítač s jen přes 2n qubits mohou shledají jeho faktory. To může také řešit příbuzný problém volal jednotlivý žurnálový problém. Tato schopnost by dovolila kvantový počítač k přerušení mnoho z cryptographic systémů v použití dnes. Zvláště, nejvíce populární kódy veřejného klíče mohly být rychle zlomené, včetně forem RSA, ElGamal a Diffie-Hellman. Tito jsou používáni chránit bezpečné internetové stránky, zašifroval e-mail, a mnoho jiných druhů dat. Rozbíjející se tito by byli významní. Jediný způsob, jak dělat algoritmus jako RSA bezpečný by byl dělat klíči velikost větší než největší kvantový počítač, který může být stavěn. To vypadá pravděpodobné, že to bude vždy být možné stavět klasické počítače, které mají více kousků než množství qubits v největším kvantovém počítači. Jestliže to je pravdivé, pak algoritmy jako RSA mohly být dělány bezpečný.

Jestliže kvantový počítač byl založený na protonech a neutronech v molekule, to by mohlo být příliš malé vidět, ale mohla by celá čísla faktoru s mnoha tisíci kousků. Klasický počítač běžící známé algoritmy mohly také faktor ta celá čísla. Ale dělat to předtím slunce pálí ven, to by muselo být větší než známý vesmír. To by bylo poněkud nevhodné se budovat.

Snad ne jak překvapivě, kvantové počítače mohly také být užitečné pro průběžné simulace kvantové mechaniky. Speedup mohl být spravedlivý jak velký jak pro factoring. Toto mohlo být velkého praktického užitku k mnoha fyzikům.

Tato dramatická výhoda kvantových počítačů je současně známá existovat pro jediný ty tři problémy: factoring, jednotlivý žurnál, a simulace kvantové fyziky. Nicméně, není tam žádný důkaz že výhoda je skutečná: stejně rychlý klasický algoritmus může ještě být objeven (ačkoli toto je zvažováno nepravděpodobný). Je tam jeden jiný problém kde kvantové počítače mají menší, ačkoli významný (kvadratická) výhoda. To je kvantové databázové hledání, a moci být řešen Groverovým algoritmem. V tomto případě výhoda je provable. Toto založí za pochybností, že (ideál) kvantové počítače jsou nadřazené klasickým počítačům.

Předpokládat tam je problém, takový jak nacházet heslo, které dešifruje soubor. Problém má tyto čtyři vlastnosti:

Pro problémy se všemi čtyřmi vlastnostmi, to vezme průměr n/ 2 odhady najít odpověď, jak používá klasický počítač. Čas na kvantový počítač platit toto bude úměrné druhé odmocnině n. To může být velmi velký speedup, redukovat některé problémy od roků k sekundám. To může být zvyklé na útok kódy symmetric takový jako 3DES a AES. Ale to je také snadné bránit se. Jen zdvojnásobit velikost klíče pro kód. Tam jsou také více komplikované metody pro bezpečnou komunikaci, takový jak používat kvantovou kryptografii.

Tam být současně žádné jiné praktické problémy známý kde kvantové počítače dávají velký speedup přes klasické počítače. Výzkum pokračuje a více problémů může přesto se nalézat.

Jak kvantové počítače pracují

Klasický počítač se třemi kousky paměti může jen skladovat tři digitální a nuly. U daného času, to by mohlo obsahovat kousky “101”. Kvantový počítač s 3 qubits může vlastně uložit 16 analogových hodnot, spárovaný k formě 8 komplexní čísla. U daného času, to by mohlo obsahovat toto:

    Státní amplitudová pravděpodobnost
    2+b2)
     000       0.37 + i 0.04      0.14
     001       0.11 + i 0.18      0.04        
     010       0.09 + i 0.31      0.10
     011       0.30 + i 0.30      0.18
     100       0.35 + i 0.43      0.31
     101       0.40 + i 0.01      0.16
     110       0.09 + i 0.12      0.02
     111       0.15 + i 0.16      0.05
Jestliže tam byl n qubits pak tento stůl by měli měl 2n řady. Pro n ve stovkách, to je více řady než tam jsou atomy ve známém vesmíru.

První sloupec ukazuje všechny možné státy pro tři kousky. Klasický počítač může držet jediný těch vzorů v době. Kvantový počítač může být v superpozici všech 8 států zároveň. Druhý sloupec ukazuje “amplitudu” pro každého 8 států. Těchto 8 komplexních čísel je momentka obsahu kvantového počítače u daného času. Během výpočtu, těchto 8 čísel bude se měnit a ovlivňovat se spolu navzájem. V tomto smyslu, 3-qubit kvantový počítač má daleko více paměti než 3-kousl klasický počítač.

Nicméně, není tam žádná cesta k přímo vidět těchto 8 čísel. Když algoritmus je dokončen, jeden měření je děláno. Měření se vrátí jednoduchý 3-kousl řetězec, a vymaže všechny 8 komplexních čísel. Zpětný řetězec je náhodně generován. Třetí sloup stolu dává pravděpodobnost pro každý možný řetězec. V tomto příkladě, tam je 14 % naděje, že zpětný řetězec bude “000”, 4 % šance to bude “001”, a tak dále. Každé komplexní číslo (+ bi) je nazýván amplitudoua každou pravděpodobností (2+b2) je nazýván čtvercovou amplitudou, protože to se rovná | + bi |2. 8 pravděpodobností se sečte k 1.

Typicky, algoritmus pro kvantový počítač bude inicializovat všechna komplexní čísla se rovnat hodnoty tak celá vůle států mají se rovnat pravděpodobnostem. Seznam komplexních čísel může být myšlenka jak 8-vektor elementu. Na každém kroku algoritmu, že vektor je upraven tím, že násobí to maticí. Matice přijde z fyziky skutečného stroje a vůle vždy být invertible a vůle zajistí, že pravděpodobnosti pokračují k součtu k 1.

Pro teplotní sborový stroj, operace je vykonávána tím, že střílí krátký puls radiace u kontejneru molekul. Různé druhy pulsů vyústí v různé matrices. Algoritmus pro kvantový počítač sestává ze kterých pulsů k použití, a v jakém pořádku. Sekvence je obvykle volena tak že všechny pravděpodobnosti budou jít do nuly kromě pro jednoho. Že pravděpodobnost je jeden odpovídající řetězci, který je správná odpověď. Pak, když měření je děláno, ta odpověď je nejvíce pravděpodobně jeden být vrácen. Pro daný algoritmus, operace budou vždy být jako zmlácené přesně stejný objednat. Tam je ne “jestliže pak” sdělení měnit objednávku, protože není tam žádný způsob, jak číst paměť před měřením na konci.

Pro více detaily na sledech operací užitých na různé algoritmy, vidět univerzální kvantový počítač, Shorův algoritmus, Groverův algoritmus, Deutsch-Jozsa algoritmus a kvantová oprava chyb.

Kvantový počítač v nahoře příklad mohl být myšlenka jako černá schránka obsahovat 8 komplexních čísel. Nebo, to mohlo být myšlenka na tolik černých schránek, každý obsahovat 3 kousky, každý v odděleném vesmíru, a každý se ovlivňovat s jiní. 8 komplexních čísel by popisovalo distribuci 3-kousl vzory přes všechny vesmíry. Tyto dva výklady odpovídají Kodaň výkladu a mnoho výkladu světů, příslušně, kvantové mechaniky. Volba výkladu má žádný účinek na matematiku, nebo na chování kvantového počítače. Jedna cesta, to je 8-vektor elementu, který je upraven maticovým násobením.

Praktické kvantové počítače

David DiVincenzo, IBM, sepsal následující požadavky pro praktický kvantový počítač:

Kandidáti

Tam být množství kvantových počítačových kandidátů, mezi ty:

  1. #rquoteNMR na molekulách v řešení“- umístěný
  2. “kvantová tečka na povrchu “- umístěný
  3. #rquotelaser jednat podle zavodňování ionty (v vakuu) “- umístěný
  4. molekulární magnet- umístěný
  5. Chobotnice- umístěný

Kvantová práce na počítači ve výpočetní složitosti teorie

Tato sekce dohlíží co je současně známé matematicky o síle kvantových počítačů. To popisuje známé výsledky od výpočetní teorie složitosti a teorie počítání se zabývat kvantovými počítači.

Třída problémů, které mohou být efektivně platila kvantovými počítači je volán BQP, pro “ohraničená chyba, quantum, polynomial čas”. Kvantové počítače jen provozují algoritmy randomized, tak BQP na kvantových počítačích je protipól BPP na klasických počítačích. To je definováno jako soubor problémů rozpustitelný s polynomial-algoritmus času, jehož pravděpodobnost chyby je ohraničená pryč od jedné poloviny. Kvantový počítač je řekl, aby “platil” problém jestliže, na každý příklad, jeho odpověď bude správně s vysokou pravděpodobností. Jestliže to řešení běží v polynomial čase, pak ten problém je v BQP.

BQP je podezřelý být disjoint od NP-kompletní a přísný superset P, ale to není známé. Jak factorization celého čísla tak jednotlivý žurnál jsou v BQP. Oba těchto problémů jsou NP problémy podezřelé být venku P. Oba jsou podezřelí nebýt NP-kompletní. Tam je obyčejný misconception že kvantové počítače mohou platit NP-kompletní problémy v polynomial čase. To není známé být pravdivý, a je obecně podezřelý být nepravdivý.

Operátor pro kvantový počítač může být myšlenka jak měnit vektor tím, že násobí to se zvláštní maticí. Násobení maticí je lineární operace. To bylo ukázané to jestliže kvantový počítač mohl být navržený s nelineárními operátory, pak to mohlo platit NP-kompletní problémy v polynomial čase. To mohlo dokonce dělat tak pro # P-kompletní problémy. To není přesto známé zda takový stroj je možný.

Ačkoli kvantové počítače jsou někdy rychlejší než klasické počítače, oni nemohou vyřešit nějaké problémy že klasické počítače nemohou platit, daný dost času a paměť. Turing stroj může simulovat kvantový počítač, tak kvantový počítač mohl nikdy vyřešit undecidable úlohu jako Váhavý problém. Existence kvantových počítačů nevyvrátí Kostel-Turing teze.

Viz též

Bližší informace