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

Функция $F\colon \cb^n\to \{0,\,1,\, \langle \text{не определено}\rangle}\}$ принадлежит классу NP, если есть частично определенная функция $R\in\P$ от двух переменных, такая что:

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

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

$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)=1 & \Longrightarrow & \forall\, y\:\big((|y|<q(|x|))\wedge(R(x,y)=1)\big),\\ F(x)=0 &>\Longrightarrow & \exists\, y\: \big((|y|<q(|x|))\Rightarrow(R(x,y)=0)\big)$

$F(x)=1 & \Longrightarrow & \exists\, y\:\big((|y|<q(|x|))\wedge(R(x,y)=1)\big),\\ F(x)=0 &>\Longrightarrow & \forall\, y\: \big((|y|<q(|x|))\Rightarrow(R(x,y)=0)\big)$ (Верный ответ)

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

Если

- множество троек вида $(\langle\text{описание k-локального гамильтониана } H\rangle, a, b)$ , где k=O(1)

, $0\leq a<b$ , $b-a=\Omega(n^{-\alpha})$ , ( a>0

), то для $z\in Z$ выполняются условия:

Если

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

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

Какому классу принадлежит функция $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.$

Каким условиям должны удовлетворять операторы $U_n\colon \BB^{\otimes N_n}\to \BB^{\otimes N_n}$ , реализуемые однородной последовательностью квантовых схем полиномиального по

размера, чтобы функция $F\colon \cb^n\to \{0,\,1,\,\}$ принадлежала классу BQNP:

Если существует квантовый алгоритм вычисления функции $F\colon\cb^*\to\cb^*$ , работающий за время O(n^d)

для некоторой константы

, то функция $F\colon\cb^*\to\cb^*$

Чему равна суммарная длина (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$ , вычисляющая

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

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

Для любого классического вероятностного алгоритма, делающего не более $2^{k/2}$ обращений к оракулу ( $n\geq k$ ), существует подгруппа $D\subseteq(\ZZ_2)^k$ и соответствующая функция $f\colon (\ZZ_2)^k\to\cb^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$ , вычисляющая

, значение $\varepsilon$ :

Какому классу принадлежит

, если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что $L=\{x\:\big|$ Б имеет выигрышную стратегию $\}$ (Б - игрок, имеющих имя "белые"):

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

Функция принадлежит классу NP, если есть частично определенная функция от двух переменных, такая что:

Функция $F\colon \cb^n\to \{0,\,1,\, \langle \text{не определено}\rangle}\}$ принадлежит классу NP, если есть частично определенная функция $R\in\P$ от двух переменных, такая что: