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

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

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

Если L_1\propto L_2, то:

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа
L_2\in\P \Rightarrow  L_1\in\P(Верный ответ)
L_2\in\NP \Rightarrow  L_1\in\NP(Верный ответ)
L_1\not\in\P \Rightarrow  L_2\not\in\P(Верный ответ)
Похожие вопросы
Проверка транзизитивности сводимости - если L_1\propto L_2, L_2\propto L_3, то L_1\propto L_3 является достаточным доказательством утверждения:
Если 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 выполняются условия:
Если A_1, A_2 - неотрицательные операторы, \calL_1, \calL_2 - их нулевые подпространства, причем \calL_1\cap \calL_2=0, ненулевые собственные числа A_1 и A_2 не меньше v, где \vt=\vt(\calL_1,\calL_2) - угол между \calL_1 и \calL_2, то справедливым является равенство:
Если 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 выполняется:
Если имеется физически реализуемое преобразование T\colon\LL(\calN)\to\LL(\calM), причем для любого чистого состояния \rho выполняется свойство: Tr_{\calF}(T\rho)=\rho, то для любого оператора X справедливым является равенство (\gamma - некоторая фиксированная матрица плотности на пространстве \calF):
Если получено l дробей вида k_1'/t_1',\,k_2'/t_2',\dots,k_l'/t_l' то вероятность того, что наименьшее общее кратное их знаменателей отлично от t (равномерно распределенное на множестве \{0,\dots,t-1\} случайное число):
Чему равна суммарная длина (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:
"Если n=uv - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на n и парами остатков от деления на u и на v " - утверждает:
Если установлена принадлежность предиката L к классу BPP, существуют полином q(\cdot) и предикат R(\cdot,\cdot)\in\P, то выражение L(x)=0 означает, что:
Чем объясняется то, что вероятность события \Prob[G\setminus\big( \bigcup_i g_iX\big)\ne\emptyset] не больше |G|\left(1-|X|/|G|\right)^k, где G - некоторая группа, а X - подмножество G: