A2 – LU disertācijas / Doctoral theses UL

Permanent URI for this community

https://dspace-dev.lu.lv/handle/7/24

Browse

Browsing A2 – LU disertācijas / Doctoral theses UL by Author "Agadžanjans, Rubens"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Kvantu vaicājošo algoritmu sarežģītība
    (Latvijas Universitāte, 2011) Agadžanjans, Rubens; Freivalds, Rūsiņš Mārtiņš; Latvijas Universitāte. Datorikas fakultāte
    Vaicājošie algoritmi ir viens no ērtākiem modeļiem kvantu sarežģītības pētīšanai. Promocijas darbā ir pētīti vaicājošie algoritmi funkcijām, kuras ir bāzētas uz pilniem Heminga un Rīda-Solomona kodiem. Mēs rādām kā uzkonstruēt eksaktos kvantu vaicājošos algoritmus abām funkciju kopām un salīdzinām viņu sarežģītību ar visefektīvāko determinēto algoritmu sarežģītību. Heminga koda funkcijai no m = 2n - 1 argumentiem mūsu algo- ritmam pietiek ar 3=4 m kvantu vaicājumiem lai atgrieztu funkcijas vērtību, kas ir par 25% mazāk nekā klasiskā sarežģītība. Mēs sasniedzam vēl lielāku sarežģītības uzlabojumu funkcijām bāzētām uz Rīda-Solomona kodiem. Mēs parādam kā uzkonstruēt eksakto kvantu vaicājošo algoritmu, kuram pietiek ar m=2 vaicājumiem kad funkcijai ir pāra skaits m argumentu. Tas ir 50% uzlabojums salīdzinājumā ar klasisko sarežģītību un tas atkārto vislabāko zināmo uzlabojumu eksaktiem kvantu vaicājošiem algoritmiem. Mēs pierādām arī polinomiālo apakšējo novērtējumu abām funkciju kopām. Heminga kodiem šis novērtējums ir 2n2, Rīda-Solomona kodiem { n 2n2. Mēs atrodam optimēlo apakšējo novērtējumu ar "adversary" metodi Heminga koda funkcijām no trim un septiņiem argumentiem. Pirmajai funkcijai tas dod ciešo apakšējo novērtējumu, ka ir nepieciešami divi vaicājumi. Apakšējais novērtējums otrai funkcijai ir trīs vaicājumi. Abi šie novērtējumi ir labāki, nekā attiecīgie novērtējumi ar poli-nomiālo metodi. Atslēgas vārdi: kvantu vaicājošie algoritmi, sarežģītība, Heminga kods, Rīda-Solomona kods