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

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

Номер 1

Чему равна вероятность получения базисного состояния,  при измерении состояния :

Ответ:

(1)

(2)

(3)

Номер 2

Какое условие должно выполняться, чтобы схема  вычисляла :

Ответ:

(1) для любого math

(2) для любого math

(3) для любого math

Номер 3

В формуле , которой должна удовлетворять квантовая схема , вычисляющая , значение  :

Ответ:

(1)

(2)

(3)

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

Номер 1

Чему равна суммарная длина  и  в формуле , которой должна удовлетворять квантовая схема , вычисляющая :

Ответ:

(1)

(2)

(3)

Номер 2

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

Ответ:

(1)

(2)

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

Номер 3

Какому Выберите верное утверждение:

Ответ:

(1) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая вычисляющая выбор math

является существенным

(2) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая вычисляющая выбор math

не является существенным

(3) в формуле math

, которой должна удовлетворять квантовая схема math

, вычисляющая math

, в качестве N выступает количество битов, с которым работает схема

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

Номер 1

Какое название имеет функция :

Ответ:

(1) функция базиса

(2) функция голосования

(3) обратимая функция

Номер 2

Какое значение принимает функция , если более половины ее аргументов равны 1:

Ответ:

(1)

(2)

(3)

Номер 3

Какой размер имеет схема, которой в полном базисе реализуется функция :

Ответ:

(1)

(2)

(3)

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

Номер 1

За какое время квантовый компьютер вычислит значение предиката  ( - количество шагов):

Ответ:

(1)

(2)

(3)

Номер 2

За какое количество шагов классический компьютер вычислит значение предиката  ( - количество битов в записи y):

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

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

(2) при вычислении предиката math

квантовые устройства дают полиномиальное ускорение по сравнению с классическими

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

за время

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

Номер 1

По какому правилу в квантовой постановке действует оракул, задающий оператор :

Ответ:

(1)

(2)

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

Номер 2

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

Ответ:

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

(2) схема дает неправильный ответ с вероятностью math

(3) схема дает правильный ответ с вероятностью math

Номер 3

Какой вид будет иметь запись оператора  в матричной форме:

Ответ:

(1)

(2)

(3)

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

Номер 1

Оператор, переводящий  в :

Ответ:

(1)

(2)

(3)

Номер 2

Если имеются операторы  и , то:

Ответ:

(1) подпространство math

инвариантно относительно обоих операторов

(2) оба оператора есть отражения относительно гиперплоскости подпространство math

инвариантно оператора math

(3) подпространство math

инвариантно оператора math

Номер 3

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

Ответ:

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

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

(3) композиция двух отражений относительно двух прямых есть поворот на угол между этими прямыми

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

Номер 1

Конструктивное описание квантовой схемы формируется:

Ответ:

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

(2) указанием квантовой вероятности

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

Номер 2

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

Ответ:

(1)

(2)

(3)

Номер 3

Обозначение оператора, реализуемого универсальной квантовой схемой, имеет вид:

Ответ:

(1)

(2)

(3)

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

Номер 1

Если имеется последовательность булевых функций , то однородная последовательность схем, вычисляющих  - это:

Ответ:

(1) классический алгоритм

(2) квантовый алгоритм

(3) специальная унитарная группа

Номер 2

Если существует квантовый алгоритм вычисления функции , работающий за время  для некоторой константы , то функция

Ответ:

(1) принадлежит классу BPP

(2) принадлежит классу BPP и BQP

(3) принадлежит классу BQP

Номер 3

Выберите верную формулу:

Ответ:

(1)

(2)

(3)

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