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

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

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

Вероятность получения ответа "n - составное" для алгоритма проверки простоты составного числа n равна:

(Отметьте один правильный вариант ответа.)
Варианты ответа
1
1/2(Верный ответ)
1/3
Похожие вопросы
Условием алгоритма проверки простоты числа n, определяющим что n - составное, где a - случайное среди чисел от 1 до n, l - нечетное, является:
Условие a^{n-1}\not\equiv1\pmod n алгоритма проверки простоты числа, где a - случайное среди чисел от 1 до n:
Если вероятность правильного ответа для каждого экземпляра из n запущенных машин Тьюринга равна c>1/2, то вероятность правильного ответа после голосования n машин:
Алгоритм проверки простоты числа с вероятностью \geq 1/2 выдает ответ:
Для любого классического вероятностного алгоритма, делающего не более 2^{k/2} обращений к оракулу (n\geq k), существует подгруппа D\subseteq(\ZZ_2)^k и соответствующая функция f\colon (\ZZ_2)^k\to\cb^n, для которой вероятность ошибки алгоритма:
При двойном проведении алгоритма проверки простоты числа вероятность ошибки оказывается:
Чему равна вероятность получения базисного состояния, x при измерении состояния \ket\psi=\sum_x c_x\ket{x}:
"Если n=uv - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на n и парами остатков от деления на u и на v " - утверждает:
Чему равна вероятность того, что что k случайных сдвигов не покрывают фиксированный элемент, где G - некоторая группа, а X - подмножество G:
Если 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 выполняется: