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

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

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

Если предикат L принадлежит классу BPP, то выражение L(x)=1 означает, что:

(Отметьте один правильный вариант ответа.)
Варианты ответа
вероятностная машина Тьюринга с вероятностью большей 2/3 дает ответ "нет"
вероятностная машина Тьюринга с вероятностью меньшей 2/3 дает ответ "да"
вероятностная машина Тьюринга с вероятностью большей 2/3 дает ответ "да"(Верный ответ)
Похожие вопросы
Если установлена принадлежность предиката L к классу BPP, существуют полином q(\cdot) и предикат R(\cdot,\cdot)\in\P, то выражение L(x)=0 означает, что:
Предикат L принадлежит классу NP, если он представим в форме:
Если 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 выполняются условия:
Какому классу принадлежит L, если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что L=\{x\:\big| Б имеет выигрышную стратегию \}(Б - игрок, имеющих имя "белые"):
Если 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, то справедливым является равенство:
Условие L(x)=0 для предиката L, принадлежащего классу NP, означает, что:
Если 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):
Какому классу принадлежит функция 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.
Что из перечисленного является характерным для тензорного произведения двух пространств L и M, в которых фиксированы базисы \{e_1,\dots,e_l\} и \{f_1,\dots,f_l\}