Kvantu vaicājošo algoritmu sarežģītība

Abstract

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

The query algorithms are a very convenient model for quantum complexity studies. In the thesis we study query algorithms for func- tions based on full Hamming codes and Reed-Solomon codes. We show a way to construct exact quantum query algorithms for the both sets of functions and compare their complexity to the com- plexity of the most ecient deterministic algorithms. Our algorithm for a Hamming code function of m = 2n 1 argu- ments needs 3=4 m queries to return the value of the function, which is 25% less than the classical complexity. We achieve even better complexity improvement for the functions based on Reed-Solomon code. We show how to construct exact quan- tum query algorithm which needs only m=2 queries when the function has an even number m of arguments. This is a 50% improvement against the classical complexity and this repeats the best known im- provement by exact quantum query algorithms. We also prove a polynomial lower bound for the both sets of func- tions. For Hamming code this bound is 2n2, for Reed-Solomon code it is n 2n2. We nd an optimal adversary lower bound of Hamming code func- tions of three and seven arguments. This gives us a tight lower bound of two queries for the former function and a lower bound of three queries for the latter. Both these lower bounds are higher then the respective polynomial lower bounds. Keywords: quantum query algorithm, complexity, Hamming code, Reed- Solomon code