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

В соответствии с алгоритмом Евклида, если делить большее число на меньшее, то длина записи меньшего числа уменьшается на константу:

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

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

на каждом шаге

остается неизменной

за каждый два шага(Верный ответ)

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

Алгоритм Евклида основан на рекурсивном использовании равенства:

Решение универсальной переборной задачи алгоритмом Гровера -

С какой вероятностью должен вычисляться делитель составного числа в подпрограмме для нахождения факторизации числа:

Полная длина квантовой схемы Z, размера L и точности не должна превышать:

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

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

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

В соответствии со свойствами квантовой механики формула $\PP(z_1,\dots,z_k|\,\rho)= \Tr(X^{(z_1)}\otimes\ldots\otimes X^{(z_k)}\rho)$ равна:

Если число ходов ограничено p(|x|)

, а

, то время работы машины Тьюринга ограничено:

Условием выхода из алгоритма проверки простоты числа является:

Проверка простоты числа является классическим примером задачи класса:

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