Quantum Fourier Transform

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-06-11

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

20

Series

Abstract

The fast Fourier transform (FFT), which computes the discrete Fourier transform (DFT), can be thought of as one of the most important numerical algorithms of the 20th century, as it is widely used in many applications. The quantum Fourier transform (QFT) is the quantum analogue of the DFT and like the FFT in classical algorithms, the QFT has many applications in quantum algorithms. The aim of this thesis is to introduce the QFT, derive it from the discrete Fourier transform, and compare the QFT with the classical fast Fourier transform. The thesis also briefly introduces other quantum algorithms that make use of the quantum Fourier transform. The paper focuses on the algorithm on a theoretical quantum computer using the quantum gate model of computation. It does not deal with the practical implementation of the algorithm on a quantum computer. The main research method used is a literature review. In addition, the thesis also proves that the discrete Fourier transform can be implemented using quantum gates. Based on the literature review and the proof, it can be concluded that the QFT is a good tool for studying certain periodic phenomena and it enables some useful quantum algorithms like the Harrow--Hassidim--Lloyd algorithm for solving linear systems of equations, and the Shor's factorization algorithm. The high-dimensional space of the quantum computer allows at most an exponential speedup over classical algorithms. On the other hand, the superposition space created by the quantum computer does not allow the result to be read directly, which also prevents the algorithm from being used directly as a substitute for the classical FFT algorithm.

Nopeaa Fourier-muunnosta (engl. fast Fourier transform, FFT), joka laskee diskreetin Fourier-muunnoksen, voidaan pitää yhtenä 1900-luvun merkittävimmistä numeerisista algoritmeista, ja sitä käytetäänkin laajasti monissa sovelluksissa. Kuten FFT klassisissa algoritmeissa, Fourier-muunnoksen suorittaminen kvanttitietokoneella (engl. quantum Fourier transform, QFT) on merkittävä algoritmi kvanttialgoritmeissa. Tämän kandityön tavoitteena on esitellä QFT ja sen johtaminen diskreetistä Fourier-muunnoksesta sekä verrata kvanttialgoritmia klassiseen nopeaan Fourier-muunnokseen. Työ esittelee lisäksi lyhyesti muita kvanttialgoritmeja, jotka käyttävän kvanttitietokoneella suoritettavaa Fourier-muunnosta hyväkseen. Työ keskittyy algoritmiin ja sen suorittamiseen teoreettisella kvanttiporttimalliin perustuvalla kvanttitietokoneella. Työ ei käsittele algoritmin toteuttamista käytännössä, oikealla kvanttitietokoneella. Työn pääasiallisena tutkimusmenetelmänä toimii kirjallisuuskatsaus. Tämän lisäksi työssä todistetaan matemaattisesti, että diskreetti Fourier-muunnos voidaan toteuttaa kvanttiporttien avulla. Kirjallisuuskatsauksen ja todistuksen perusteella voidaan todeta, että kvanttitietokoneella laskettava Fourier-muunnos on hyvä työkalu joidenkin jaksollisten ilmiöiden tutkimiseen ja se mahdollistaa muun muassa Harrow'n, Hassidimin ja Lloydin lineaaristen yhtelöiden ratkaisualgoritmin sekä Shorin tekijöintialgoritmin. Kvanttitietokoneen suuriulotteinen avaruus mahdollistaa Fourier-muunnoksen tehokkaan laskemisen. Toisaalta kvanttitietokoneen luoma superpositiotila ei mahdollista tuloksen lukemista suoraan, mikä myös estää algoritmin käyttämisen suoraan klassisen FFT-algoritmin korvikkeena.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Kaski, Petteri

Keywords

quantum computers, quantum Fourier transform, discrete Fourier transform

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202408205537

Collections

[kand] Perustieteiden korkeakoulu / SCI