6533b856fe1ef96bd12b208d

RESEARCH PRODUCT

Kvantu algoritmi punktu sadalīšanai pa taisnēm

subject

description

Bakalaura darba mērķis ir uzlabot klasisko algoritmu punktu sadalīšanai pa taisnēm, pielietojot kvantu algoritmus. Darbā tiek apskatīti klasiskie algoritmi punktu sadalīšanas problēmai un sadalīšanas problēmas speciālgadījumam, kad punktu izvietošanā atbilsts daļiņu pozīcijai pēc sadursmes lielā hadronu paātrinātājam. Darba rezultātā tiek piedāvāti kvantu algoritmi ar sarežģītību O(n^(1+(k-1)/k)/k) pamata problēmai un O(n^1.5/√k log⁡(n/k) ) speciālgadījumam. Dotie algoritmi uzlabo efektīvāko zināmo klasisko algoritmu, kuram darbības laiks ir O(n^2/k*log⁡(n/k) ). Secinājumos tiek piedāvāts paņēmiens, ka pielietot speciālgadījuma rezultātus reālajam daļiņu ceļu atrašanas uzdevumam, kad daļiņu ceļi ir slīpas līnijas.