6533b81ffe1ef96bd1278a7a

RESEARCH PRODUCT

Parametrizētu algoritmu paātrinājumi kvantu datoram

subject

description

Darbā tiek aplūkots, kā uz kvantu datora iespējams paātrināt zināmus parametrizētus algoritmus problēmām “Closest string”, “Cluster vertex deletion”, “Cluster editing”, “Vertex cover” un “Longest path” problēmu risinājumiem, ka arī to uzlabošana kvantu datoram, izmantojot kvantu algoritmus meklēšanas koka apstaigāšanai un dinamiskai programmēšanai. Ir parādīts, kā izveidot kvantu algoritmus “Cluster vertex deletion” problēmas risinājumam ar laika sarežģītību 𝑂(1.7321^𝑘 * √𝑘 * 𝑛^3) un “Vertex cover” problēmai ar laiku 𝑂(1.175^𝑘 * 𝑘^𝑂(1) + 𝑛√𝑚), kas ir labāk, nekā labākajiem zināmajiem algoritmiem ar laiku 𝑂(1.9102^𝑘 * (𝑛 + 𝑚)) un 𝑂(1.2738^𝑘 + 𝑘𝑛), attiecīgi. Ka arī ir parādīts, kā izveidot kvantu algoritmus “Closest string” problēmai ar laiku 𝑂(𝑘𝐿 + k^2 * 𝑑^(3/2) * (√(d + 1))^𝑑), “Cluster editing” problēmai ar laiku 𝑂(1.7321^𝑘 * √𝑘 * 𝑛^3) un “Longest path” problēmai ar laiku 𝑂((1.7274√𝑒)^𝑘 * 𝑛^𝑂(1)), kas nav labāk, nekā ātrākiem pazīstamiem algoritmiem ar laiku 𝑂(𝐿𝑘 + 𝑘𝑑(|Σ| − 1)^𝑑 ⋅ 2^3.25𝑑), 𝑂(1.62^𝑘 + 𝑚 + 𝑛)) un 𝑂(2^𝑘 ⋅ 𝑝𝑜𝑙𝑦(𝑛, 𝑘)), attiecīgi.