Министерство образования и науки РФ
Федеральное государственное бюджетное
образовательное учреждение
высшего профессионального образования
Российский экономический университет
им. Г.В. Плеханова
Факультет математической
экономики и информатики
Кафедра информатики
Реферат по
дисциплине
«Операционные
системы»
на тему:
«Квантовые компьютеры»
Выполнила: студентка 2 курса
группы 427
Вавилова Д.Д.
Проверила: д.п.н., проф. Шихнабиева
Т.Ш.
г. Москва
2014г
Содержание
Введение
Специалисты предсказывают,
что вскоре на смену обычным компьютерам
придут квантовые, по мощности превосходящие
современные вычислительные системы в
несколько раз. Но что же из себя представляют
квантовые компьютеры?
История возникновения квантового
компьютера
В 1982 году Фейнман написал
статью, в которой рассмотрел два вопроса.
Он подошел к процессу вычисления как
физик: есть чисто логические ограничения
на то, что можно вычислить (можно придумать
задачу, для которой вообще нет алгоритма,
можно придумать задачу, для которой любой
алгоритм будет долго работать). А есть
ли какое-нибудь физическое ограничение
на функционирование компьютера, которое
накладывает некие запреты на реализуемость
алгоритмов? И Фейнман показал, что термодинамических
ограничений нет. Это означает, что вычисления
можно сделать обратимым образом. Собственно,
Фейнмана это и заинтересовало: ведь реальное
вычисление на реальном компьютере необратимо.
И полученный им результат состоит в том,
что можно так переделать любое вычисление
- без особой потери эффективности, - чтобы
оно стало обратимым.
И в этой же работе Фейнман
обратил внимание на то, что если у нас
имеется устройство квантовое, то есть подчиняющееся
законам квантовой механики, то его вычислительные
возможности совершенно не обязательно
должны совпадать с возможностями обычного
устройства. Возникают некоторые дополнительные
возможности. Но пока непонятно, позволяют
они получить какой-то выигрыш или нет.
Фактически, он и поставил своей статьей
такой вопрос.
Манин в конце семидесятых
годов написал две популярные книжки по
логике - «Вычислимое и невычислимое»
и «Доказуемое и недоказуемое», и в одной
из них есть сюжет про квантовые автоматы,
где он говорит о некоторых кардинальных
отличиях этих автоматов от классических.
В середине восьмидесятых
годов появились работы Дойча (D. Deutsch),
Бернстайна и Вазирани (Е. Bernstein, U. Vazirani),
Яo (A. Уао). В них были построены формальные
модели квантового компьютера - например,
квантовая машина Тьюринга.
Следующий этап - статья Шора
(Р.W. Shor) 1994 года. Шор построил квантовый
(то есть реализуемый на квантовом компьютере)
алгоритм факторизации (разложения целых
чисел на множители - используется в том
числе для вскрытия зашифрованных сообщений).
Считается, что быстрого алгоритма решения
этой задачи не существует. Более того,
гарантией надежности большинства существующих
шифров является именно сложность решения
задачи факторизации или одной из родственных
ей теоретико-числовых задач, например
- дискретного логарифма. И вдруг выясняется,
что на квантовом компьютере эта задача
имеет всего лишь кубическую сложность.
Перед квантовым компьютером классические
банковские, военные и другие шифры мгновенно
теряют всякую ценность. Впрочем, выясняется,
что не только классическая, но и квантовая
криптография часто не способна противостоять
квантовой криптоаналитике (науке о расшифровке).
Некоторые важные криптографические протоколы
рушатся при переходе к квантовым вычислениям.
Точнее, гарантией их надежности является
отныне не сложность тех или иных алгоритмов,
а сложность задачи создания квантового
компьютера.
Таким образом возникает новая
отрасль вычислений – квантовые вычисления.
Сейчас, это предмет чрезвычайно модный
в математике и физике, как теоретической,
так и экспериментальной. Судя по всему,
именно интерес стимулировал первопроходцев
- Ричарда Фейнмана, написавшего пионерскую
работу, в которой ставился вопрос о вычислительных
возможностях устройств на квантовых
элементах; Дэвида Дойча, формализовавшего
этот вопрос в рамках современной теории
вычислений; и Питера Шора, придумавшего
первый нетривиальный квантовый алгоритм.
Устройство и принципы работы
квантовых компьютеров
Бит как
минимальная единица информации имеет
два «базисных» состояния: 1 и 0. Изменения
этих состояний легко контролировать:
«выключатель» может принимать одно из
двух положений (вкл-выкл), объекты могут
либо находиться в данном месте, либо не
находиться в нем. Поэтому многие объекты
физического мира можно перенести в мир
виртуальный с помощью множества комбинаций
нулей и единиц. Как известно, все тексты,
интерфейсы, сайты, фотографии, операционные
системы и другие виртуальные объекты
представляют собой сложный набор битов.
Квантовые
же компьютеры двоичной системой координат
не ограничены: вычисления здесь производятся
с помощью кубитов, которые могут находиться
одновременно во всех возможных своих
состояниях. Результат вычисления получается
при измерении состояния квантового процессора
после совершения им операций особого
вида (так называемых «унитарных операций»)
над кубитами. Уже описаны десятки возможных
алгоритмов работы подобного компьютера,
разрабатываются и особые языки программирования.
Принципиальная схема работы
любого квантового компьютера может быть
представлена следующим образом (см. рис.1.1).
Рис. 1.1. Схематическая структура
квантового компьютера
Основной его частью является
квантовый регистр - совокупность некоторого
числа кубитов. До ввода информации в компьютер
все кубиты регистра должны быть приведены
в основные базисные состояния. Эта операция
называется подготовкой начального состояния
или инициализацией. Далее каждый кубит
подвергается селективному воздействию.
При вводе информации в квантовый
компьютер состояние входного регистра,
с помощью соответствующих импульсных
воздействий преобразуется. В таком виде
информация далее подвергается воздействию
квантового процессора, выполняющего
последовательность квантовых логических
операций. К некоторому моменту времени
в результате преобразований исходное
квантовое состояние становится новой
суперпозицией, которая и определяет результат
преобразования информации на выходе
компьютера.
Совокупность всех возможных
операций на входе данного компьютера,
формирующих исходные состояния, а также
осуществляющих унитарные локальные преобразования,
соответствующие алгоритму вычисления,
способы подавления потери когерентности
- так называемой декогерентизации (decoherence)
квантовых состояний и исправления случайных
ошибок, играют здесь ту же роль, что и
"программное обеспечение" (software)
в классическом компьютере.
Теперь обратимся к аппаратной
части квантового компьютера. При выборе
конкретной схемы любого квантового компьютера
необходимо решить три вопроса: во-первых,
выбрать физическую систему, представляющую
требуемую систему кубитов, во-вторых,
определить физический механизм, определяющий
взаимодействие между кубитами, в-третьих,
определить способы селективного управления
кубитами и измерения их состояния на
выходе. Все это вместе взятое аналогично
"аппаратному обеспечению" (hardware)
классического компьютера.
Типы квантовых компьютеров
Можно выделить два типа квантовых
компьютеров. И те, и другие основаны на
квантовых явлениях, только разного порядка.
Представителями первого типа
являются, например, компьютеры, в основе
которых лежит квантование магнитного
потока на нарушениях сверхпроводимости
- Джозефсоновских переходах. На эффекте
Джозефсона уже сейчас делают линейные
усилители, аналого-цифровые преобразователи,
СКВИДы и корреляторы.
Другой тип квантовых компьютеров,
называемых еще квантовыми когерентными
компьютерами, требует поддержания когерентности
волновых функций используемых кубитов
в течение всего времени вычислений - от
начала и до конца (кубитом может быть
любая квантомеханическая система с двумя
выделенными энергетическими уровнями).
Именно последний тип устройств имеется
в виду, когда говорят о квантовых компьютерах.
Область применения квантовых
компьютеров
Существуют задачи, решение
которых с помощью обычного компьютера
очень трудно найти, но легко проверить.
Время, затрачиваемое на решение таких
задач, растет экспоненциально по отношению
к числу битов, которыми представлена
задача. Именно здесь может пригодиться
естественный параллелизм квантовых вычислений.
Одной из областей применения
квантовых компьютеров может стать квантовая
криптография и квантовый криптоанализ.
Другая вершина, которую должен покорить
квантовый компьютер, — это поиск записи
в базе данных. Квантовые компьютеры будут
справляться с этой задачей гораздо быстрее
современных компьютеров.
И, наконец, самое парадоксальное
применение квантовых компьютеров — это
моделирование других квантовых систем.
Ведь если бы такое моделирование было
сегодня легко реализуемо, то с одной стороны,
исчерпали бы себя проблемы с конструированием
квантовых компьюетров, а с другой — Ричард
Фейнманн, возможно, не написал бы своей
статьи, породившей такой интерес к данным
компьютерам.
Одним словом, создание квантового
компьютера позволило бы решать многие
задачи проще, быстрее и с меньшей затратой
ресурсов.
Отличительные особенности
квантовых компьютеров
Если классическая машина Тьюринга способна
одновременно исполнять лишь одно вычисление,
то квантовая занимается несколькими
вычислениями параллельно. Сегодняшние
компьютеры работают по тому же принципу,
что и нормальные машины Тьюринга – с
битами, которые находятся в одном из двух
состояний: 0 или 1. У квантовых компьютеров
таких ограничений нет: информация в них
зашифрована в квантовых битах (кубитах),
которые могут содержать суперпозиции
обоих состояний.
И квантовые, и классические
компьютеры обрабатывают данные, которые
закодированы единицами и нулями. Разница
в том, что в классическом компьютере значение
каждого бита всегда известно. Значение
кубитов — элементов для хранения информации,
из которых состоит квантовый компьютер,
может быть неопределённым и соответствовать
сразу и единице, и нулю, причём с различной
вероятностью для того и другого.
Во время работы квантового
компьютера отдельные кубиты связаны
между собой эффектом квантовой запутанности
(entanglement). Несколько связанных кубитов
с неопределённым значением содержат
не одно число, а все возможные числа, умещающиеся
в ячейке такой разрядности. Иными словами,
квантовый компьютер одновременно рассматривает
все решения задачи, и правильные, и ошибочные.
Достижения и перспективы развития квантовых
компьютеров
2000 г. - В марте ученые из Национальной
лаборатории объявили о создании 7-кубитного
квантового компьютера в одной единственной
капле жидкости.
2001 г. - Демонстрация вычисления
алгоритма Шора специалистами из IBM и Стэнфордского
университета на 7-кубитном квантовом
компьютере.
2005 г. - В институте квантовой
оптики и квантовой информации при Иннсбрукском
университете впервые удалось создать
кубайт (сочетание 8 кубитов) с помощью
ионных ловушек.
2007 г. - Канадская компания
D-Wave продемонстрировала первый 16-кубитный
квантовый компьютер, способный решать
целый ряд задач и головоломок, типа судоку.
С 2011 года D-Wave предлагает
за $11 млн долларов квантовый компьютер
D-Wave One с 128-кубитным чипсетом, который
выполняет только одну задачу – дискретную
оптимизацию.
По прогнозу футурологов-исследователей
из компании Cisco Systems, «полноценный» квантовый
компьютер должен появиться к середине
2020 года. Компьютер будущего стоимостью
в $1000 может быть таким же мощным, как человеческий
мозг. В IBM говорят, что ее специалисты
смогут создать квантовый компьютер через
10 – 15 лет. Внешне такие системы будут
напоминать традиционные серверные станции
с платами внутри. Но для их полноценной
работы, скорее всего, придется охлаждать
их модули на сотни градусов по Цельсию:
при ультранизких температурах, когда
способность к смене
позиций атомов и групп атомов снижается,
контролировать «квантовые эффекты» проще.
Аналитическая
компания Gartner включила квантовые компьютеры
в список перспективных технологий, которые
«выстрелят» в ближайшие десять лет. Основатели
компании Parallels, видимо, разделяют это
мнение, потому что недавно они основали
фонд, который будет инвестировать в развитие
квантовых технологий. Тем временем Google
и Lockheed Martin тратят миллионы на устройства,
использующие для работы квантовые эффекты.
В Квантовой лаборатория по
изучению искусственного интеллекта,
расположенной в Исследовательском центре
NASA им. Эймса будет установлен квантовый
компьютер от D-Wave Systems. Целью исследователей
будет изучение того, как квантовые компьютеры
могут помочь улучшить машинное обучение.
В Google считают, что квантовые компьютеры
помогут изменить поиск в Сети и технологию
распознавания голоса, тогда как учёные
NASA надеются использовать тот же подход
для моделирования распространения заболеваний
и изменения климата.
В 2011 году корпорация Lockheed Martin, гигант
военно-промышленного комплекса США, объявила
о приобретении 128-кубитной машины D-Wave
за 10 миллионов долларов. В марте 2013 года
в Lockheed Martin решили купить следующую модель
квантового компьютера D-Wave.
В D-Wave в итоге пошли на попятную и опубликовали
пару научных работ о своей машине. Попутно
стало ясно, что это, во-первых, не квантовый
компьютер в самом распространённом понимании
этого слова, а во-вторых, кубиты, о которых
идёт речь в рекламе компании, строго говоря,
не вполне кубиты. В основе машины D-Wave
лежит охлаждённая до -273 градусов по Цельсию
микросхема с решёткой, построенной из
сверхпроводящих квантовых интерферометров.
Именно их в компании называют кубитами.
Значение кубитов D-Wave, как и значение кубитов
в настоящем квантовом компьютере, может
быть неопределённым. Машина D-Wave не годится
для алгоритмов, которые используют квантовые
вентили. Ни алгоритм Шора, ни алгоритм
Гровера на ней не пойдут. Вместо этого
она использует для работы совершенно
иной принцип — так называемые адиабатические
квантовые вычисления. Это значительно
ограничивает её возможности, но позволяет
не беспокоиться о декогеренции и других
проблемах, сопровождающих обычные квантовые
вычислители. Адиабатические квантовые
компьютеры представляют собой специализированные
устройства, предназначенные для решения
единственной задачи: поиска оптимального
решения функции. Выполнять операции над
отдельными кубитами они не способны,
но в данном случае этого и не требуется.