6533b7d7fe1ef96bd1267e2b
RESEARCH PRODUCT
Eksakto kvantu vaicājošo algoritmu sarežģītība nejaušām Būla funkcijām
Vladislavs Kļevickissubject
pārstāvošie polinomieksaktie kvantu algoritmiDatorzinātnenejaušas Būla funkcijasdescription
Ir pierādīts, ka nejaušai n-bitu Būla funkcijai optimālam kvantu vaicājošajam algoritmam ir nepieciešami aptuveni n/2 vaicājumi, ja algoritmam ir atļauts kļūdīties ar nelielu varbūtību, taču eksaktajiem algoritmiem šī sarežģītība nav zināma. Šajā darbā tiek pētītas polinomiālās metodes iespējas eksaktas kvantu vaicājumu sarežģītības apakšējas robežas pierādīšanai. Tiek apskatīti tādi polinomi, kuru kvadrātu summa pārstāv doto Būla funkciju. Pirmkārt, ar pusnoteiktās programmēšanas palīdzību tiek skaitliski parādīts priekš n<=8, ka nejaušai n-bitu Būla funkcijai pietiekami precīzi |(n+1)/2| pakāpes polinomi eksistē ar lielu varbūtību. Otrkārt, tiek pierādīts, ka gandrīz visas Būla funkcijas var būt precīzi izteiktas ar ne vairāk kā diviem n-1 pakāpes polinomu kvadrātiem, kā arī parādīts, ka eksperimentāli tas izpildās arī priekš n-2.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2018-01-01 |