E-viri
Recenzirano
-
Ozols, Raitis; Freivalds, Rūsiņš; Ivanovs, Jevgeņijs; Kalniņa, Elīna; Lāce, Lelde; Miyakawa, Masahiro; Tatsumi, Hisayuki; Taimiņa, Daina
SOFSEM 2005: Theory and Practice of Computer ScienceBook Chapter
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
