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

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

Алгоритм, позволяющий по заданному числу x достаточно быстро вычислять ax (mod p), несложен. Обратная же операция - вычисление по заданному b его дискретного логарифма является очень сложной. Это свойство дискретного логарифма используется в его многочисленных криптографических применениях. Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, по своей сложности сравнимы с наиболее быстрыми алгоритмами разложения чисел на множители.

См. также: Алгоритм, Модуль сравнения, Числовые кольца и поля.

16. Комплексные числа (КЧ) - числа вида 

z = x + iy,  (1)

где х и у - действительные (вещественные) числа, а  - так называемая мнимая единица (символ i предложил Л. Эйлер), - число, квадрат которого равен -1. x = Re z называется действительной (вещественной), частью, а у = Im z - мнимой частью КЧ. Если x = 0, КЧ называется мнимым. Если у = 0, имеем действительное (вещественное) число. Таким образом, действительные и мнимые числа - частные случаи КЧ. Множество КЧ образует поле КЧ, которое можно рассматривать как расширение поля действительных чисел.

Форма записи КЧ (1) называется алгебраической.

Все алгебраические действия с КЧ выполняются, как с многочленами, с учетом того, что i2 = -1.

Если отложить по оси абсцисс x, а по оси ординат y , то каждой точке координатной плоскости можно сопоставить КЧ (рис. 1).

Длина радиус-вектора r=|z| = называется модулем, угол φ - фазой КЧ. Числа z = x + iy и z*= x – iy называются сопряжёнными. Комплексно сопряжённые КЧ расположены симметрично относительно действительной оси. Их сумма и произведение – действительные числа.

Рис. 1. Изображение комплексного числа точкой на

координатной плоскости или вектором.

Отметим несколько очевидных свойств комплексно сопряжённых чисел:

- если два раза выполнить комплексное сопряжение, то получится исходное число;

- комплексное число равно своему сопряжённому в том и только в том случае, если оно действительное (мнимая часть равна нулю);

- сопряжённое по отношению к сумме комплексных чисел равно сумме сопряжённых;

- сопряжённое по отношению к произведению комплексных чисел равно произведению сопряжённых.

КЧ можно представить вектором, приложенным к точке O (к началу координат) (рис. 1). Тогда x и y можно считать координатами этого вектора. При такой интерпретации сложение и вычитание КЧ производится по правилам сложения и вычитания векторов. Такая интерпретация широко применяется в электротехнике (в теории переменных токов) и в квантовой механике.

Существует также матричная интерпретация КЧ. Число  z = x + iy можно отождествить с матрицей второго порядка следующего вида:

.

Действия сложения, вычитания и умножения выполняются по обычным правилам матричной алгебры.

Из рис. 1 следует тригонометрическая форма КЧ:

z = r(cos φ + i sin φ). (2)

На основании формулы Эйлера получается показательная форма КЧ:

z = re±iφ . (3)

Отсюда следует формула Муавра: zn = rn (cos nφ + i sin nφ).

См. также: Матрица, Формула Эйлера, Числовые кольца и поля.

17. Корреляция (от лат. correlatio) – статистическая зависимость между случайными величинами, не имеющая, вообще говоря, функционального характера. В отличие от функциональной зависимости рассматривается тогда, когда одна из величин зависит не только от другой, но и от ряда случайных факторов; проявляется в том, что условное распределение одной случайной величины при фиксированной значении другой отличается от её безусловного распределения. При этом изменения значений одной или нескольких из этих величин сопутствуют систематическому изменению значений другой или других величин. Математической мерой корреляции двух случайных величин служит коэффициент корреляции, который можно определить так:

,

где N – число измерений пар случайных величин ξ и ξ*, между которыми предполагается статистическая нефункциональная взаимосвязь.

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

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

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

См. также: Гильбертово пространство, Матрица, Функциональный анализ.

19. Матрица - математический объект, представляющий собой прямоугольную таблицу элементов, находящихся на пересечении строк и столбцов:

A = (1)

Если число строк n равно числу столбцов m, матрица называется квадратной. В математике матрицы применяются для компактной записи систем линейных уравнений. При этом число строк равно числу уравнений, а число столбцов – числу неизвестных. Решение систем уравнений сводится к операциям над матрицами (матричное исчисление).  

Для матриц определены следующие алгебраические операции:

- сложение матриц, имеющих один и тот же размер (все элементы суммарной матрицы равны попарно сумме всех соответствующих элементов матриц);

- умножение матриц одинакового размера (матрицу, имеющую  столбцов, можно умножить справа на матрицу, имеющую  строк по правилу «строка на столбец», т. е. каждый элемент матрицы-произведения равен сумме произведений элементов в соответствующей строке первого множителя и столбце второго);

- умножение на матрицу вектора (по обычному правилу матричного умножения, вектор является частным случаем матрицы);

- умножение матрицы на число (каждый элемент матрицы умножается на это число).

След матрицы – сумма диагональных элементов:

(читается трэйс, от англ. trace - след).

Матрица, состоящая из одной строки или одного столбца, называется соответственно вектор-строкой или вектор-столбцом. Вектор-столбцы и вектор-строки называют просто векторами.

Матрица, состоящая из одного числа, отождествляется с этим числом. Матрица, все элементы которой равны нулю, называются нулевой матрицей и обозначается через 0. Элементы матрицы с одинаковыми индексами называют элементами главной диагонали. Если число строк матрицы равно числу столбцов, то есть m = n, то матрицу называют квадратной порядка n. Квадратные матрицы, у которых отличны от нуля лишь элементы главной диагонали, называются диагональными матрицами и записываются так:

A =.

Если все элементы a i i диагональной матрицы равны 1, то матрица называется единичной и обозначается буквой Е:

   .

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

Пусть дана матрица (1).

Переставим в ней строки и столбцы. Получим матрицу

AT = ,

которая будет транспонированной по отношению к матрице А. В частности, при транспонировании вектора-столбца получается вектор-строка и наоборот.

Произведением матрицы А на действительное число b называется матрица, элементы которой получаются из соответствующих элементов матрицы А умножением на число b: b A = (b a i j ).

Суммой двух матриц А = (a i j) и B = (b i j) одного размера называется матрица C = (c i j) того же размера, элементы которой определяются по формуле c i j = a i j + b i j.

Произведение АВ матрицы А на матрицу В определяется только в предположении, что число столбцов матрицы А равно числу строк матрицы В.