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
Commissione
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,<br>che giocano un ruolo fondamentale in informatica quantistica, <br>in particolare nell&#39;ambito dei codici a correzione di errore e nel modello di computazione one-way.<br>Lo scopo di questa tesi è studiare alcune proprietà dei graph state attraverso un approccio combinatorio.<br>Innanzitutto si sono analizzate le proprietà di un&#39;invariante dei grafi: il numero di sottografi indotti con numero dispari di archi.<br>Questo numero è stato valutato per famiglie importanti di grafi ed è stato trovato un algoritmo efficiente per calcolarlo.<br>Abbiamo inoltre caratterizzato questo numero rispetto all&#39;azione di local complementation.<br>Alcune proprietà delle funzioni booleane associate ai graph state sono state studiate analizzando <br>la struttura dei grafi di Cayley delle suddette funzioni.<br>Infine sono stati definiti, e ne è stata analizzata la struttura, grafi che permettono di tracciare <br>le trasformazioni di local complementation e switching fra graph state.<br>Un congettura è stata fatta sulla struttura di questi grafi. <br>A margine del lavoro, sono state introdotte alcune estensioni alla definizione classica di graph state.<br>In particolare sono stati definiti gli &#34;edge graph state&#34; e i &#34;3-hypergraph state&#34;.
File