База ответов ИНТУИТ

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

<<- Назад к вопросам

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

(Отметьте один правильный вариант ответа.)
Варианты ответа
O(\log N)
O(n\log N)(Верный ответ)
O(n\log N^2)
Похожие вопросы
Какое название имеет функция \MAJ(x_1,\dots,x_n):
Какое значение принимает функция \MAJ(x_1,\dots,x_n), если более половины ее аргументов равны 1:
Если f(\cdot) вычислима булевой схемой размера L, то размер памяти, на которой можно вычислить функцию \exists\, x_1\:\forall\, y_1\:\dots\:\exists\, x_M\:\forall\, y_M\: f(x_1,y_1,\dots,x_M,y_M,z), равен:
Если Z - множество троек вида \langle\text{описание квантовой схемы } W\rangle, p_0, p_1) описанием схемы - приближенная реализация в стандартном базисе, а p_1-p_0=\Omega(n^{-\alpha}) (a>0, n - размер описания схемы). Тогда для z\in\Z F(z)=1 выполняется:
Если получено l дробей вида k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l' то вероятность того, что наименьшее общее кратное их знаменателей отлично от t (равномерно распределенное на множестве \{0,\dots,t-1\} случайное число):
В качестве \mathsf{Q}_j в булевой формуле \mathsf{Q}_1\, y_1\dots\mathsf{Q}_n\, y_n F(y_1,\dots,y_n), задаваемой задачей TQBF, где y_i\in\cb,F - некоторая логическая формула, выступает:
Что из перечисленного является характерным для тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}
Чему равна суммарная длина (F(x),z) и (x,O^{N-n}) в формуле \sum_{z}^{} \bigl| \langle F(x),z|\,U\,|x,0^{N-n}\rangle\bigr|^2 \geq \varepsilon, которой должна удовлетворять квантовая схема U=U_L\cdot\ldots\cdot U_2U_1, вычисляющая F:
Определение тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}:
Если h_1,\dots,h_l - независимые случайные равномерно распределенные элементы абелевой группы X, то вероятность, с которой они порождают всю группу X, определяется: