Классификация и организация вычислительных систем. Михайлов Б.М - 117 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

В середине 80-х годов XX в. появились работы Д. Дойча, Е. Бернстайна и У.
Вазирини, А. Яо, в которых были описаны модели квантового компьютера Например,
была описана модель квантовой машины Тьюринга. Появившаяся в 1994 г. статья П.
Шора (P. W. Shor, сотрудник фирмы Lucent Technologies, мате матик) вызвала
лавинообразный поток публикаций о квантовых вычислениях (KB). П. Шор
предложил квантовый алгоритм, позволяющий производить бы струю факторизацию
больших чисел. Напомним, что все известные алгоритмы для обычного компьютера —
экспоненциальные, т. е. время их вычисления растет как экспонента от числа знаков в
записи факторизуемого числа. Так, например, факторизация 129-разрядного числа
потребовала бы 500 MIPS-лет или 8 месяцев непрерывной работы системы из 1600
рабочих станций, объединенных через Интернет. А факторизация числа в 500 разрядов
потребует времени, превышающего возраст Вселенной, и одновременную работу всех
существующих в мире компьютеров. Алгоритм П. Шора, по сравнению с другими, дает
многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем
значительнее выигрыш в скорости.
В 1996 г. коллега П. Шора Л. Гровер (L. Grover) предложил квантовый алго
ритм быстрого поиска в неупорядоченной базе данных. Этот алгоритм позволяет не
только ускорить процесс поиска, но и увеличить примерно в 2 раза число пара метров,
учитываемых при поиске оптимальным способом.
Независимо от П. Шора наш ученый А. Китаев (ИТФ им. Л. Д. Ландау) также
разработал квантовый алгоритм для решения задачи о дискретном логарифме и
некоторых других более общих задач.
Именно середину 90-х годов XX в. можно считать временем рождения новой
отрасли вычислений — квантовых вычислений (KB), т. е. вычисления на кван-
товом компьютере (КК).
Хотя самого КК еще не существует, но уже имеются подходы для его по-
строения.
Прежде чем рассматривать структуры КК, кратко рассмотрим суть КВ. В KB, как
и в обычных компьютерах, оперируют понятием бит, которое в этом случае носит
название кубит (qubit, quantum bit). Если обычный бит — это пространство
состояний из двух элементов 0 и 1, то кубит — это двумерное комплексное
пространство. В квантовой системе можно выполнять только унитарные пре-
      В середине 80-х годов XX в. появились работы Д. Дойча, Е. Бернстайна и У.
Вазирини, А. Яо, в которых были описаны модели квантового компьютера Например,
была описана модель квантовой машины Тьюринга. Появившаяся в 1994 г. статья П.
Шора (P. W. Shor, сотрудник фирмы Lucent Technologies, мате матик) вызвала
лавинообразный поток публикаций о квантовых вычислениях (KB). П. Шор
предложил квантовый алгоритм, позволяющий производить бы струю факторизацию
больших чисел. Напомним, что все известные алгоритмы для обычного компьютера —
экспоненциальные, т. е. время их вычисления растет как экспонента от числа знаков в
записи факторизуемого числа. Так, например, факторизация 129-разрядного числа
потребовала бы 500 MIPS-лет или 8 месяцев непрерывной работы системы из 1600
рабочих станций, объединенных через Интернет. А факторизация числа в 500 разрядов
потребует времени, превышающего возраст Вселенной, и одновременную работу всех
существующих в мире компьютеров. Алгоритм П. Шора, по сравнению с другими, дает
многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем
значительнее выигрыш в скорости.
      В 1996 г. коллега П. Шора Л. Гровер (L. Grover) предложил квантовый алго
ритм быстрого поиска в неупорядоченной базе данных. Этот алгоритм позволяет не
только ускорить процесс поиска, но и увеличить примерно в 2 раза число пара метров,
учитываемых при поиске оптимальным способом.
      Независимо от П. Шора наш ученый А. Китаев (ИТФ им. Л. Д. Ландау) также
разработал квантовый алгоритм для решения задачи о дискретном логарифме и
некоторых других более общих задач.
      Именно середину 90-х годов XX в. можно считать временем рождения новой
отрасли вычислений — квантовых вычислений (KB), т. е. вычисления на кван-
товом компьютере (КК).
      Хотя самого КК еще не существует, но уже имеются подходы для его по-
строения.
      Прежде чем рассматривать структуры КК, кратко рассмотрим суть КВ. В KB, как
и в обычных компьютерах, оперируют понятием бит, которое в этом случае носит
название кубит (qubit, quantum bit). Если обычный бит — это пространство
состояний из двух элементов 0 и 1, то кубит — это двумерное комплексное
пространство. В квантовой системе можно выполнять только унитарные пре-

Страницы