Kvantu algoritms maksimāla inducēta meža problēmai

Abstract

Maksimāla inducēta meža problēmas uzdevums ir atrast dotajā grafā maksimāli lielu apakškopu no tā virsotnēm, kas veido aciklisku grafu. Šī ir plaši zināmā NP-pilna problēma, kas nozīme, ka labākais zināmais algoritms spēj atrisināt to eksponenciālajā laikā. Šī problēmas papildinājums ir plaši zināma problēma, ko sauc par virsotņu kopu ar atpakaļvērstām šķautnēm, līdz ar to abu problēmu algoritmi ir ekvivalenti. Šajā darbā ir piedāvāts jauns kvantu algoritms, kas balstās uz kvantu klejošanas principiem un risina doto problēmu laikā O*(1.3747^n log(1/δ)), kur δ ir kļūdas varbūtība. Darbā ir nodemonstrēta klasiskā algoritma darbība, aprakstīta kvantu pieeja līdzīgo problēmu risināšanai, kā arī ir nodefinēta struktūra un piedāvāti algoritmi, kas ļauj optimizēt vienu no ātrākajiem zināmajiem klasiskajiem algoritmiem dotai problēmai.

The main task of the maximum induced forest (MIF) problem is to find in a given graph a largest possible subset of its vertices that induce an acyclic graph. This is a well-known NP-complete problem, meaning that the best known algorithm can solve it in exponential time. The complement of this problem is a well-known problem called feedback vertex set (FVS), so the algorithms for the two problems are equivalent. In this work, a new quantum algorithm is proposed, which is based on the principles of quantum walk, and solves the given problem in time O*(1.3747^n log(1/δ)), where δ is the error probability. This work decomposes the classical algorithm, describes the quantum approach to solving similar backtracking problems, defines the structure and proposes algorithms that allow optimizing one of the fastest known classical algorithm for that problem.