A Taxonomy of Quantum Algorithms - The core ideas of existing quantum algorithms and their implications on cryptography
Examensarbete för masterexamen
Computer systems and networks (MPCSN), MSc
With quantum computers coming up as one of the fastest growing areas in multiple research areas, such as computer science and physics, a taxonomy of the existing quantum algorithms is necessary. However, before this thesis, no taxonomy which included many of the existing quantum algorithms could be found. We have filled that gap with this thesis. The result is a taxonomy with 31 algorithms. Each algorithm are classified into different groups depending on the characteristics and the core idea that the algorithm uses. We have focused on three different core ideas distributed as 33% using the Quantum Fourier Transform, 27% uses Amplitude Amplification and 15% uses Quantum Walks with the remaining 25% being classified as "Other". On top of this, we also discuss the security implications on the cryptographic schemes used today, once quantum computers become reality. A taxonomy about an area that expands as fast as quantum computing is never finished, but we believe that this thesis provides a good base for future work in the area. This thesis can also be used as an introduction to quantum computing for students with a base knowledge about computer science and mathematics.
Data- och informationsvetenskap , Computer and Information Science