Būla funkcijas ar augstu jutīgumu un zemu polinoma pakāpi

Abstract

Bakalaura darba ietvaros tiek pētītas Būla funkcijas ar maksimālo jutīgumu. Tiek ņemtas Būla funkcijas ar zemu pārstāvošā polinoma pakāpi, lai tiem būtu liela starpība starp pakāpi un maksimālo jutīgumu, kas iespējami var nozīmēt, ka šo funkciju varēs efektīvi izmantot kvantu algoritmos. Būla funkciju meklēšanai tika izstrādāta un uzlabota datora programma ar mērķi atrast Būla funkciju ar maksimālo jutīgumu, kas ir vienāds ar 14, un pārstāvošā polinoma pakāpi 5. Programma netika gala ar šo uzdevumu, taču tika iegūti jauni rezultāti. Darba otrajā daļā tiek pētīti un meklēti novērtējumi no augšas Būla funkcijas ar noteiktu pārstāvošā polinoma pakāpi jutīgumam. Ar programmas palīdzību tika atrasti jutīguma augšējie novērtējumi Būla funkcijām ar pakāpi ≤ 42 un tika aprēķināta sakarība starp Būla funkcijas jutīguma augšējo novērtējumu un pakāpi.

In the bachelor’s thesis Boolean functions with maximum sensitivity are studied. Boolean functions with a low degree of the representing polynomial are taken in order to have a large difference between the degree and the maximum sensitivity, which can potentially mean that this function can be used efficiently in quantum algorithms. A computer program was developed and improved for searching Boolean functions with the aim of finding a Boolean function with maximum sensitivity equal to 14 and representing polynomial of degree 5. The program did not succeed in this task, but new results were obtained. In the second part of the paper, upper bound estimates on the sensitivity of a Boolean function with a given degree of the representing polynomial are investigated and searched for. The program was used to find upper bound estimates on the sensitivity of a Boolean functions with degree ≤ 42 and to calculate the relation between the sensitivity upper bound estimate and the degree of the Boolean function.