Математические основы квантовой информатики (стр. 1 )

Министерство образования и науки Российской Федерации

Псковский государственный университет

МАТЕМАТИЧЕСКИЕ ОСНОВЫ

КВАНТОВОЙ ИНФОРМАТИКИ

Учебный словарь-справочник

П с к о в

Издательство ПсковГУ

2013

УДК 681.3+51 (075.8)

ББК 22.1 я73+32.973я73

В 363

Рекомендовано к изданию кафедрой общей физики ПсковГУ

Рецензенты:

– , доктор физ.-мат. наук, проф. (ПсковГУ);

– , канд. техн. наук, профессор (ПсковГУ)

В 363 Математические основы квантовой информатики: Учебный словарь-справочник. – Псков: Издательство ПсковГУ, 2013. – 59 с.

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

УДК 681.3+51 (075.8)

ББК 22.1 я73+32.973я73

ISBN

© , 2013

© Псковский государственный университет, 2013

Предисловие

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

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

- квантовая криптография (включающая плотную кодировку);

- квантовая телепортация.

К квантовой информатике следует отнести также квантовую теорию сознания, рассматривающую особую роль наблюдателя в квантовой механике. К этому направлению относятся классические работы В. Паули, известного швейцарского психолога и философа Карла Юнга, а в наши дни - работы проф. . Поэтому в список наук, на перекрёсте которых рождается квантовая информатика, должна быть включена также и психология.

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

Предлагаемая брошюра должна, по замыслу автора, в какой-то мере восполнить этот пробел. От читателя требуется лишь знание таких понятий, как производная, дифференциал, интеграл, непрерывность и некоторых других, предусмотренных программой по математике. Каждый пункт брошюры – это маленькая статья, которую можно читать независимо от других. В некоторых случаях в конце такой статьи приводится список литературы, включающий интернет-ресурсы. Для читателей, уже прошедших курс информатики, некоторые статьи (Алгоритм, Позиционная система счисления, Теория информации и др.) будут полезным напоминанием.

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

Содержание Стр.

1.  Аксиома Архимеда ………………………………………. 5

2.  Алгоритм ………………………………………………….. 5

3.  Алгоритм Шора …………………………………………... 10

4.  Асимптотическое поведение функций ………………….. 11

5.  Базис ……………………………………………………….. 12

6.  Булева алгебра …………………………………………….. 13

7.  Вектор состояния …………………………………………. 15

8.  Векторное исчисление ……………………………………. 14

9.  Векторное произведение ………………………………….. 15

10.  Вектор состояния ………………………………………….. 16

11.  Вероятность …………………………………………………16

12.  Волновая функция ……………………………………….... 18

13.  Гильбертово пространство …………………………………18

14.  Дедекиндово сечение ……………………………………… 21

15.  Дискретное логарифмирование …………………………… 22

16.  Комплексные числа ………………………………………… 23

17.  Корреляция ………………………………………………….. 25

18.  Линейная алгебра …………………………………………… 25

19.  Матрица ……………………………………………………… 26

20.  Модуль сравнения …………………………………………... 30

21.  Неархимедова геометрия …………………………………… 31

22.  Норма вектора ……………………………………………….. 31

23.  O-нотация …………………………………………………….. 32

24.  Оператор ……………………………………………………… 33

25.  Ортогональные функции …………………………………….. 37

26.  Ортогональный базис ………………………………………… 37

27.  Ортонормированный базис ………………………………….. 37

28.  Позиционная система счисления ……………………………. 38

29.  Преобразование Адамара ……………………………………. 41

30.  Преобразование Фурье ………………………………………. 44

31.  Проектор ……………………………………………………… 45

32.  p-адические числа ……………………………………………. 45

33.  Скалярное произведение …………………………………….. 50

34.  Скобки Пуассона ……………………………………………... 51

35.  Теория информации ………………………………………….. 52

36.  Унитарное преобразование ………………………………….. 53

37.  Уравнения Гамильтона ……………………………………..... 54

38.  Факторизация …………………………………………………. 54

39.  Формула Муавра ……………………………………………… 54

40.  Формула Эйлера ……………………………………………… 54

41.  Функциональный анализ …………………………………….. 55

42.  Числовые кольца и поля ……………………………………… 56

«…любой естественнонаучной теорией мы

не овладеваем до тех пор, пока не выделим

в ней математическое ядро и не раскроем

его полностью. Без математики невозможны

современная астрономия и физика; эти нау-

ки в своих теоретических частях растворя-

ются в математике». 

Давид Гильберт,

«Познание природы и логика»

Математические основы квантовой информатики

1. Аксиома Архимеда – утверждение сформулированное Архимедом в 3 веке до Р. Х. (а ещё ранее Евдоксом Книдским). Пусть имеется два отрезка, причём один короче другого: a < b. Тогда, отложив достаточное число раз меньший из двух заданных отрезков, всегда можно получить отрезок, превосходящий больший из них: a∙n > b, где n – достаточно большое целое число. Аналогично аксиому можно сформулировать для площадей, объёмов, положительных чисел и т. д. Давид Гильберт называл аксиому Архимеда аксиомой непрерывности. Утверждение Архимеда казалось самоочевидным до тех пор, пока в конце 19 в. не обнаружили существование величин, по отношению к которым эта аксиома не выполняется. Такие математические структуры называются неархимедовыми. Интерес к таким структурам возник в конце 19 века в связи с открытием p-адических чисел. Какое отношение имеет аксиома Архимеда к физике? В микромире (на планковских масштабах) меняется метрика пространства и времени. Обычная квантовая механика и аксиома Архимеда оказываются при таких условиях неприменимыми. Проф. (Математический институт им. ) предложил использовать здесь неархимедову геометрию и р-адические числа.

См также: Неархимедова геометрия, p-адические числа.

2. Алгоритм - набор предписаний (инструкций) исполнителю, описывающих порядок действий для достижения результата (решения задачи) за конечное число шагов. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от латинского написания имени аль-Хорезми - выдающегося математика средневекового Востока.

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

Курт Гёдель (1906-1978) – австрийский математик, логик и философ

В связи с этим возникло представление о невозможности алгоритмического разрешения ряда математических проблем. Была осознана необходимость стандартизации понятия «алгоритм». Первые стандартизованные варианты этого понятия были разработаны в 30-х годах 20 века в работах английского математика Алана Тьюринга, считающегося отцом информатики, а также американских учёных А. Чёрча и Э. Поста.

 

Алан Тьюринг (1912-1954) – английский математик, логик и криптограф

Функция, связывающая входные данные алгоритма с количеством элементарных операций, называется функцией трудоёмкости. Одним из упрощённых видов анализа алгоритмов, используемых на практике, является асимптотический анализ. Цель такого анализа - сравнение затрат времени и других ресурсов при реализации различных алгоритмов, предназначенных для решения одной и той же задачи, при больших объёмах входных данных. В информатике и теории алгоритмов вводится оценка трудоёмкости алгоритма, называемая «вычислительной сложностью». Так называют функцию, определяющую зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Такая оценка позволяет определить, как быстро растёт трудоёмкость алгоритма с увеличением объёма данных.

В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Так, оценка  представляет собой верхнюю асимптотическую оценку трудоёмкости алгоритма. Мы говорим, что функция сложности алгоритма  , если f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. Здесь n - величина объёма входных данных или длина входа.