6533b85cfe1ef96bd12bcdd6
RESEARCH PRODUCT
Kvantu vaicājošie algoritmi
Jeļena ŠIšovasubject
Datorzinātnedescription
Darba mērķis ir uzkonstruēt pēc iespējas efektīvākus kvantu vaicājošos algoritmus multifunkcijām. Pašlaik visefektīvākā zināmā kvantu precīza vaicājošā algoritma sarežģītība ir O(N^0.8675...); klasiskajam algoritmam, kurš risina tādu pašu problēmu, ir nepieciešami vismaz N vaicājumi. Atrast kvantu algoritmu, kurš būtu labāks par klasisko algoritmu, ir diezgan grūts uzdevums. Tiek pieņemts, ka lielu starpību starp kvantu un klasisko vaicājošo algoritmu sarežģītību var sasniegt, ja konstruēt algoritmus multifunkcijām, t.i. kad rezultāts var būt viena vai vairākas vērtības no noteiktas kopas. Darbā tiek aprakstīta programma kvantu algoritmu ģenerēšanai, kura rēķina arī klasiskas sarežģītības apakšējo robežu. Ir aprakstītas arī vairākas multifunkcijas, kurām kvantu vaicājošie algoritmi ir efektīvāki par klasiskajiem algoritmiem.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-01-01 |