Специфика применения

Примеры квантовых алгоримов

Вычисление

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

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

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2ⁿ базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической.

1) Практически (квантовый) алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоримов.

2) Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log(n) время.

Может показаться, что квантовый компьютер — это разновидность аналоговой вычислительной машины. Но это не так: по своей сути это цифровое устройство, но с аналоговой природой.

Основные проблемы, связанные с созданием и применением квантовых компьютеров:

• необходимо обеспечить высокую точность измерений;
• внешние воздействия могут разрушить квантовую систему или внести в неё искажения.

Алгоритм Шора - Приложения к криптографии

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

Тем самым становится возможной атака на алгоритм RSA. алгоритм RSA основан на том, что НЕИЗВЕСТНЫ быстрые алгоритмы разложение чисел на множители. Он широко применяется при защите информации.(например в банках и электроных карточках). Пока квантовая ВМ разложила 15 на 3 и 5.

Продолжение по Цилькер, Орлов.

Напоминаем:

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

В свою очередь, вычислительную систему (ВС) определим как совокупность взаимо-

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

подготовки и решения задач пользователей.

Таким образом, формально отличие ВС от ВМ выражается в количестве вы-

числителей. Множественность вычислителей позволяет реализовать в ВС парал-

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

Замечание

Условимся, что сказанное относительно вычислительных машин распространяется и на ВС с традиционными процессорами. В тех случаях, когда излагаемый материал справедлив лишь по отношению ВС, структура или принцип действия которых отличается от традиционных, будет действовать термин «вычислительная система».

Дата добавления: 2014-01-07