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

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

Номер 1

Дискретное преобразование Фурье (ДПФ) – это широко используемый на практике математический инструмент изучения поведения периодических или почти периодических функций. Какие утверждения справедливы для ДПФ:

Ответ:

(1) Непрерывную функцию, описывающую некоторый колебательный процесс, можно рассматривать как функцию f(t), изменяющуюся во времени.

(2) От непрерывной функции f(t) можно перейти к ее дискретному представлению – вектору f = (f₀, f₁, …, f_{N – 1}), где f_j = f(t_j) – измеренное значение функции f в момент времени t_j.

(3) При построении ДПФ измерения значений f(t) можно выполнять в произвольные моменты времени.

(4) При построении ДПФ измерения значений f(t) следует выполнять на некотором интервале 0 < t < π в N равноотстоящих точках этого интервала.

Номер 2

Дискретное преобразование Фурье (ДПФ) – это широко используемый на практике математический инструмент изучения поведения периодических или почти периодических функций. Какие утверждения справедливы для ДПФ:

Ответ:

(1) Непрерывную функцию, описывающую некоторый колебательный процесс, можно рассматривать как функцию f(t), изменяющуюся во времени.

(2) Непрерывную функцию, описывающую некоторый колебательный процесс, можно рассматривать как функцию f, представляющую суперпозицию семейства базисных функций sin(kt) и cos(kt).

(3) ДПФ позволяет перейти от временного представления функции к частотному представлению.

(4) Обратный переход от частотного представления к временному не всегда возможен, поскольку обратное преобразование Фурье может не существовать.

Номер 3

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

Ответ:

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

(2) Колебательный процесс имеет основную базисную частоту колебаний.

(3) Колебательный процесс помимо колебания с базисной частотой включает обертона – колебания с другими частотами.

(4) Число обертонов ограничено и не может быть более трех.

(5) Математические функции sin(x) и cos(x) позволяют моделировать колебательные процессы.

(6) Функции sin(x) и cos(x) позволяют моделировать только колебания с базовой частотой, но не обертона.

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

Номер 1

Пусть f(t) – периодическая (почти периодическая) функция с периодом T, который за счет масштабирования времени можно полагать равным π. Измеряя значения функции на интервале 0 <t<π, перейдем к вектору f с координатами: f(t₀, t₁, …t_N-1) в пространстве ^N. Пусть N – четно и равно 2M, а t_j= (2j + 1)* π /(2*N). 
Пусть в ^N построен ортонормированный базис из векторов {u_k, v_k},где 
u_k= √(2/N){cos((2k+1)*t₀), cos((2k+1)*t₁), … , cos((2k+1)*t_N-1)}, (k = 0, 1, … M - 1).
v_k = √(2/N){sin((2k+1)*t₀), sin((2k+1)*t₁), … , sin((2k+1)*t_N-1)}, (k = 0, 1, … M - 1).
Укажите корректные высказывания:

Ответ:

(1)

Вектор f может быть представлен как суперпозиция базисных векторов:

f = a₀u₀ + a₁u₁ + … + a_M-1u_M-1 + b₀v₀+ b₁v₁ + … + b_M-1v_M-1, где a_k, b_k– коэффициенты Фурье.

(2) Коэффициент Фурье a_k может быть вычислен как скалярное произведение базисных векторов u_kºu_k.

(3) Коэффициент Фурье b_k может быть вычислен как скалярное произведение векторов fºv_k.

(4) Коэффициент Фурье a_k может быть вычислен как скалярное произведение векторов fºu_k.

(5) Коэффициент Фурье a_k может быть вычислен как скалярное произведение базисных векторов u_kºv_k.

Номер 2

Пусть f(t) – периодическая (почти периодическая) функция с периодом T, который за счет масштабирования времени можно полагать равным π. Измеряя значения функции на интервале 0 <t<π, перейдем к вектору f с координатами: f(t₀, t₁, …t_N-1) в пространстве ^N. Пусть N – четно и равно 2M, а t_j= (2j + 1)* π /(2*N). 
Рассмотрим семейства векторов:
u_k = {cos((2k+1)*t₀), cos((2k+1)*t₁), … , cos((2k+1)*t_N-1)}, (k = 0, 1, … M - 1).
v_k = {sin((2k+1)*t₀), sin((2k+1)*t₁), … , sin((2k+1)*t_N-1)}, (k = 0, 1, … M - 1).
Какое семейство векторов представляет ортонормированный базис в ^N:

Ответ:

(1) u_k.

(2) {u_k, v_k }.

(3) {√(N/2) u_k, √(N/2) v_k }.

(4) {√(2/N) u_k, √(2/N) v_k}.

(5) v_k.

Номер 3

Пусть f(t) – периодическая (почти периодическая) функция с периодом T, который за счет масштабирования времени можно полагать равным π. Измеряя значения функции на интервале 0 <t<π, перейдем к вектору f с координатами: f(t₀, t₁, …t_N-1) в пространстве ^N. Пусть N – четно и равно 2M, а t_j= (2j + 1)* π /(2*N). Какие семейства векторов будут ортогональны в ^N:

Ответ:

(1) w_k(cos(k*t₀), cos(k*t₁), … , cos(k*t_N-1)), (k = 0, 1, … M - 1).

(2) w_k(sin(k*t₀), sin(k*t₁), … , sin(k*t_N-1)), (k = 0, 1, … M - 1).

(3) w_k(cos((2k+1)*t₀), cos((2k+1)*t₁), … , cos((2k+1)*t_N-1)), (k = 0, 1, … M - 1).

(4) w_k(sin((2k+1)*t₀), sin((2k+1)*t₁), … , sin((2k+1)*t_N-1)), (k = 0, 1, … M - 1).

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

Номер 1

Отметьте корректные утверждения:

Ответ:

(1) ДПФ является линейной ортогональной трансформацией, а обратное ДПФ таковой не является.

(2) Обратное ДПФ является линейной ортогональной трансформацией, а прямое ДПФ таковой не является.

(3) Прямое и обратное ДПФ являются линейными ортогональными трансформациями.

(4) Прямое и обратное ДПФ не являются линейными ортогональными трансформациями.

Номер 2

Где используется ДПФ:

Ответ:

(1) При сжатии аудио файлов в формате MP3.

(2) При сжатии больших массивов текстовых данных.

(3) При сжатии графических данных в формате JPEG.

(4) В задачах сортировки массивов.

Номер 3

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

Ответ:

(1) ДПФ совместимо с квантовыми вычислениями и имеет квантовую версию.

(2) Значение коэффициента Фурье определяет насколько велик вклад сигнала с частотой, определяемой коэффициентом, в общее значение сигнала.

(3) В частотном спектре сигнала пики частот соответствуют пиковым значениям коэффициентов Фурье.

(4) При записи аудио сигнала, как правило, большинство коэффициентов Фурье имеют большие значения.

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

Номер 1

Какие утверждения справедливы для быстрого преобразования Фурье (БПФ):

Ответ:

(1) Вектор измерений f длины 2ⁿ разбивается на два вектора g и h длины 2^{n – 1}. В вектор g входят первые 2^{n – 1} элементов вектора f, в h – оставшиеся элементы.

(2) Вектор измерений f длины 2ⁿ разбивается на два вектора g и h длины 2^{n – 1}. В вектор g входят четные 2^{n – 1} элементов вектора f, в h – нечетные элементы.

(3) При счете четных и нечетных коэффициентов Фурье – a_p^g, a_p^h, b_p^g, b_p^hдля ряда значений p необходимо применять рекуррентную формулу.

(4) При счете четных и нечетных коэффициентов Фурье – a_p^g, a_p^h, b_p^g, b_p^hдля всех значений p используется одна и та же схема вычислений.

(5) При счете четных и нечетных коэффициентов Фурье – a_p^g, a_p^h, b_p^g, b_p^hприменяется рекурсивная схема, на каждом шаге которой длина вектора уменьшается вдвое. Рекурсия заканчивается при n = 2, когда коэффициенты вычисляются явным образом.

Номер 2

Какие утверждения справедливы для быстрого преобразования Фурье (БПФ):

Ответ:

(1) БПФ – рекурсивный алгоритм.

(2) Вектор измерений f длины 2M разбивается на два вектора длины M, для каждого из которых рекурсивно вычисляются коэффициенты Фурье.

(3) Число измерений функции f должно быть степенью двойки – N = 2ⁿ.

(4) Число измерений функции f может быть произвольным большим числом.

Номер 3

Быстрое преобразование Фурье (БПФ) позволяет сократить время вычислений в сравнении с ДПФ

Ответ:

(1) В два раза.

(2) В N раз.

(3) В N/ log₂N раз.

(4) В log₂N раз.

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

Номер 1

Какое из приведенных соотношений задает СR_α трансформацию – управляемый поворот по часовой стрелке на угол α:

Ответ:

(1) T|0 = ½ |0> + ½ |1>; T|1 = ½ |0> - ½ |1>;

(2) T|0 = cos(α)|0> - sin(α)|1>; T|1 = sin(α)|0> + cos(α)|1>;

(3) T|0 = √(½ )|0> + √(½) |1>; T|1 = √(½ )|0> - √(½) |1>

(4) T|xy = if(x = 0) |xy>; if(x = 1) |xR_α(y)>.

Номер 2

Какое из приведенных соотношений задает R_α трансформацию – поворот по часовой стрелке на угол α:

Ответ:

(1) T|0 = ½ |0> + ½ |1>; T|1 = ½ |0> - ½ |1>;

(2) T|0 = cos(α)|0> - sin(α)|1>; T|1 = sin(α)|0> + cos(α)|1>;

(3) T|0 = √(½ )|0> + √(½) |1>; T|1 = √(½ )|0> - √(½) |1>;

(4) T|xy = if(x = 0) |xy>; if(x = 1) |xR_α(y)>.

Номер 3

Какое из приведенных соотношений задает H трансформацию Адамара:

Ответ:

(1) T|0 = ½ |0> + ½ |1>; T|1 = ½ |0> - ½ |1>;

(2) T|0 = cos(α)|0> - sin(α)|1>; T|1 = sin(α)|0> + cos(α)|1>;

(3) T|0 = √(½ )|0> + √(½) |1>; T|1 = √(½ )|0> - √(½) |1>;

(4) T|xy = if(x = 0) |xy>; if(x = 1) |xR_α(y)>.

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

Номер 1

Укажите корректные высказывания:

Ответ:

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

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

(3) Трансформация Адамара – это трансформация над двумя кубитами.

(4) Трансформация управляемого поворота – это трансформация над двумя кубитами.

(5) Трансформация поворота – это трансформация над двумя кубитами.

Номер 2

Какие утверждения справедливы относительно квантового преобразования Фурье (КПФ) и быстрого преобразования Фурье (БПФ):

Ответ:

(1) На входе КПФ задается вектор измерений f размерности N = 2ⁿ.

(2) На выходе КПФ вычисляется вектор размерности n, четные элементы которого являются коэффициентами Фурье a_k, нечетные - коэффициентами bk.

(3) Для КПФ дополнительная память не требуется.

(4) КПФ и БПФ имеют одинаковую сложность.

(5) КПФ существенно эффективнее БПФ. Сложность КПФ равна O((log₂N)²), а сложность БПФ равна O(Nlog₂N).

(6) БПФ существенно эффективнее КПФ. Сложность КПФ равна O(N²), а сложность БПФ равна O(Nlog₂N).

Номер 3

Какие утверждения справедливы относительно квантового преобразования Фурье (КПФ):

Ответ:

(1) Для КПФ рекурсивная схема вычислений не может быть реализована.

(2) КПФ использует рекурсивную схему, вычисляя рекурсивно КПФ для nкубитов по результатам КПФ от n – 1 кубита.

(3) КПФ использует n кубитов для записи входа и выхода.

(4) КПФ использует дополнительную память в n кубитов.

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

Номер 1

Какие действия выполняются на четвертом этапе алгоритма КПФ:

Ответ:

(1) К первым n – 1 битам применяется трансформация CNOT.

(2) К первым n – 1 битам применяется последовательность управляемых поворотов CR_α.

(3) К первым n – 1 битам применяется алгоритм КПФ.

(4) К первым n – 1 битам применяется H трансформация Адамара.

Номер 2

Какие действия выполняются на первом этапе алгоритма КПФ:

Ответ:

(1) К первым n – 1 битам применяется трансформация CNOT.

(2) К первым n – 1 битам применяется последовательность управляемых поворотов CR_α.

(3) К первым n – 1 битам применяется алгоритм КПФ.

(4) К первым n – 1 битам применяется H трансформация Адамара.

Номер 3

Сколько этапов выполняется в алгоритме КПФ:

Ответ:

(1) 2

(2) 4

(3) 6

(4) 7

(5) 8

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

Номер 1

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

Ответ:

(1) В алгоритме Шора используется КПФ – квантовое преобразование Фурье, по результатам которого удается определить порядок элемента группы, что и является главной задачей алгоритма.

(2) В результате выполнения измерения определяется значение r, близкое к значению, кратному частоте периодического сигнала.

(3) Наиболее трудоемкая часть алгоритма Шора связана с реализацией алгоритма Эвклида вычисления наибольшего общего делителя для случая нецелых чисел.

(4) Квантовая часть алгоритма Шора завершается получением последовательности r₀, r₁, …r_d, где d – небольшое число.

Номер 2

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

Ответ:

(1) В алгоритме Шора можно выделить часть, выполняемую на квантовом компьютере, и заключительную часть вычислений по определению множителей N, выполняемую на обычном компьютере.

(2) Все вычисления по факторизации N должны выполняться на квантовом компьютере.

(3) Однократное выполнение алгоритма Шора однозначно позволяет определить множители N.

(4) Из-за вероятностной природы квантовых вычислений для получения результата может понадобиться выполнить несколько запусков алгоритма Шора.

(5) Недостатком алгоритма Шора является тот факт, что проверить корректность полученного ответа не представляется возможным.

Номер 3

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

Ответ:

(1) Идея алгоритма в том, чтобы определить M – порядок мультипликативной группы остатков ^*_N, что позволяет выполнить факторизацию N.

(2) Определение M - порядка группы сводится к определению порядка элементов группы, являющихся делителями M.

(3) Используя мощь массивного параллелизма квантовых вычислений, в алгоритме Шора одновременно вычисляются степени g^k элемента группы для экспоненциально большого числа значений k.

(4) Прочитав значение одной из степеней g^h, можно однозначно определить порядок элемента группы, а тем самым и значение порядка всей группы.

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

Номер 1

Укажите корректные высказывания:

Ответ:

(1) На входе алгоритма Шора задается число N, которое требуется факторизовать – разложить на множители.

(2) На входе алгоритма Шора все биты инициализируются нулевыми значениями.

(3) На втором этапе алгоритма Шора используется массивный параллелизм, позволяющий вычислить степени элемента группы g^k для всех k от 0 до 2²ⁿ – 1.

(4) На четвертом этапе алгоритма Шора используется массивный параллелизм, позволяющий выполнить квантовое преобразование Фурье.

(5) Наибольший вклад в эффективность алгоритма Шора оказывает второй этап.

(6) Наибольший вклад в эффективность алгоритма Шора оказывает четвертый этап.

Номер 2

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

Ответ:

(1) 1.

(2) 2.

(3) 3.

(4) 4.

(5) 5.

Номер 3

В алгоритме Шора факторизации числа N, где 2^n-1 <N< 2ⁿ, число n-кубитов равно:

Ответ:

(1) 1.

(2) 2.

(3) 3.

(4) 4.

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

Номер 1

Укажите корректные высказывания:

Ответ:

(1) При описании состояния кубитаa|0> + b|1> коэффициенты a и b можно рассматривать как комплексные числа.

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

(3) При переходе к комплексным числам не все результаты, приведенные в книге, остаются справедливыми.

Номер 2

Укажите корректные высказывания:

Ответ:

(1) Существующие квантовые компьютеры из нескольких кубитов строятся только на основе фотонов.

(2) Различные физические системы используются при построении существующих квантовых компьютеров.

Номер 3

Укажите корректные высказывания:

Ответ:

(1) Алгоритм Шора является единственным примером алгоритма для квантового компьютера, который не может быть реализован на классическом компьютере с той же эффективностью.

(2) Существуют и другие алгоритмы для квантового компьютера, которые не могут быть реализованы на классическом компьютере с той же эффективностью.

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