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

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

Номер 1

В данной книге утверждается:

Ответ:

(1) Концепция симметрии сыграла центральную роль в физике 20-го века.

(2) Концепция симметрии сыграла центральную роль в информатике 20-го века.

(3) Теория групп является инструментом изучения симметрии.

(4) Теория групп позволяет обобщить алгебру логики на алгебру симметрий.

(5) Теория групп позволяет обобщить алгебру чисел на алгебру симметрий.

Номер 2

Какие утверждения не соответствуют определению понятия «группа»:

Ответ:

(1) Группа представляет множество элементов с некоторым выделенным элементом и двумя операциями — унарной и бинарной.

(2) Множество элементов группы содержит два выделенных элемента — ноль и единица.

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

(4) Для любого элемента группы u существует обратный элемент v, вычисляемый унарной операцией инверсии. Обратный элемент обозначается как u^-1 в мультипликативной группе, - u в аддитивной группе.

(5) Для любого элемента мультипликативной группы u: u • u^-1 = e, где e – единица группы.

(6) Выделенные элементы группы 0 и 1 взаимно обратимы.

Номер 3

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

Ответ:

(1) Множество целых чисел с выделенным элементом 0, бинарной операцией сложения и инверсией -x.

(2) Множество целых чисел с выделенным элементом 1, бинарной операцией умножения и инверсией (операцией деления) 1 / x.

(3) Множество целых чисел с выделенным элементом 1, бинарной операцией умножения и инверсией (операцией деления нацело) 1 % x.

(4) Множество вещественных чисел, из которого исключено число 1, с выделенным элементом 0, бинарной операцией сложения и инверсией -x.

(5) Множество вещественных чисел, из которого исключено число 0, с выделенным элементом 1, бинарной операцией умножения и инверсией (операцией деления) 1 / x.

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

Номер 1

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

Ответ:

(1) Каждая трансформация симметрии T обратима — существует обратная трансформация T^-1.

(2) Трансформации симметрии T и T^-1 совпадают.

(3) Композиция трансформаций симметрии является трансформацией симметрии.

(4) Композиция трансформаций симметрии коммутативна.

(5) Композиция трансформаций симметрии ассоциативна.

(6) Существует трансформация симметрии, не меняющая объект, - трансформация тождественности, играющая роль единицы в группе трансформаций симметрии.

Номер 2

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

Ответ:

(1) Диедральная группа — это группа, элементы которой являются диедралами.

(2) Диедральная группа — это группа, элементы которой являются трансформациями симметрии правильного многоугольника с n вершинами.

(3) Число элементов диедральной группы равно n.

(4) Число элементов диедральной группы равно 2n.

(5) Число элементов диедральной группы равно 2ⁿ.

Номер 3

Какие группы являются абелевыми (коммутативными):

Ответ:

(1) Группа обратимых квадратных матриц с операцией умножения матриц.

(2) Группа трансформаций симметрий квадрата.

(3) Группа вещественных чисел с операцией сложения.

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

Номер 1

Рассмотрим группу трансформаций симметрии равностороннего треугольника. Какие утверждения справедливы:

Ответ:

(1) Поворот на 90° — является элементом группы.

(2) Поворот на 120° — является элементом группы.

(3) Поворот на 180° — является элементом группы.

(4) Поворот на 240° — является элементом группы.

(5) Поворот на 270° — является элементом группы.

(6) Число элементов в группе равно 6.

(7) Число элементов в группе равно 3.

Номер 2

Рассмотрим диедральную группу. Пусть R – трансформация поворота, а T – трансформация отражения. Какие утверждения справедливы:

Ответ:

(1) Трансформация T совпадает с инверсией T: T₂ = I.

(2) Трансформация R совпадает с инверсией R: R₂ = I.

(3) Трансформация R в степени n совпадает с единичной трансформацией: Rⁿ = I.

(4) Трансформация T в степени n совпадает с единичной трансформацией: Rⁿ = I.

(5) Rⁱ T = T R^-i.

(6) Rⁱ T = T R^n-i.

Номер 3

Рассмотрим диедральную группу. Пусть R – трансформация поворота, а T – трансформация отражения. Какие утверждения справедливы относительно композиции трансформаций:

Ответ:

(1) Композиция поворотов — поворот (RºR = R).

(2) Композиция поворотов — отражение (RºR = T).

(3) Композиция поворота и отражения — поворот (RºT = R).

(4) Композиция поворота и отражения — отражение (RºT = T).

(5) Композиция отражения и поворота — поворот (T ºR = R).

(6) Композиция отражения и поворота — отражение (T ºR = T).

(7) Композиция отражений — поворот (T ºT = R).

(8) Композиция отражений — отражение (T ºT = T).

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

Номер 1

Для группы симметрий квадрата чему равен элемент таблицы умножений T₁V₂:

Ответ:

(1) R₁.

(2) R₂.

(3) R₃.

Номер 2

Для группы симметрий квадрата чему равен элемент таблицы умножений T₁T₂:

Ответ:

(1) R₁.

(2) R₂.

(3) R₃.

Номер 3

Для группы симметрий квадрата чему равен элемент таблицы умножений T₁V₁:

Ответ:

(1) R₁.

(2) R₂.

(3) R₃.

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

Номер 1

Укажите корректные утверждения:

Ответ:

(1) Каждая группа содержит подгруппы.

(2) Каждый элемент группы g порождает циклическую подгруппу {g^k}, где 1 ≤k≤ n.

(3) Число подгрупп совпадает с порядком группы — числом ее элементов.

(4) Подгруппой группы D₄ = { e, R₁, R₂, R₃, T₁, T₂, V₁, V₂} является группа { e, T₁, T₂, V₁, V₂}.

(5) Подгруппой группы D₄ = { e, R₁, R₂, R₃, T₁, T₂, V₁, V₂} является группа { e, R₁, R₂, R₃}.

Номер 2

Сколько подгрупп содержит группа D₄ = { e, R₁, R₂, R₃, T₁, T₂, V₁, V₂}:

Ответ:

(1) 4.

(2) 5.

(3) 6.

(4) 7.

Номер 3

Смежным классом для элемента группы g и подгруппы H называется множество произведений {gh}, где h – пробегает все значения элементов подгруппы H. Сколько различных смежных классов существует для подгруппы H = { e, R₁, R₂, R₃} группы D₄ = { e, R₁, R₂, R₃, T₁, T₂, V₁, V₂}:

Ответ:

(1) 1.

(2) 2.

(3) 3.

(4) 4.

(5) 7.

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

Номер 1

Какие утверждения справедливы:

Ответ:

(1) Порядок любой подгруппы H группы G является делителем порядка G.

(2) Группа G является объединением непересекающихся смежных классов любой подгруппы H группы G.

(3) Порядок любого элемента g группы G является делителем порядка G.

(4) Для любого элемента g группы G справедливо: gⁿ = e, где n – порядок G.

(5) Порядок группы равен сумме порядков ее подгрупп.

Номер 2

Смежным классом для элемента группы g и подгруппы H называется множество произведений {gh}, где h – пробегает все значения элементов подгруппы H. Сколько различных смежных классов существует для подгруппы H = { e, T₁} группы D₄= { e, R₁, R₂, R₃, T₁, T₂, V₁, V₂}:

Ответ:

(1) 1.

(2) 2.

(3) 3.

(4) 4.

(5) 7.

Номер 3

Какие утверждения справедливы:

Ответ:

(1) Порядком элемента группы g называется минимальное целое k, такое что g^k = e.

(2) Для любого элемента группы g справедливо gⁿ = e, где n – порядок группы.

(3) В группе G всегда существует элемент g, порядок которого совпадает с порядком группы.

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

Номер 1

Какие утверждения справедливы для множества остатков по модулю m:

Ответ:

(1) Число элементов этого множества равно m.

(2) Множество образует аддитивную группу _m с операцией сложения по модулю m.

(3) Множество образует мультипликативную группу ^*_m с операцией умножения по модулю m.

(4) В аддитивной группе _mобратным элементом к элементу k является элемент m – k.

(5) Аддитивная группа _mявляется циклической с генератором 1.

(6) В мультипликативной группе ^*_mобратным элементом к элементу k является элемент m – k.

Номер 2

Определите порядок элемента 7 в аддитивной группе остатков по модулю 13:

Ответ:

(1) 5.

(2) 7.

(3) 9.

(4) 11.

(5) 13.

(6) 15.

Номер 3

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

Ответ:

(1) Число элементов этой группы равно m.

(2) Существует группа, число элементов которой равно m.

(3) Если m – простое число, то число элементов этой группы равно m – 1.

(4) Из аддитивной группы _mв мультипликативную группу ^*_mпопадают только те элементы, которые имеют мультипликативно обратный элемент.

(5) Остаток k имеет мультипликативно обратный элемент в _mтогда и только тогда, когда НОД(m, k) = 1.

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

Номер 1

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

Ответ:

(1) Пусть p - простое число. Если a – целое, не делящееся на p, то a^p-1 = 1 mod p.

(2) Если НОД(m, s ) = 1, то для любой пары остатков amodm, b mod s существует уникальный остаток x mod ms, такой что x = a mod m и x = b mod s.

(3) Пусть G – конечная группа, тогда порядок любой подгруппы H в G является делителем порядка G и порядок любого элемента g в G является делителем порядка G.

Номер 2

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

Ответ:

(1) Пусть p - простое число. Если a – целое, не делящееся на p, то a^{p – 1} = 1 modp.

(2) Если НОД(m, s ) = 1, то для любой пары остатков a mod m, b mod s существует уникальный остаток x mod ms, такой что x = a mod m и x = b mod s.

(3) Пусть G – конечная группа, тогда порядок любой подгруппы H в G является делителем порядка G и порядок любого элемента g в G является делителем порядка G.

Номер 3

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

Ответ:

(1) Пусть p - простое число. Если a – целое, не делящееся на p, то a^{p – 1} = 1 modp.

(2) Если НОД(m, s ) = 1, то для любой пары остатков amodm, b mod s существует уникальный остаток xmodms, такой что x = amodm и x = b mod s.

(3) Пусть G – конечная группа, тогда порядок любой подгруппы H в G является делителем порядка G и порядок любого элемента g в G является делителем порядка G.

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

Номер 1

Какие утверждения справедливы для группы O(2) непрерывных трансформаций симметрии на плоскости:

Ответ:

(1) Элементы группы могут быть трансформациями двух типов — повороты R_α и отражения T_α.

(2) Множество элементов можно представить как {R_α, T_α}, где α — произвольный угол в пределах от до 360°.

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

(4) Обратной к трансформации R_α является сама трансформация R_α.

(5) Обратной к трансформации T_α является сама трансформация T_α.

Номер 2

Какие тождества принадлежат таблице умножения для элементов группы O(2) – группы непрерывных трансформаций симметрии на плоскости:

Ответ:

(1) R_α R_β= R_α+β.

(2) T_α T_β= T_α+β.

(3) T_α T_β= T_α-β.

(4) T_α T_β = R_α-β.

(5) R_α T_β = T_α+β.

Номер 3

Какие утверждения справедливы для группы O(3) непрерывных трансформаций симметрии в трехмерном пространстве ³:

Ответ:

(1) Элементы группы могут быть трансформациями двух типов — пространственные повороты вокруг некоторой оси R_α и отражения в некоторой плоскости T_α.

(2) Плоскость, в которой выполняется отражение выбирается независимо от оси поворота.

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

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

Номер 1

Квантовый алгоритм представляет ортогональную трансформацию в пространстве кубитов^N. При реализации алгоритма эта трансформация декомпозируется на трансформации в подпространствах L_i меньшей размерности. Какие утверждения справедливы относительно этих подпространств:

Ответ:

(1) Каждое подпространство L_i имеет размерность 3.

(2) Все подпространства L_i взаимно не пересекаются.

(3) Каждое подпространство L_i имеет размерность 1 или 2.

(4) Все подпространства L_i пересекаются в одной точке — начале координат.

(5) Каждое подпространство L_i инвариантно относительно трансформации T. Это означает, что T преобразует вектор из L_i в вектор в том же подпространстве L_i.

Номер 2

Укажите корректные утверждения:

Ответ:

(1) Квантовый алгоритм является ортогональной трансформацией в пространстве кубитов ^N.

(2) Квантовый алгоритм может быть декомпозирован в композицию элементарных трансформаций, выполняемых в подпространствах малой размерности — 1 или 2.

(3) В одномерном пространстве отражение является ортогональной трансформацией.

(4) В двумерном пространстве поворот является ортогональной трансформацией.

(5) Декомпозиция алгоритма выполняется автоматически.

Номер 3

Квантовый алгоритм представляет ортогональную трансформацию в пространстве кубитов^N. При реализации алгоритма эта трансформация декомпозируется на трансформации в подпространствах L_i меньшей размерности. Какие утверждения справедливы относительно этих подпространств:

Ответ:

(1) Каждое подпространство L_i имеет размерность 1 или 2.

(2) В одномерном подпространстве L_i трансформация представляет отражение Tv = v или Tv = - v.

(3) В двумерном подпространстве L_i трансформация представляет поворот в плоскости L_i.

(4) На диагонали матрицы трансформации всегда стоят 1.

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