6533b7cffe1ef96bd1257eb4

RESEARCH PRODUCT

Kvantu algoritmi algoritmiskās ģeometrijas uzdevumiem

subject

description

Viens no svarīgākajiem uzdevumiem teorētiskajā datorzinātnē ir 3SUM uzdevums. 3SUM uzdevumu var formulēt sekojoši: ir dota kopa S ar n veseliem skaitļiem, ir jānoteic, vai eksistē tādi a, b, c ∈ S, ka a + b + c = 0. Šim uzdevumam algoritms ar sarežģītību O(n^(2-ϵ)) nav zināms. Uzdevums 3SUM ir reducējams uz daudziem ģeometriskajiem uzdevumiem, un tiem algoritms ar sarežģītību O(n^(2-ϵ)) arī nav zināms. Darbā ir apvienotas divas svarīgas datorzinātnes nozares: kvantu skaitļošana un algoritmiskā ģeometrija ar mērķi izveidot kvantu algoritmus 3SUM-HARD klases ģeometriskajiem uzdevumiem. Daudziem no tiem ir atrasts kvantu algoritms ar sarežģītību O(n^(1+o(1))).