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

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

Предикат принадлежит классу , если он представим в форме:

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

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

$L(x)=\exists\, y\:\big( (|y|<q(|x|))\:\wedge\: R(x,y)\big)$ (Верный ответ)

$L(x)=\exists\, y\:\big( (|y|>q(|x|))\:\wedge\: R(x,y)\big)$

$L(x)=\exists\, y\:\big( (|y|>q(|x|))\:\vee\: R(x,y)\big)$

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

Если предикат

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

означает, что:

Если установлена принадлежность предиката

к классу BPP, существуют полином $q(\cdot)$ и предикат $R(\cdot,\cdot)\in\P$ , то выражение L(x)=0

означает, что:

Если

-полный предикат можно вычислить за время T(n)

, то любой предикат из

для некоторого числа

можно вычислить за время:

Условие

для предиката

, принадлежащего классу

, означает, что:

Если

- множество троек вида $(\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=\{x\:\big|$ Б имеет выигрышную стратегию $\}$ (Б - игрок, имеющих имя "белые"):

Если

- неотрицательные операторы, $\calL_1$ , $\calL_2$ - их нулевые подпространства, причем $\calL_1\cap \calL_2=0$ , ненулевые собственные числа A_1

не меньше

, где $\vt=\vt(\calL_1,\calL_2)$ - угол между $\calL_1$ и $\calL_2$ , то справедливым является равенство:

Если

- множество троек вида $\langle\text{описание квантовой схемы } W\rangle, p_0, p_1)$ описанием схемы - приближенная реализация в стандартном базисе, а $p_1-p_0=\Omega(n^{-\alpha})$ ( a>0

- размер описания схемы). Тогда для $z\in\Z F(z)=1$ выполняется:

Если имеется физически реализуемое преобразование $T\colon\LL(\calN)\to\LL(\calM)$ , причем для любого чистого состояния $\rho$ выполняется свойство: $Tr_{\calF}(T\rho)=\rho$ , то для любого оператора

справедливым является равенство ( $\gamma$ - некоторая фиксированная матрица плотности на пространстве $\calF$ ):

Какому классу принадлежит функция $F\colon \cb^n\to \{0,\,1,\,\}$ , если существует однородная последовательность квантовых схем полиномиального по

размера, реализующих такие операторы $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.$