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

Упражнение 1:

Номер 1

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

Ответ:

(1) является единственным нетривиальным использованием квантовых свойств для вычислений

(2) дает следствия для теории сложности вычислений

(3) дает полиноминальное ускорение

Номер 2

Автором "задачи о скрытой группе" является

Ответ:

(1) Саймон

(2) Гровер

(3) Черч

Номер 3

Выберите верное утверждение:

Ответ:

(1) косвенным свидетельством превосходства по скорости квантовых вычислений над классическими является задача с оракулом

(2) доказано, что квантовые вычисления значительно превосходят по скорости классические вероятностные вычисления

(3) любой классический вероятностный алгоритм является экспоненциальным

Упражнение 2:

Номер 1

Для любого классического вероятностного алгоритма, делающего не более  обращений к оракулу (), существует подгруппа  и соответствующая функция , для которой вероятность ошибки алгоритма:

Ответ:

(1)

(2)

(3)

Номер 2

Если  - независимые случайные равномерно распределенные элементы абелевой группы  , то вероятность, с которой они порождают всю группу , определяется:

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

(1)

(2)

(3)

Упражнение 3:

Номер 1

Автором каких квантовых алгоритмов является П. Шор:

Ответ:

(1) алгоритм нахождения скрытой группы

(2) алгоритм разложения числа на простые множители

(3) алгоритм вычисления дискретного логарифма

Номер 2

Как называется порядок числа  в мультипликативной группе вычетов

Ответ:

(1) норма

(2) амплитуда

(3) период

Номер 3

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

Ответ:

(1) нет верного ответа

(2)

(3)

Упражнение 4:

Номер 1

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

Ответ:

(1) не меньше math

(2) не меньше math

(3) не больше math

Номер 2

Какова вероятность получить делитель числа  в результате работы процедуры нахождения делителя ( - число различных простых делителей ):

Ответ:

(1) не меньше, чем math

(2) не меньше, чем math

(3) не больше, чем math

Номер 3

Какой полиномиальный размер имеет булева функция для умножения вычетов:

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

Если получено  дробей вида  то вероятность того, что наименьшее общее кратное их знаменателей отлично от  (равномерно распределенное на множестве  случайное число):

Ответ:

(1) больше math

(2) меньше math

(3) меньше math

Номер 2

Выберите верное утверждение:

Ответ:

(1) обозначение несократимой дроби, представляющей рациональное число math

, имеет вид math

(2) для умножения вычетов существует булева схема полиномиального размера math

(3) в контексте квантовых вычислений пределы орбиты числа math

- это цикл перестановки, которому принадлежит math

Номер 3

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

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Условные вероятности для оператора  определяются, как (- значение в -ом бите):

Ответ:

(1)

(2)

(3)

Номер 2

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

Ответ:

(1)

(2)

(3)

Номер 3

Какое свойство характерно для оператора умножения на число

Ответ:

(1)

(2)

(3)

Упражнение 7:

Номер 1

Какое из ниже перечисленных равенств является справедливым (с учетом тождества ):

Ответ:

(1)

(2)

(3)

Номер 2

Выберите верное утверждение:

Ответ:

(1) точность определения собственных чисел полиномиально зависит от размера схемы

(2) если полиномиальная схема есть для самого оператора math

, то ее можно получить для math

(3) определение собственных чисел произвольного оператора производится с высокой точностью

Номер 3

Равномерное распределение на множестве всех собственных чисел  можно получить, если взять в качестве начального состояние, задаваемое следующей диагональной матрицей плотности:

Ответ:

(1)

(2)

(3)

Упражнение 8:

Номер 1

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

Ответ:

(1) Саймоном

(2) Шором

(3) Куком

Номер 2

В задаче о скрытой подгруппе в  имеется "скрытая подгруппа" , порядок которой  не превосходит:

Ответ:

(1)

(2)

(3)

Номер 3

Выберите верное утверждение:

Ответ:

(1) задача о вычислении периода является частным случаем задачи о скрытой подгруппе в math

(2) фурьеобраз от произведения равен свертке фурье-образов сомножителей

(3) распределением по множеству всех собственных чисел можно управлять

(4) определение группы характеров имеет обозначение math

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