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

Каким условиям должны удовлетворять операторы $U_n\colon \BB^{\otimes N_n}\to \BB^{\otimes N_n}$ , реализуемые однородной последовательностью квантовых схем полиномиального по размера, чтобы функция $F\colon \cb^n\to \{0,\,1,\,\}$ принадлежала классу BQNP:

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

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

$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) \geq p_1,\\ 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) \leq p_0$

$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)$

$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\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.$

В случае изометрического вложение $V\colon \BB^{\otimes n} \double\to \BB^{\otimes N}$ в пространство большей размерности, задаваемое формулой $\ket\xi\stackrel{\scriptscriptstyle V}{\mapsto} \ket\xi\otimes\ket{0^{N-n}}$ , матрица плотности $\rho$ преобразуется:

Какому условию должно удовлетворять $\eps$ в неравенстве $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\in\BQNP$

Какому условию должно удовлетворять p_1

в неравенстве $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\in\BQNP$

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

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

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

Верно ли, что если применить измеряющий оператор к состоянию $\ket0\bra0\otimes\rho$ , где $\rho\double\in\LL(\calN)$ , то вероятность наблюдения состояния

можно записать в виде: $\PP\Bigl(W(\ket0\bra0\otimes\rho)W^\dagger,\,\CC(\ket{k})\otimes\calN\Bigr) \,=\, \prod\limits_{j} \PP(k\big| j) \PP(\rho, \calL_j)$ ?

Почему

в операторе $\Lambda(U)=\Pi_0\otimes I + \Pi_1\otimes U$ можно разложить в сумму проекторов на собственные подпространства следующим образом: $U=\sum_{j} \lambda_j\Pi_{\calL_j}$ , $|\lambda_j|=1$ ?

Можно ли в операторе $\Lambda(U)=\Pi_0\otimes I + \Pi_1\otimes U$ разложить

в сумму проекторов на собственные подпространства следующим образом: $U=\sum_{j} \lambda_j\Pi_{\calL_j}$ , $|\lambda_j|=1$ ?

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

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

Если на пространстве $\calN=\calN_1\otimes\calN_2$ задана матрица плотности вида $\rho_1\otimes\rho_2$ и имеется два подпространства $\calM_1\subseteq \calN_1$ , $\calM_2\subseteq \calN_2$ , то справедливо равентство: