База ответов ИНТУИТ

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

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

В контексте квантовой постановки нерешаемость задачи для любого предиката \calA(x,y) на квантовой схеме, означает, что:

(Отметьте один правильный вариант ответа.)
Варианты ответа
схема дает неправильный ответ с вероятностью >1/3(Верный ответ)
схема дает неправильный ответ с вероятностью >1/2
схема дает правильный ответ с вероятностью >1/3
Похожие вопросы
Для квантовой схемы \calA - последовательности U_l[A_l]\cdot\ldots\cdot U_1[A_1], A_j выступает в роли:
Если Z - множество троек вида \langle\text{описание квантовой схемы } W\rangle, p_0, p_1) описанием схемы - приближенная реализация в стандартном базисе, а p_1-p_0=\Omega(n^{-\alpha}) (a>0, n - размер описания схемы). Тогда для z\in\Z F(z)=1 выполняется:
Последовательность перестановок U_1[A_1],\dots, U_l[A_l], где A_j - множества битов, U_j\in\calA, \calA - некоторое множество перестановок вида G\colon\cb^k \to \cb^k является:
Если имеется физически реализуемое преобразование T\colon\LL(\calN)\to\LL(\calM), причем для любого чистого состояния \rho выполняется свойство: Tr_{\calF}(T\rho)=\rho, то для любого оператора X справедливым является равенство (\gamma - некоторая фиксированная матрица плотности на пространстве \calF):
За какое время квантовый компьютер вычислит значение предиката F(x)\double=\exists\, y\:\calA(x,y) (N - количество шагов):
Если требуется O(n) обращений к оракулу и каждый вопрос имеет длину O(k(n+\log k)), то размер квантовой схемы определяется как:
Сколько экземпляров квантовой схемы U необходимо взять, чтобы уменьшить вероятность неудачи в N раз:
За какое количество шагов классический компьютер вычислит значение предиката F(x)\double=\exists\, y\:\calA(x,y) (n - количество битов в записи y):
По какому правилу в квантовой постановке действует оракул, задающий оператор U_x:
Если установлена принадлежность предиката L к классу BPP, существуют полином q(\cdot) и предикат R(\cdot,\cdot)\in\P, то выражение L(x)=0 означает, что: