logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-01262009-095220


Tipo di tesi
Tesi di laurea specialistica
Autore
COSENTINO, ALESSANDRO
URN
etd-01262009-095220
Titolo
On some combinatorial properties of graph states
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
Relatore Bernasconi, Anna
Relatore Severini, Simone
Parole chiave
  • graph states
  • graph theory
  • quantum computing
Data inizio appello
13/02/2009
Consultabilità
Completa
Riassunto
I graph state sono particolari stati quantistici, rappresentabili tramite grafi indiretti semplici,
che giocano un ruolo fondamentale in informatica quantistica,
in particolare nell'ambito dei codici a correzione di errore e nel modello di computazione one-way.
Lo scopo di questa tesi è studiare alcune proprietà dei graph state attraverso un approccio combinatorio.
Innanzitutto si sono analizzate le proprietà di un'invariante dei grafi: il numero di sottografi indotti con numero dispari di archi.
Questo numero è stato valutato per famiglie importanti di grafi ed è stato trovato un algoritmo efficiente per calcolarlo.
Abbiamo inoltre caratterizzato questo numero rispetto all'azione di local complementation.
Alcune proprietà delle funzioni booleane associate ai graph state sono state studiate analizzando
la struttura dei grafi di Cayley delle suddette funzioni.
Infine sono stati definiti, e ne è stata analizzata la struttura, grafi che permettono di tracciare
le trasformazioni di local complementation e switching fra graph state.
Un congettura è stata fatta sulla struttura di questi grafi.
A margine del lavoro, sono state introdotte alcune estensioni alla definizione classica di graph state.
In particolare sono stati definiti gli "edge graph state" e i "3-hypergraph state".
File