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

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

Номер 1

Если требуется  обращений к оракулу и каждый вопрос имеет длину , то размер квантовой схемы определяется как:

Ответ:

(1)

(2)

(3)

Номер 2

Функция  принадлежит классу NP, если есть частично определенная функция  от двух переменных, такая что:

Ответ:

(1)

(2)

(3)

Номер 3

Класс, входящий в иерархию классов, определяемых играми Артура - Мерлина, обозначается как:

Ответ:

(1) MA

(2) NP

(3) BPP

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

Номер 1

В играх Артура - Мерлина в качестве Артура выступает:

Ответ:

(1) детерминированная полиномиальная машина Тьюринга

(2) вероятностная полиномиальная машина Тьюринга

(3) недетерминированная полиномиальная машина Тьюринга

Номер 2

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

Ответ:

(1) NP

(2) BQNP

(3) BPP

Номер 3

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

Ответ:

(1)

(2)

(3)

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

Номер 1

Какому условию должно удовлетворять  в неравенстве , если

Ответ:

(1)

(2)

(3)

Номер 2

Какому условию должно удовлетворять  в неравенстве , если

Ответ:

(1)

,

(2)

,

(3)

,

Номер 3

В соответствии со свойствами квантовой механики формула  равна:

Ответ:

(1)

(2)

(3)

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

Номер 1

Если  - множество троек вида  описанием схемы - приближенная реализация в стандартном базисе, а  (,  - размер описания схемы). Тогда для  выполняется:

Ответ:

(1) если существует вектор math

, при действии на который в первом бите получится 1 с вероятностью, большей math

(2) если существует вектор math

, при действии на который в первом бите получится 1 с вероятностью, меньшей math

(3) если для всех math

вероятность получить в первом бите 1 меньше math

Номер 2

Каждое слагаемое локального гамильтониана  является:

Ответ:

(1) эрмитовым оператором, действующим на множестве q-битов math

,

(2) проектором, действующим на множестве q-битов math

,

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

Номер 3

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

Ответ:

(1) локальный гамильтониан является квантовым аналогом 3-кнф

(2) локальность является аналогом ограниченности числа переменных, входящих в одну дизъюнкцию

(3) в классе BQNP не существует полных задач относительно полиномиальной сводимости

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

Номер 1

Условие нормировки  означает:

Ответ:

(1)

и

- отрицательно полуопределенные

(2)

и

- положительно полуопределенные

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

Номер 2

Если  - множество троек вида , где , , , (), то для  выполняются условия:

Ответ:

(1)

если у

есть собственное число, не меньшее math

(2)

если у

есть собственное число, не большее math

(3)

если все собственные числа math

больше

Номер 3

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

Ответ:

(1) PSPACE

(2) BQNP

(3) PP

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

Номер 1

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

Ответ:

(1) пространство, на котором действует схема

(2) пространство счетчика шагов

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

Номер 2

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

Ответ:

(1)

(2)

(3)

(4)

Номер 3

Конечному состоянию гамильтониана, сопоставляемого схеме, отвечает:

Ответ:

(1)

(2)

(3)

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

Номер 1

Чему равна левая часть формулы

Ответ:

(1)

(2)

(3)

Номер 2

Какое слагаемое гамильтониана  описывает эволюцию системы:

Ответ:

(1)

(2)

(3)

Номер 3

Как определяется слагаемое гамильтониана , отвечающее начальному состоянию:

Ответ:

(1)

(2)

(3)

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

Номер 1

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

Ответ:

(1)

(2)

(3)

Номер 2

Если ,  - неотрицательные операторы, ,  - их нулевые подпространства, причем , ненулевые собственные числа  и  не меньше , где  - угол между  и , то справедливым является равенство:

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

(1)

(2)

(3)

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