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

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

Если характеристическая функция предиката вычислима на машине Тьюринга , для которой $S_М(n)=\poly(n)$ , то

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

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

предикат

на множестве $\cb^*$ принадлежит классам

предикат

на множестве $\cb^*$ принадлежит классу PSPACE

предикат

на множестве $\cb^*$ принадлежит классу

(Верный ответ)

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

Условие существования вероятностной машины Тьюринга

и полинома p(n)

, причем машина

заведомо остановится за время, не превосходящее p(|x|)

, определяет, что:

Частичная функция

из $\calA^*$ в $\calA^*$ вычислима на машине Тьюринга :

Если

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

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

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

Если

- неотрицательные операторы, $\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(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(\cdot)$ вычислима булевой схемой размера

, то размер памяти, на которой можно вычислить функцию $\exists\, x_1\:\forall\, y_1\:\dots\:\exists\, x_M\:\forall\, y_M\: f(x_1,y_1,\dots,x_M,y_M,z)$ , равен:

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

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

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

Для любого классического вероятностного алгоритма, делающего не более $2^{k/2}$ обращений к оракулу ( $n\geq k$ ), существует подгруппа $D\subseteq(\ZZ_2)^k$ и соответствующая функция $f\colon (\ZZ_2)^k\to\cb^n$ , для которой вероятность ошибки алгоритма:

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

Если характеристическая функция предиката вычислима на машине Тьюринга , для которой , то

Если характеристическая функция предиката вычислима на машине Тьюринга , для которой $S_М(n)=\poly(n)$ , то