mgr-szz:in-tei:11-tei

Obsah

Zadání
Vypracování
Předměty
Kompletnost
Diskuze

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: $|\phi\rangle = \begin{pmatrix} \phi_1 \\ \vdots \\ \phi_n \end{pmatrix}$

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:

Hadamarov operator: $H = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ , $H |0\rangle = |0'\rangle$ a takisto aj s $|1\rangle$ a aj opacne.
Pauliho matice: $\sigma_x, \sigma_y, \sigma_z$ , pozri http://en.wikipedia.org/wiki/Pauli_matrices
CNOT alebo teda XOR: $\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{pmatrix}$

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

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

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.