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

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

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

Если 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), равен:

(Отметьте один правильный вариант ответа.)
Варианты ответа
O(L^M)
O(LM)
O(L+M)(Верный ответ)
Похожие вопросы
В качестве \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\}
Если получено l дробей вида k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l' то вероятность того, что наименьшее общее кратное их знаменателей отлично от t (равномерно распределенное на множестве \{0,\dots,t-1\} случайное число):
Определение тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}:
Какому классу принадлежит функция F\colon \cb^n\to \{0,\,1,\,\}, если существует однородная последовательность квантовых схем полиномиального по n размера, реализующих такие операторы U_n\colon \BB^{\otimes N_n}\to \BB^{\otimes N_n}, что F_n(x)=1 & \Longrightarrow & \exists\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \geq p_1,\\ F_n(x)=0 & \Longrightarrow & \forall\, \ket\xi\: \PP\Bigl(U_n\ket\xi\otimes\ket{x}\otimes\ket{0^{N_n-n-m_n}},\calM\Bigr) \leq p_0.
Чему равна суммарная длина (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:
При сравнении вероятностных распределений в \ell^1 - норме,если \boldsymbol p=(p_1,\dots,p_n) , \boldsymbol q=(q_1,\dots,q_n) - два распределения, то мерой их различия считаем
Если Z - множество троек вида (\langle\text{описание k-локального гамильтониана } H\rangle, a, b), где k=O(1), 0\leq a<b, b-a=\Omega(n^{-\alpha}), (a>0), то для z\in 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 к классу BPP, существуют полином q(\cdot) и предикат R(\cdot,\cdot)\in\P, то выражение L(x)=0 означает, что: