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

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

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

Алгоритм проверки простоты числа с вероятностью \geq 1/2 выдает ответ:

(Отметьте один правильный вариант ответа.)
Варианты ответа
"n - простое", если n - простое
"n - составное", если n - составное(Верный ответ)
"n - составное", если n - простое
Похожие вопросы
Условием алгоритма проверки простоты числа n, определяющим что n - составное, где a - случайное среди чисел от 1 до n, l - нечетное, является:
Условие a^{n-1}\not\equiv1\pmod n алгоритма проверки простоты числа, где a - случайное среди чисел от 1 до n:
Вероятность получения ответа "n - составное" для алгоритма проверки простоты составного числа n равна:
Если A_1, A_2 - неотрицательные операторы, \calL_1, \calL_2 - их нулевые подпространства, причем \calL_1\cap \calL_2=0, ненулевые собственные числа A_1 и A_2 не меньше v, где \vt=\vt(\calL_1,\calL_2) - угол между \calL_1 и \calL_2, то справедливым является равенство:
Утверждение о том, что схема, на вход которой подан вектор \ket\xi, дает ответ 1 с вероятностью не меньше, чем 1-\eps описывается формулой:
Если Z - множество троек вида (\langle\text{описание k-локального гамильтониана } H\rangle, a, b), где k=O(1), 0\leq a<b, b-a=\Omega(n^{-\alpha}), (a>0), то для z\in Z выполняются условия:
Если существует квантовый алгоритм вычисления функции F\colon\cb^*\to\cb^*, работающий за время O(n^d) для некоторой константы d, то функция F\colon\cb^*\to\cb^*
"Если n=uv - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на n и парами остатков от деления на u и на v " - утверждает:
Если 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 выполняется:
Если имеется физически реализуемое преобразование T\colon\LL(\calN)\to\LL(\calM), причем для любого чистого состояния \rho выполняется свойство: Tr_{\calF}(T\rho)=\rho, то для любого оператора X справедливым является равенство (\gamma - некоторая фиксированная матрица плотности на пространстве \calF):