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

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

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

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

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

Варианты ответа
меньше 1/2
меньше 1/3
меньше 1/4(Верный ответ)
Похожие вопросы
Вероятность получения ответа "n - составное" для алгоритма проверки простоты составного числа n равна:
Условием выхода из алгоритма проверки простоты числа является:
Алгоритм проверки простоты числа с вероятностью \geq 1/2 выдает ответ:
Условие a^{n-1}\not\equiv1\pmod n алгоритма проверки простоты числа, где a - случайное среди чисел от 1 до n:
Условием алгоритма проверки простоты числа n, определяющим что n - составное, где a - случайное среди чисел от 1 до n, l - нечетное, является:
Проверка простоты числа является классическим примером задачи класса:
Для любого классического вероятностного алгоритма, делающего не более 2^{k/2} обращений к оракулу (n\geq k), существует подгруппа D\subseteq(\ZZ_2)^k и соответствующая функция f\colon (\ZZ_2)^k\to\cb^n, для которой вероятность ошибки алгоритма:
С какой вероятностью должен вычисляться делитель составного числа в подпрограмме для нахождения факторизации числа:
Какова вероятность получить делитель числа y в результате работы процедуры нахождения делителя (k - число различных простых делителей y):
Как накапливаются ошибки при квантовом вычислении?