Kvantové počítače

Jeden z prvních podnětů pro zapojení kvantové fyziky do výpočetních procesů pochází od Richarda Feynmana, který si všiml, že při simulaci kvantových systémů na klasickém počítači rostou často nároky na výpočetní čas exponenciálně s délkou vstupu, a položil si otázku, zda by toho nešlo využít obráceně. Tedy zda by cílená evoluce vhodného kvantového systému nemohla být využita k "počítání", což by mohlo vést k podstatnému urychlení běhu některých algoritmů.

Definici kvantového počítače však zavedl až David Deutsch v roce 1985.

Kvantové počítače využívají principu suprpozice a linearity kvantové mechaniky (důležitá je kvantová interference a entanglement). Proto jejich činnost musí být popsána unitárními operátory (z čehož, mj., plyne, že kvantový počítač pracuje vratně).

Pod kvantovým výpočtem se rozumí řízená unitární evoluce speciálně připraveného kvantového systému následovaná měřením.

Abychom pochopili v čem jsou kvantové počítače "lepší" než klasické, musíme se zmínit o teorii výpočtové složitosti:

V teorii složitosti se obecné problémy převádějí na rozhodovací problémy, jejichž výsledkem může být pouze ANO či NE. Pro rozhodovací problémy jsou pak definovány následující třídy: P - pro problémy z této třídy existují algoritmy, jejichž časové nároky rostou (asymptoticky) s délkou vstupu nejvýše polynomiálně. NP - do této třídy patří, zjednodušeně řečeno, problémy, jejichž řešení lze ověřit v polynomiálním čase, máme-li navíc k dispozici vhodnou doplňkovou informaci. Nemusí být ovšem znám žádný algoritmus řešící problém v polynomiálním čase. Zřejmě P Í NP. Nicméně dodnes se nepodařilo dokázat domněnku, že P ą NP.

Je důležité si uvědomit, že informace je fyzikální veličina a že zařazení problému do třídy P může záviset na tom jakou fyzikou se "řídí" počítací stroj (klasický vs. kvantový).

Kvantové počítače umožňují řešit některé problémy, pro něž není známý klasický polynomiální algoritmus, v polynomiálním čase. Není nicméně známo, jestli lze kvantovými počítači řešit v polynomiálním čase každý NP problém. Pravděpodobně nelze.

Poznámky:

• V případě "hustého kvantového kódování" se sice dva bity kódují prostřednictvím manipulace pouze s jednou částicí, nicméně se tím mění celkový stav "kompozitního" systému sestávajícího ze dvou částic (dvou qubitů).
• Všiměte se (v posledním příkladu), že qubity se mohou nacházet v entanglovaném stavu.

Kvantový počítač lze sestavit z kvantových hradel:

Poznámky:

• Operace z příkladů 1 a 2 lze snadno realizovat např. s lineárně polarizovanými fotony pouhým otáčením směru úpolarizace. Dvou-qubitová operace z příkladu 3 vyžaduje interakci mezi dvěma systémy reprezentujícími qubity a její praktická realizace je značně netriviální.
• V r. 1989 Deutsch ukázal, že existuje univerzální 3-qubitové kvantové hradlo (univerzální v tom smyslu, že kombinací takových hradel lze realizovat libovolnou operaci). Dnes se ví, že Deutschovo hradlo není zdaleka jediné univerzálníhradlo.
• V r. 1995 Di Vincenzo dokázal, že Deutschovo hradlo lze realizovat posloupností 2- a 1-qubitových hradel. 

Poznámky:

• Reversibilita vyžaduje pomocné bity, nesoucí informaci nutnou k "obrácení" výpočtu.
• Lze-li hodnotu funkce v daném bodě spočítat (v polynomiálním čase) klasicky, lze to i kvantově.