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

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

Какую сложность имеет алгоритм нахождения скрытой группы $(\ZZ_2)^k$ :

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

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

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

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

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

В задаче о скрытой подгруппе в $\ZZ_k$ имеется "скрытая подгруппа" $D\subseteq\ZZ^k$ , порядок которой $E=\ZZ^k/D$ не превосходит:

Если

- множество троек вида $(\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$ , то справедливым является равенство:

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

в результате работы процедуры нахождения делителя (

- число различных простых делителей

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

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

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

Если

- множество троек вида $\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$ ):

Если $h_1,\dots,h_l$ - независимые случайные равномерно распределенные элементы абелевой группы

, то вероятность, с которой они порождают всю группу

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

Если имеется чистое состояние $\ket{\psi}\in\calN\otimes\calF$ , то разложение Шмидта имеет вид ( $0<\lambda_j\le 1$ , $\{\ket{\xi_j}\}\subset\calN$ и $\{\ket{\eta_j}\}\subset\calF$ - ортонормированные вектора):

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

Какую сложность имеет алгоритм нахождения скрытой группы :

Какую сложность имеет алгоритм нахождения скрытой группы $(\ZZ_2)^k$ :