ETD system

Electronic theses and dissertations repository

 

Tesi etd-01262009-095220


Thesis type
Tesi di laurea specialistica
Author
COSENTINO, ALESSANDRO
URN
etd-01262009-095220
Title
On some combinatorial properties of graph states
Struttura
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Supervisors
Relatore Bernasconi, Anna
Relatore Severini, Simone
Parole chiave
  • graph states
  • graph theory
  • quantum computing
Data inizio appello
13/02/2009;
Consultabilità
Completa
Riassunto analitico
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