On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory

Colledan, Andrea (2018) On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory. [Laurea], Università di Bologna, Corso di Studio in Informatica [L-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Non opere derivate 3.0 (CC BY-NC-ND 3.0)

Download (474kB)


Quantum computing has opened the way to new algorithms that can efficiently solve problems that have always been deemed intractable. However, since quantum algorithms are hard to design, the necessity to find a generalization of these problems arises. Such necessity is satisfied by the hidden subgroup problem (HSP), an abstract problem of group theory which successfully generalizes a large number of intractable problems. The HSP plays a significant role in quantum complexity theory, as efficient algorithms that solve it can be employed to efficiently solve other valuable problems, such as integer factorization, discrete logarithms, graph isomorphism and many others. In this thesis we give a computational definition of the HSP. We then prove the reducibility of some of the aforementioned problems to the HSP. Lastly, we introduce some essential notions of quantum computing and we present two quantum algorithms that efficiently solve the HSP on Abelian groups.

Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Colledan, Andrea
Relatore della tesi
Corso di studio
Ordinamento Cds
Parole chiave
quantum,quantum computing,hidden subgroup problem,HSP,complexity theory,reducibility,group theory,Simon's problem,discrete logarithm,integer factorization,graph isomorphism,quantum circuits,quantum fourier transform,quantum algorithm,abelian
Data di discussione della Tesi
18 Luglio 2018

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento