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

==== Základy ====
  - Kvantové spracovanie informacie je založené na kvantových vlastnostiach častíc ako fotóny, elektróny, atómy
  - 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
  - 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í
  - Kvantové počítanie je teda v podstate pravdepodobnostné, využíva kvantového paralelizmu (častica sa nachádza vo viacerých stavoch "naraz")
  - 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:** <math> 
|\phi\rangle  = \begin{pmatrix}
  \phi_1 \\
  \vdots \\
  \phi_n
 \end{pmatrix}
</math>

a 

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

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

Dva stavy sú ortogonálne ak <math> \langle\phi|\psi\rangle = 0</math>, 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 (<math> H_2 </math>)
**standardna baza** v <math> H_2 </math> - <math>\{|0\rangle, |1\rangle\}</math> = <math>\left\{\begin{pmatrix} 1 \\ 0\end{pmatrix}, \begin{pmatrix} 0 \\ 1\end{pmatrix}\right\}</math>
**dualna baza** v <math> H_2 </math> - <math>\{|0'\rangle, |1'\rangle\}</math> = <math>\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\}</math>
**priklad**: kvantovy stav <math> \phi = \alpha|0\rangle + \beta|1\rangle</math>, kde musí byť splnené <math> |\alpha|^2 + |\beta|^2 = 1 </math>, je stav, ktorý po meraní zkolabuje do stavu <math>|0\rangle</math> s pravdepodobnostou <math> |\alpha|^2</math> a do stavu <math> |1\rangle </math> s pravdepodobnostou <math>|\beta|^2</math>
**2-qubit register** je potom definovany ako kvantovy stav 2 qubitov, t.j. vektor v <math> H_4 </math>, <math>|\phi\rangle = a|00\rangle + b|01\rangle + c|10\rangle + d|11\rangle</math>, kde <math> |00\rangle, |01\rangle, |10\rangle, |11\rangle </math> su vektory standartnej baze, t.j. <math> \begin{pmatrix} 1\\ 0\\ 0\\ 0 \end{pmatrix} \cdots \begin{pmatrix} 0\\ 0\\ 0\\1 \end{pmatrix}</math>, 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:**
  * Hadamarov operator: <math> H = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} </math>, <math> H |0\rangle = |0'\rangle</math> a takisto aj s <math>  |1\rangle</math> a aj opacne.
  * Pauliho matice: <math> \sigma_x, \sigma_y, \sigma_z</math>, pozri [[http://en.wikipedia.org/wiki/Pauli_matrices]]
  * CNOT alebo teda XOR: <math> \begin{pmatrix} 1 & 0 & 0 & 0\\  0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{pmatrix} </math>

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

==== Zakladne kvantove algoritmy ====

  - quantum one-time pad
  - quantum teleportation/super dense coding
  - Deutsch problem
  - Simon problem
  - quantove automaty
  - BB84 a B92
  - Shorov algoritmus na prvociselny rozklad - dost zlozite, asi staci vediet len ideu

===== Předměty =====
  * [[https://is.muni.cz/auth/predmet/fi/IA066|IA066 Úvod do kvantových algoritmov a počítačov]]

===== 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.

~~DISCUSSION~~