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

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

Какое понятие используется для определения класса :

(Ответ считается верным, если отмечены все правильные варианты ответов.)

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

понятие полиномиально вычислимого предиката от одной переменной

понятие полиномиально вычислимого предиката от двух переменных(Верный ответ)

понятие недетерминированной машины Тьюринга(Верный ответ)

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

Если

-полный предикат можно вычислить за время 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$ выполняются условия:

Если

- неотрицательные операторы, $\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$ , вычисляющая

Чем объясняется то, что вероятность события $\Prob[G\setminus\big( \bigcup_i g_iX\big)\ne\emptyset]$ не больше $|G|\left(1-|X|/|G|\right)^k$ , где

- некоторая группа, а

- подмножество

Условием алгоритма проверки простоты числа

, определяющим что

- составное, где

- случайное среди чисел от 1 до

- нечетное, является: