• graph states
• graph theory
• quantum computing

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".