Eksakto kvantu vaicājošo algoritmu sarežģītība nejaušām Būla funkcijām
| Autor: | Kļevickis, Vladislavs |
|---|---|
| Přispěvatelé: | Smotrovs, Juris, Latvijas Universitāte. Datorikas fakultāte |
| Jazyk: | lotyšština |
| Rok vydání: | 2018 |
| Předmět: | |
| Popis: | 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 It has been proved that for a random n-bit Boolean function optimal quantum query algorithm requires approximately n/2 queries if small probability of error is allowed. However, in case of exact algorithms such complexity is unknown. In this work the capabilities of polynomial method for proving lower bounds of exact quantum query complexity are explored. The goal is to find polynomials of minimal degree, such that their sum of squares represents given Boolean function. First, using semidefinite programming it is shown numerically for n |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|