Obsah

Zadání

11. Základní metody tvorby kvantových algoritmů a kvantové automaty, resp. kvantová teorie informace

Vypracování

Základy

  1. Kvantové spracovanie informacie je založené na kvantových vlastnostiach častíc ako fotóny, elektróny, atómy
  2. Základný experiment ilustrujúci paradaxy kvantového sveta - dvojštrbinový experiment: http://en.wikipedia.org/wiki/Double-slit_experiment → častice „sa možu vyskytovať vo viacerých stavoch (poloha častice) naraz“, častice majú aj vlnový charakter - wave-particle duality, stav častice je vyjadreny vlnovou funkciou
  3. Meranie stavu kvantovej častice spôsobuje kolaps vlnovej funckie, t.j. zmeriame jeden konkretny stav (polohu, polarizaciu, …) s pravdepodobnosťou, ktorá je vyjadrená vlnovou funkciou, teda kvantový stav častice je definovaný ako distribúcia pravdepodobností (konkrétne odmocniny pravdepodobností, pozri ďalej) nad stavmi v akých sa častica môže nachádzať po meraní
  4. Kvantové počítanie je teda v podstate pravdepodobnostné, využíva kvantového paralelizmu (častica sa nachádza vo viacerých stavoch „naraz“)
  5. Ako „dôsledok“ použitého matematického aparátu, celý výpočet musí byť reverzibilný (funckie, hradlá, procesy)

Kvantové stavy, qubity, zakladne operacie s qubitmi

Kvantový stav je vyjadrený ako stĺpcový vektor v n-rozmernon Hilbertovskom priestore, v pripade qubitu (quantum bit) sa jedná o 2-rozmerný vektor. Na zápis sa používa bra-ket notácia:
ket-vektor: |\phi\rangle  = \begin{pmatrix} 
  \phi_1 \\ 
  \vdots \\ 
  \phi_n 
 \end{pmatrix}

a

bra-vektor: \langle\psi|  = \begin{pmatrix} 
  \psi_1^* & \cdots & \psi_n^* 
 \end{pmatrix}, kde * značí complexne konjungované číslo (zmení sa znamienko komplexnej časti čísla, ak ju má)

Prechod zo stavu do stavu, \phi \rightarrow \psi : \langle\psi|\phi\rangle  = \sum_{i=1}^{n} \phi_i . \psi_i^* a jeho pravdepodobnosť je daná: |\langle\psi|\phi\rangle|^{2}

Dva stavy sú ortogonálne ak \langle\phi|\psi\rangle = 0, takéto dva stavy sú takisto perfektne fyzikálne odlíšitelné, t.j. existuje merianie na základe ktorého vieme jednoznačne povedať v akom stave sa častica nachádzala.

Qubit - je vektor v dvojrozmernom hilbertovskom priestore (H_2)
standardna baza v H_2 - \{|0\rangle, |1\rangle\} = \left\{\begin{pmatrix} 1 \\ 0\end{pmatrix}, \begin{pmatrix} 0 \\ 1\end{pmatrix}\right\} dualna baza v H_2 - \{|0'\rangle, |1'\rangle\} = \left\{\begin{pmatrix} \dfrac{1}{\sqrt{2}} \\  \dfrac{1}{\sqrt{2}}\end{pmatrix}, \begin{pmatrix} \dfrac{1}{\sqrt{2}} \\ -\dfrac{1}{\sqrt{2}}\end{pmatrix}\right\} priklad: kvantovy stav \phi = \alpha|0\rangle + \beta|1\rangle, kde musí byť splnené |\alpha|^2 + |\beta|^2 = 1, je stav, ktorý po meraní zkolabuje do stavu |0\rangle s pravdepodobnostou |\alpha|^2 a do stavu |1\rangle s pravdepodobnostou |\beta|^2 2-qubit register je potom definovany ako kvantovy stav 2 qubitov, t.j. vektor v H_4, |\phi\rangle = a|00\rangle + b|01\rangle + c|10\rangle + d|11\rangle, kde |00\rangle, |01\rangle, |10\rangle, |11\rangle su vektory standartnej baze, t.j. \begin{pmatrix} 1\\ 0\\ 0\\ 0 \end{pmatrix} \cdots \begin{pmatrix} 0\\ 0\\ 0\\1 \end{pmatrix}, n-qubitove regitre su definovane obdobne
Pocitanie na kvantovy bitoch je potom vyjadrene ako nasobenie vektoru vyjadrujuceho kvantovy register unitarnou maticou - pozri https://en.wikipedia.org/wiki/Unitary_matrix. Unitarnost je vyzadovana pretoze zachovava sucet druhych mocnin vektoru rovny jednej.

Zakladne kvantove operacie:

Meranie stavu qubitu(ov) zavisi na baze v akej meriame, napr. ak |0\rangle meriame v dualnej baze dostavame |0'\rangle s pravdepodobnostou 1/2 a |1'\rangle s pravdepodobnostou 1/2, ak meriame v standardnej baze, dostavme |0\rangle s pravdepodobnostou 1. Vseobecne \psi = \alpha|0\rangle + \beta|1\rangle sa v dualnej baze rovna \dfrac{1}{\sqrt{2}}((\alpha + \beta)|0'\rangle +  (\alpha - \beta)|1'\rangle )

Zakladne kvantove algoritmy

  1. quantum one-time pad
  2. quantum teleportation/super dense coding
  3. Deutsch problem
  4. Simon problem
  5. quantove automaty
  6. BB84 a B92
  7. Shorov algoritmus na prvociselny rozklad - dost zlozite, asi staci vediet len ideu

Předměty

Kompletnost

Vypracoval Miroslav Stuhl, 207551. Vypracovanie nie je kompletne, chce to doplnit popis k jednotlivym algoritmom, no uz som to nestihal, kazdopadne dobre vysvetlenie je vzdy na wikipedii. Casom zkusim doplnit aspon k dvom ci trom cosi. Co sa tyka zvysku, snazil som sa to zostrucnit a zjednodusit co najviac, no pre ludi co nemali predmet s prof. Gruskom to asi velmi uzitocne nebude. Ak chcete po mne osvetlit/doplnit nieco viac, napiste.