Κβαντικοί Υπολογιστές και αλγόριθμος Grover

2013-04-07 01:08

Οι πρόσφατες εξελίξεις με τους Κβαντικούς Υπολογιστές επιβάλλουν να δούμε μια από τις συγκλονιστικότερες διαφορές των Κβαντικών Υπολογιστών με τους σημερινούς κλασικούς.'Οτι για πρώτη φορά στην ανθρώπινη ιστορία θα μπορούμε να ψάχνουμε ένα αντικείμενο μεταξύ

αντικειμένων,χωρίς κατα μέσο όρο να κάνουμε $\frac{n}{2}$ βήματα πριν το βρούμε.Δηλαδή χωρίς πολυπλοκότητα $\mathcal{O}(n)$ όπως λένε στην πληροφορική.Αφού μέχρι τώρα στην ανθρώπινη ιστορία η διαδικασία αναζήτησης ενός αντικειμένου μεταξύ

είναι το δίχως άλλο μια $\mathcal{O}(n)$ διαδικασία,αφού στη χειρότερη περίπτωση μπορεί το ζητούμενο αντικείμενο να βρεθεί τελευταίο.Και λέω στην ανθρώπινη ιστορία διότι το γεγονός αυτό δεν είναι μόνο χαρακτηριστικό των search σε μια βάση δεδομένων ενός κλασικού υπολογιστή.Το ότι και αυτή είναι $\mathcal{O}(n)$ διαδικασία είναι φυσικά απόρροια της κλασικής φύσης της πληροφορίας αυτής και δε διαφέρει σε τίποτα από πλευράς πολυπλοκότητας από το να ψάχνεις π.χ. μεταξύ

κλειστών κουτιών από τα οποία n-1

είναι άδεια να βρείς το ένα που έχει μέσα κάτι.Και αυτο γιατί και τα bits και τα κουτιά είναι κλασικά αντικείμενα.Δεν υπάρχουν εκεί καταστάσεις του τύπου:

$\frac{1}{\sqrt{n}}(|1\quad bit\rangle +|\alpha\lambda\lambda o\quad bit\rangle+\cdots + |\kappa .\tau .\lambda\rangle )$

ή

$\frac{1}{\sqrt{n}}(|1\quad \kappa o \upsilon\tau\iota\rangle +|\alpha\lambda\lambda o\quad \kappa o \upsilon\tau\iota\rangle+\cdots + |\kappa .\tau .\lambda\rangle )$

Αυτή είναι μια σπουδαία διαφορά του να κάνεις υπολογιστική με οντότητες που έχουν κβαντικές ιδιότητες,γιατί εκεί υπάρχουν αυτές οι καταστάσεις και ο αλγόριθμος Grover είναι ακριβώς η πρώτη φορά που ελλατώνεται η πολυπλοκότητα αυτής της διαδικασίας και είναι μια μόνο καινοτομία.Υπάρχουν και άλλες,o αλγόριθμος Simon,ο αλγόριθμος Shor και άλλα.Ουσιαστικά,για να λέμε τα πράγματα με το όνομά τους,οι μεν κλασικοί υπολογιστές υπακούουν στην κλασική πραγματικότητα,οι δε κβαντικοί υπολογιστές στην κβαντική πραγματικότητα,δηλαδή την πραγματική πραγματικότητα της Φύσης και όχι την μακροσκοπική.Αυτή είναι και η βασική διαφορά η οποία βεβαίως είναι κολοσσιαία διαφορά.
Σε αυτήν την πραγματική πραγματικότητα οι υπολογισμοί γίνονται στον λεγόμενο χώρο Hilbert $\mathcal{H}$ που είναι διανυσματικός χώρος και στην περίπτωση ενός απλού κβαντικού bit του qubit είναι ένας μιγαδικός διανυσματικός χώρος δύο διαστάσεων και αν συμβολίσουμε με $\{|0\rangle,|1\rangle\}$ τη βάση αυτού του χώρου τότε μπορούμε να συμβολίσουμε το qubit ως:

$\displaystyle |\phi\rangle=c_0|0\rangle+c_1|1\rangle\in \mathcal{H}$

και βέβαια αυτή είναι η μεγάλη διαφορά.

Λίγα στοιχεία σχετικά με τους Κβαντικούς Υπολογισμούς

Το qubit σε αντίθεση με το κλασικό bit δεν μπορεί να είναι μόνο

αλλά είναι ακριβώς $|\phi\rangle=c_0|0\rangle+c_1|1\rangle$ .Αυτό ακριβώς.Δεν έχει καμία σχέση με την μακροσκοπική/εμπειρική πραγματικότητα αλλά είναι αλήθεια!Αλλά το πλέον ενδιαφέρον είναι ότι ο χώρος Hilbert $\mathcal{H}_n$ για n-qubits είναι ένα τανυστικό γινόμενο των χώρων Hilbert των 1-qubit.Έτσι το τυχόν διάνυσμα του $\mathcal{H}_n$ γράφεται:

$\displaystyle |\Phi\rangle = \sum_{i_1,\cdots,i_n} c_{i_1,\cdots,i_n}|\phi_{i_1}\rangle \otimes |\phi_{i_2}\rangle\otimes\cdots\otimes |\phi_{i_n}\rangle$

και το εσωτερικό γινόμενο δύο τέτοιων διανυσμάτων είναι:

$\displaystyle \langle \Phi|\Psi\rangle=\prod_{i=1}^{n}\langle \phi_i|\psi_i\rangle$

Ο αλγόριθμος αναζήτησης δουλεύει σε έναν υποχώρο m-qubit του n-qubit χώρου Hilbert :

$\displaystyle (\mathcal{H}_n)^m=H_n^{m}=\{|\Phi\rangle=(|\phi_1\rangle,\cdots,|\phi_m\rangle)| |\phi_i\rangle\in\mathcal{H}_n\}$

Εδώ,το εσωτερικό γινόμενο δύο διανυσμάτων αυτού του υποχώρου ορίζεται ως:

$\displaystyle\langle\Phi|\Psi\rangle =\frac{1}{m}\sum_{i=1}^{m}\langle \phi_i|\psi_i\rangle$

Τώρα,τα στοιχεία του χώρου Hilbert τα οποία έχουν norm 1 είναι οι φυσικές καταστάσεις με όρους των οποίων εκτελεί υπολογισμούς ο κβαντικός υπολογιστής.Ο διανυσματικός χώρος αυτών των καταστάσεων είναι:

$\displaystyle (\mathcal{H}_n)_1^m =\{\Phi\in(\mathcal{H}_n^{m}|\langle\Phi,\Phi\rangle =1\}$

Ο αλγόριθμος αναζήτησης Grover

Έστω ότι έχουμε μια σειρά δεδομένων μεγέθους N=2^n

και πως

από αυτά επισημαίνονται από τα σύμβολα $d_1,d_2,\cdots,d_m,d_j\in\{1,2,\cdots,2^n\}$ που είναι διαφορετικά μεταξύ τους.Το σύνολο όλων των δυνατών επιγραφών τω δεδομένων είναι το σύνολο όλων των δυνατών μεταθέσεων m πραγμάτων από 2^n

δηλαδή ${}_{2^n} P_m$ .
Ο σκοπός του αλγορίθμου αναζήτησης είναι να εντοπίσει μια συγκεκριμένη σειρά δεδομένων από τα συνολικά N =2^n

δεδομένα.
Στους κβαντικους υπολογιστές αυτή η συγκεκριμένη σειρά δεδομένων που αναζητούμε και που χαρακτηρίζεται από τα σύμβολα $d_1,d_2,\cdots,d_m,d_j\in\{1,2,\cdots,2^n\}$ μπορεί να περιγραφεί με ένα διάνυσμα που ανήκει στον $(\mathcal{H}_n)_1^m$ .Ένα τέτοιο διάνυσμα μπορεί να παρασταθεί από τον πίνακα:

$\displaystyle W=[e_{d_1},e_{d_2},\cdots,e_{d_m}],\qquad e_j=[0,0,\cdots,\underbrace{1}_\text{j-th},\cdots,0]$

Ποιά είναι η βασική ιδέα τώρα.Ξεκινούμε από μια άλλη κατάσταση του $(\mathcal{H}_n)_1^m$ την εξής:

$\displaystyle A=[a,\cdots,a],\qquad a=\frac{1}{\sqrt{2^n}}[1,\cdots,1]^{\top}$

Αυτή είναι η αφετηρία του αλγορίθμου.Και είναι μια κβαντική υπέρθεση όλων των διανυσμάτων βάσης του $(\mathcal{H}_n)_1^m$ .Με τους πίνακες που χρησιμοποιούμε για καταστάσεις ο παραπάνω ορισμός του εσωτερικού γινομένου στον $(\mathcal{H}_n)_1^m$ γράφεται:

$\displaystyle (\Phi,\Psi)=\frac{1}{m}(tr\Phi^{\top}\Psi),\qquad \Phi,\Psi\in (\mathcal{H}_n)_1^m$

Τώρα,εισάγουμε δύο τελεστές πάνω στον $(\mathcal{H}_n)_1^m$ :

$\displaystyle I_W: (\mathcal{H}_n)_1^m\rightarrow (\mathcal{H}_n)_1^m,\qquad \Phi\rightarrow \Phi-2(W,\Phi) W$

$\displaystyle I_A: (\mathcal{H}_n)_1^m\rightarrow (\mathcal{H}_n)_1^m,\qquad \Phi\rightarrow \Phi-2(A,\Phi) A$

Στη συνέχεια ορίζουμε την κατάσταση:

$\displaystyle R=\sqrt{\frac{2^n}{2^n-1}}A-\frac{1}{\sqrt{2^n-1}}W$

Τα

και

αποτελούν μια ορθοκανονική βάση με $span_\mathbb{C}\{W,A\}=span_\mathbb{C}\{R,W\}$ .Τώρα η βασική ιδέα είναι ο τελεστής Grover: $G=-I_A\circ I_W$ .Αυτός ο τελεστής δρα πάνω στο $span_\mathbb{C}\{R,W\}$ ως στροφή στα διανύσματα βάσης

και

διότι:

$\displaystyle G(W)=(1-\frac{2}{2^n})W-2\sqrt{\frac{1}{2^n}}\sqrt{\frac{2^n-1}{2^n}} R$

και

$\displaystyle G(R)=(1-\frac{2}{2^n}) R+2\sqrt{\frac{1}{2^n}}\sqrt{\frac{2^n-1}{2^n}} W$

όπου αμέσως βλέπουμε πως θέτοντας:

$\displaystyle sin\frac{\theta}{2}=\sqrt{\frac{1}{2^n}},cos\frac{\theta}{2}=\sqrt{\frac{2^n-1}{2^n}}$

τότε η δράση του τελεστή Grover συνοψίζεται στο:

$G\{R,W\}=\{R,W\} \begin{bmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{bmatrix}$

δηλαδή είναι πράγματι μια στροφή αυτών των διανυσμάτων βάσης.

Βλέπουμε τώρα ότι η κατάσταση $A=[a,\cdots,a],\quad a=\frac{1}{\sqrt{2^n}}[1,\cdots,1]^{\top}\in (\mathcal{H}_n)_1^m$ που αποτελεί την αφετηρία του αλγορίθμου και που αποτελεί μια κβαντική υπέρθεση όλων των διανυσμάτων βάσης του $(\mathcal{H}_n)_1^m$ μετά τον ορισμό της κατάστασης

μπορεί να γραφεί ως:

$\displaystyle A=\sqrt{\frac{2^n-1}{2^n}}R+\sqrt{\frac{1}{2^n}} W$

Δηλαδή η αρχική κατάσταση υπέρθεσης όλων των διανυσμάτων βάσης του $(\mathcal{H}_n)_1^m$ ανήκει και στο $span_\mathbb{C}\{R,W\}$ συνεπώς υπόκειται στην δράση του τελεστή στροφής Grover με σκοπό να συμπέσει με την κατάσταση που αναζητούμε,δηλαδή την κατάσταση

.Διότι ασκώντας

διαδοχικές στροφές στην

μέσω του τελεστή Grover πέρνουμε:

$\displaystyle G^{k}(A)=[cos(k+\frac{1}{2})\theta]R+[sin(k+\frac{1}{2})\theta]W$

και φυσικά για $N=2^n >>1\Rightarrow \frac{\theta}{2}\approx \sqrt{\frac{1}{2^n}}$ κατάσταση αυτή είναι κοντά στην ζητούμενη

με πιθανότητα πολύ κοντά στη μονάδα όταν:

$\displaystyle (k+\frac{1}{2})2\sqrt{\frac{1}{2^n}}=\frac{\pi}{2}\Rightarrow k= \frac{\pi}{4}\sqrt{2^n}-\frac{1}{2}$

Δηλαδή πρέπει να εφαρμόσουμε τον τελεστή Grover πάνω στην αρχική κατάσταση $k \approx\sqrt{ 2^n}=\sqrt{N}$ φορές.Είναι δηλαδή για πρώτη φορά στην ιστορία της ανθρωπότητας η αναζήτηση αυτή δεν είναι διαδικασία πολυπλοκότητας $\mathcal{O}(N)$ όπως θα ήταν αν η διαδικασία ήταν κλασική αλλά είναι διαδικασία πολυπλοκότητας $\mathcal{O}(\sqrt{N})$ χάρη στην κβαντική φύση του υπολογισμού που επέτρεψε την εφαρμογή αυτού του κβαντικού αλγορίθμου που είναι μια διαδικασία στροφής πάνω σε ένα κατάλληλο χώρο Hilbert κβαντικών καταστάσεων,κάτι φυσικά που μόνο στην κβαντομηχανική θα μπορούσε να συμβεί.

—————

Πίσω

Θέμα: Κβαντικοί Υπολογιστές και αλγόριθμος Grover

Δεν βρέθηκαν σχόλια.

Προσομοιώσεις Φυσικής

Κβαντικοί Υπολογιστές και αλγόριθμος Grover

Θέμα: Κβαντικοί Υπολογιστές και αλγόριθμος Grover