Kernel Learning Algo on Graph - Quantum Walker

Definizione 

Descrizione 

Un Quantum Walker è l'analogo Quantomeccanico di un Random Walker.

Consideriamo ora il caso di un Discrete Quantum Walker.

Utilizzeremo questo elemento per definire cosa si intende per Passeggiata Quantomeccanica su un Grafo. 

Si immagini un Grafo $ G(V, E) $ in cui ad ogni Vertice corrisponde un Possibile Stato di un generico Sistema Quantomeccanico.

La possibilità di una Transizione Diretta da uno Stato $ v_{i} $ ad uno stato $ v_{j} $ con $ v_{i}, v_{j} \in V $ è descritta dalla $ A $ Matrice di Transizione, in cui un generico elemento è definito nel seguente modo

$$ a_{i,j} = \left\{\begin{matrix}
1 & \text{Se Transizione Diretta Possibile} \\
0 & \text{Altrimenti}
\end{matrix}\right.
$$

Rappresentiamo quindi l'evoluzione temporale del Sistema come la Passeggiata di un Camminatore sul Grafo degli Stati possibili.

Nel caso di un Random Walk le Transizione tra un Nodo e l'altro sono regolate da una Matrice di Transizione di tipo Stocastico mentre
nel caso del Quantum Walk la Matrice di Transizione è di tipo Deterministico.

Questa Quantum Walk Transition Matrix è una Matrice Complessa Unaria ovvero
una Matrice che moltiplicata per la sua Auto-Aggiunta (Matrice Trasposta, i cui elementi sono Complessi Coniugati) fornisce la Matrice Identità

Il Cammino inizia da uno Stato qualsiasi $ u_0 \in V $ sul Grafo e poi evolve nel tempo
e quindi all'istante $ t $ esso sarà dato da una Combinazione Lineare di tutti Vertici del Grafo,
in cui il Coefficiente relativo all’i-esimo Stato indica (attraverso un’operazione di Modulo Quadro) la Probabilità che il Sistema si trovi in quello Stato

$ \left | \psi(t) \right \rangle = \sum_{u \in V} \alpha_{u}(t) \left | u \right \rangle $

Ovviamente all’istante iniziale avremo che

$$ \alpha_{u}(0) = \left\{\begin{matrix}
1 & u = u_0 \\
0 & u \neq u_0
\end{matrix}\right.
$$

Defiamo quindi un Processo Stocastico $ X(t) $ la cui Realizzazione al Tempo $ t $ sia una Variabile Aleatoria che rappresenta la Probabilità che il Quantum Walker si trovi in un determinato Vertice in quell’istante

Conformemente all’Interpretazione Probabilistica della Funzione d’Onda del Quantum Walker da parte della Meccanica Quantistica, tale probabilità sarà data da 

$ P\left ( \left \{ X(t) = u \right \} \right ) = \alpha_{u}(t)^{*} \alpha_{u}(t) = \left | \alpha_{u}(t) \right | $

Naturalmente Coefficienti sono tali da essere Normalizzati e quindi 

$$ \sum_{u \in V} \left | \alpha_{u}(t) \right | = 1 $$ 

Osservazione  Differenza tra Moto Stocastico e Moto Quantistico Si sarà notato che, come per il Moto del Random Walk, anche nel caso del Quantum Walk la Posizione del Quantum Walker è rappresentata da una Processo Stocastico ma la ragione per cui questo è ovviene completamente diversa. Nel caso del Random Walk la Dinamica del Camminatore è intrinsecamente stocastica e questo viene reso dal fatto che la Matrice di Transizione è proprio Stocastica. Nel caso del Quantum Walk la Dinamica del Camminatore è determinata da una Transition Matrix di tipo Deterministico. Essa svolge il ruolo di Hamiltoniana da inserire nella Equazione di Schroedinger che è l’Equazione Fondamentale che determina l'Evoluzione Temporale di un Sistema Quantistico. Questa Equazione è comunque deterministica. La Aleatorietà relativa alla Posizione della Particella in un dato istante deriva direttamente dai Postulati della Meccanica Quantistica ed è di natura diversa da quella del Moto Stocastico. In un moto Stocastico Classico, ad ogni Transizione la Particella evolve in uno solo dei Possibili Stati scegliendo a caso conformemente alla Distribuzione di Probabilità espressa dalla Matrice di Transizione. In un moto Quantomeccanico, ad ogni Transizione la Funzione d'Onda del Camminatore evolve in tutti gli Stati Possibili, sarà poi l'atto di una eventuale misura che farà collassare il Sistema in una delle sue Autofunzioni. Una conseguenza di questo tipo di Dinamiche è che il Moto Stocastico Classico non è Reversibile mentre il Moto Quantomeccanico è Reversibile.

La Dinamica del Quantum Walker è determinata dalla Equazione di Schroedinger utilizzando la $ A $ Matrice di Adiacenza come Hamiltoniana e quindi 

$$ \frac{d}{dt} \left | \psi(t) \right \rangle = - i A \left | \psi(t) \right \rangle $$

Questa è di fatto una ODE la cui Soluzione risulta immediata 

$$ \left | \psi(t) \right \rangle = \exp\left ( - i A t \right ) \left | \psi(t_{0}) \right \rangle $$

Effettuando quindi una Decomposizione Spettrale della Matrice troviamo che 

$$ A = \Phi \Lambda \Phi^{T} $$

Con

• $ \Phi $ Matrice le cui colonne sono gli $ n $ Autovettori di $ A $ 
• $ \Lambda $ Matrice Diagonale i cui elementi sono gli $ n $ Autovaloti di $ A $ 

e quindi

$$ \exp(-i A t) = \Phi \exp(- i \Lambda t) \Phi^{T} $$

e quindi la Soluzione di cui sopra risulta 

$$ \left | \psi(t) \right \rangle = \Phi \exp\left ( - i \Lambda t \right ) \Phi^{T} \left | \psi(t_{0}) \right \rangle $$