Kvanttilaskennan kompleksisuuden perusteet
Mäntysaari, Ville (2023)
2023
Tekniikan ja luonnontieteiden kandidaattiohjelma - Bachelor's Programme in Engineering and Natural Sciences
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2023-05-15
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202305105568
https://urn.fi/URN:NBN:fi:tuni-202305105568
Tiivistelmä
Tässä työssä tarkastellaan kvanttilaskennan kompleksisuuden perusteita. Työssä esitetään kvanttimekaniikan perusteiden kannalta tärkeää lineaarialgebraa sekä kvanttimekaniikan perusteita. Kvanttimekaanisen systeemin tila voidaan kuvata kompleksisen vektoriavaruuden yksikkövektorina. Suljetun kvanttimekaanisen systeemin tilan muutos tilasta toiseen voidaan kuvata kertomalla alkuperäistä tilaa unitaarisella matriisilla. Kvanttimekaanisen systeemin mittaukseen liittyy satunnaisuutta. Jokainen mahdollinen kvanttimekaanisen systeemin mittauksen tulos voidaan saada jollakin tietyllä todennäköisyydellä. Kvanttimekaaninen systeemi siirtyy mittausta vastaavaan tilaan systeemin mittauksen aikana.
Tässä työssä esitetään kvanttivirtapiirimalli, joka on kvanttimekaaninen laskennan malli. Kubitti on yksinkertainen kvanttimekaaninen systeemi, joka voidaan kuvata kahden kvanttimekaanisen tilan superpositiona. Kvanttivirtapiirimallissa laskenta tapahtuu muuttamalla laskennan kubittien tilaa. Kubittien tilaa muutetaan porteilla. Jokaista porttia vastaa jokin unitaarinen matriisi, joka kuvaa systeemin tilan muutosta. Jokainen systeemin tilan muutos voidaan approksimoida mielivaltaisen tarkasti yhdistämällä portteja äärellisestä joukosta portteja.
Laskennallisessa kompleksisuusteoriassa tarkastellaan, kuinka tehokkaasti laskennalliset ongelmat voidaan ratkaista erilaisilla laskennan malleilla. Turingin kone on laskennan malli, jolla voidaan johtaa klassisen laskennan teoreettisia tuloksia. Kvanttivirtapiirimallin avulla voidaan johtaa kvanttilaskentaan liittyviä laskennallisen kompleksisuuden tuloksia. Laskennalliset ongelmat voidaan jakaa luokkiin niiden laskennallisten ominaisuuksien perusteella. Tässä työssä osoitetaan, että tehokkaasti kvanttivirtapiireillä laskettavien ongelmien kompleksisuusluokka BQP kuuluu polynomitilassa laskettavien ongelmien kompleksisuusluokkaan PSPACE.
Tässä työssä esitetään kvanttivirtapiirimalli, joka on kvanttimekaaninen laskennan malli. Kubitti on yksinkertainen kvanttimekaaninen systeemi, joka voidaan kuvata kahden kvanttimekaanisen tilan superpositiona. Kvanttivirtapiirimallissa laskenta tapahtuu muuttamalla laskennan kubittien tilaa. Kubittien tilaa muutetaan porteilla. Jokaista porttia vastaa jokin unitaarinen matriisi, joka kuvaa systeemin tilan muutosta. Jokainen systeemin tilan muutos voidaan approksimoida mielivaltaisen tarkasti yhdistämällä portteja äärellisestä joukosta portteja.
Laskennallisessa kompleksisuusteoriassa tarkastellaan, kuinka tehokkaasti laskennalliset ongelmat voidaan ratkaista erilaisilla laskennan malleilla. Turingin kone on laskennan malli, jolla voidaan johtaa klassisen laskennan teoreettisia tuloksia. Kvanttivirtapiirimallin avulla voidaan johtaa kvanttilaskentaan liittyviä laskennallisen kompleksisuuden tuloksia. Laskennalliset ongelmat voidaan jakaa luokkiin niiden laskennallisten ominaisuuksien perusteella. Tässä työssä osoitetaan, että tehokkaasti kvanttivirtapiireillä laskettavien ongelmien kompleksisuusluokka BQP kuuluu polynomitilassa laskettavien ongelmien kompleksisuusluokkaan PSPACE.
Kokoelmat
- Kandidaatintutkielmat [8639]