Классические и квантовые вычисления

Какой полиномиальный размер имеет булева функция для умножения вычетов:

(Отметьте один правильный вариант ответа.)

Варианты ответа

$O(\log n)$

(Верный ответ)

Похожие вопросы

Какой размер имеет схема, которой в полном базисе реализуется функция $\MAJ(x_1,\dots,x_n)$ :

Размер схемы умножения чисел

столбиком определяется, как:

Какое название имеет функция $\MAJ(x_1,\dots,x_n)$ :

Как называется порядок числа

в мультипликативной группе вычетов $(\ZZ/q\ZZ)^*$

Порядок числа

в мультипликативной группе вычетов $(\ZZ/q\ZZ)^*(a)$ обозначается как:

Какой вид имеет элемент Тоффоли:

Какой вид имеет линейный оператор?

Какой вид имеет измеряющий оператор?

Если требуется O(n)

обращений к оракулу и каждый вопрос имеет длину $O(k(n+\log k))$ , то размер квантовой схемы определяется как:

Какое свойство характерно для оператора умножения на число U_a