Множество задач, для которых существуют «быстрые» алгоритмы решения, и время работы которых полиномиально зависит от размера входных данных, относят к классу P (от англ. polynomial).

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

См. также: Асимптотическое поведение функций, O-нотация, Унитарное преобразование, Факторизация.

Литература

1. Теория алгоритмов. Введение в теорию алгоритмов.

-Режим доступа: http://th-algoritmov. narod. ru/1.htm

2. Машина Тьюринга и алгоритмически неразрешимые проблемы. –Режим доступа: http://th-algoritmov. narod. ru/3.htm

3. Оценка времени исполнения. Символ O (…).

-Режим доступа: http://algolist. manual. ru/misc/o_n. php

4. Теория алгоритмов (конспект лекций). - Режим доступа: http://www. nsu. ru/education/podzorov/Alg/Course. pdf

3. Алгоритм Шора – алгоритм, с помощью которого решается проблема факторизации. Был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

НЕ нашли? Не то? Что вы ищете?

Основан на возможности быстрого вычисления с высокой точностью собственных значений унитарного оператора, если есть возможность эффективно вычислить любые его степени. В качестве такого оператора берётся умножение на  по модулю . Этот оператор действует в 2^n-мерном пространстве, где 2^{n-1}< N\le 2^n. Базисный вектор, соответствующий числу , преобразуется в базисный вектор, соответствующий числу xa(mod N). Далее вычисляется такое , что x^n=1(mod N), что позволяет (с высокой вероятностью) разложить  на множители на обычном компьютере. Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью, причём вероятность ошибки может быть уменьшена при повторном использовании алгоритма.

Алгоритма Шора можно разделить на 2 этапа:

- классическое сведение разложения на множители к нахождению периода некоторой функции;

- квантовое нахождение периода этой функции.

Пусть:

M- нечётное число, не являющееся степенью простого числа, которое хотим разложить на множители;
N- размер используемого основного регистра памяти.

Известно, что битовый размер этой памяти  примерно в 2 раза больше размера , а точнее, M^2<N=2^n<2M^2.
t- случайный параметр, такой что 1< t <M и НОД (t, M) = 1, НОД - наибольший общий делитель.

Отметим, что , ,  – фиксированы. В алгоритме Шора используется стандартный способ сведения задачи разложения к задаче поиска периода функции для случайно подобранного числа t.

Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. Например, криптографический алгоритм RSA (первые буквы фамилий Rivest, Shamir и Adleman) использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA - найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы.

См. также: Алгоритм, Модуль сравнения, O-нотация, Факторизация.

Литература

1. Квантовые вычисления. - Казань: 2007.

-Режим доступа: http://old. kpfu. ru/eng/departments/ktk/RESOURCE/posobie. pdf

2. Физика квантовой информации.

-М.: Постмаркет, 2002. - 376 с.

-Режим доступа: http://quantmag. ppole. ru/Books/boumeister. pdf

4. Асимптотическое поведение функций. При исследовании поведения функции вблизи некоторой точки x0 (или при x → ∞) удобно заменить исследуемую

функцию на более простую (или более изученную) функцию, которая в окрестности исследуемой точки x0 с малой относительной погрешностью воспроизводит значения изучаемой функции. Так, функция sin x или tg x при x → 0 ведёт себя как функция x, (x + 1)/x при x → ∞ - как 1, ln (1 + x) при x → 0 – как x и т. д. Сама функция может быть не определена в точке x0 (или при x → ∞), и её поведение в окрестности этой точки называется асимптотическим. Для сравнения асимптотического поведения функций используются обозначения: «O» большое и «o» малое. Пусть f(x) и g(x) - две функции, определенные в некоторой проколотой окрестности точки x_0 (проколотой называется окрестность, из которой исключена сама точка x0), и в этой окрестности  не обращается в нуль. Говорят, что:

а)  является «O» большим от  при x\to x_0, если существует такая константа C>0, что для всех  из некоторой окрестности точки x_0 имеет место неравенство

|f(x)| \leqslant C |g(x)|;

б)  является «о» малым от  при x\to x_0, если для любого \varepsilon>0 найдется такая проколотая окрестность U_{x_0}' точки x_0, что для всех x\in U_{x_0}' имеет место неравенство

|f(x)| < \varepsilon |g(x)|.

Иначе говоря, в первом случае отношение |f|/|g| в окрестности точки x_0 ограничено сверху, а во втором оно стремится к нулю при x\to x_0.

См. также: Алгоритм.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15