Квантовые компьютеры

Федеральное агентство  по образованию РФ

ГОУ ВПО

«Вологодский государственный технический университет»

Кафедра автоматики и  вычислительной техники

 

 

Реферат

По дисциплине «введение  в специальность»

 

Квантовые компьютеры

 

 

 

 

 

 

Выполнил студент группы

 ЭМ-11 Гунько И. Н.

Принял: Сердюков Н.А.

 

 

 

 

 

 

Г. Вологда 2009

Содержание.

 

 

Введение

Гипотеза Макса Планка, высказанная им в 1900 году, о том, что любая энергия поглощается или испускается только порциями, которые состоят из целого числа квантов с энергией ε таких, что эта энергия пропорциональна частоте ν с коэффициентом пропорциональности, положила основу и образовала науку известною сейчас как Квантовая механика, особо бурно развивающуюся в двадцатом веке. Одна из особенностей квантовой механики - это трудность её понимания для обывателя. Во-первых, некоторые свойства квантовых систем кажутся нам непривычными (невозможность одновременно измерить координату и импульс, несуществование траектории частицы, вероятностное описание, дискретность наблюдаемых величин). Это вовсе не значит, что они неверны: это означает, что наша повседневная интуиция никогда не сталкивалась с такими процессами. Во-вторых, в квантовой механике очень сложный математический аппарат зачастую плохо понятный человеку профессия которого не связана с квантовыми вычислениями. Но это делает Квантовую механику невероятно увлекательной. Квантовые компьютеры, о коих пойдёт речь в этом реферате, есть практическое применение Квантовой механики, и более того, создаются квантовые компьютеры в  первою очередь для квантовых расчетов. И действительно, еще пять лет назад о квантовых компьютерах знали разве что специалисты в области квантовой физики. Однако в последние годы количество публикаций в Интернете и в специализированных изданиях, посвященных квантовым вычислениям, возрастало лавинообразно. Тема квантовых вычислений стала популярной и вызвала множество различных мнений, далеко не всегда соответствующих действительности. В связи с трудностью математического аппарата Квантовой механики и физического понятия процессов, происходящих в микромире, я постараюсь не вдаваться в математическое описание происходящих процессов. В этом реферате я попытаюсь как можно более доступно рассказать о том, что же такое квантовый компьютер и на какой стадии находятся современные разработки в этой области.  

1. Предпосылки создания квантового компьютера

1.1. Недостатки стандартных кремневых компьютеров

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

По просьбе  журнала “Electronics” Гордон Мур написал статью, приуроченную к 35-й годовщине издания. Он сделал прогноз относительно того, как будут развиваться полупроводниковые устройства в течение ближайших десяти лет. Проанализировав темпы развития полупроводниковых устройств и экономические факторы за прошедшие шесть лет, то есть начиная с 1959 года, Гордон Мур предположил, что к 1975 году количество транзисторов в одной интегральной микросхеме составит 65 тыс.

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

Впоследствии  в закон Мура были внесены коррективы (чтобы соотнести его с реальностью), но смысл от этого не поменялся: количество транзисторов в микросхемах увеличивается экспоненциально. Естественно, увеличение плотности размещения транзисторов на кристалле возможно лишь за счет сокращения размеров самих транзисторов. В связи с этим уместен вопрос: до какой степени можно уменьшать размеры транзисторов? Уже сейчас размеры отдельных элементов транзисторов в процессорах сопоставимы с атомарными, например ширина диоксидного слоя, отделяющего диэлектрик затвора от канала переноса заряда, составляет всего несколько десятков атомарных слоев. Понятно, что существует чисто физический предел, делающий невозможным дальнейшее уменьшение размеров транзисторов. Даже если предположить, что в будущем они будут иметь несколько иную геометрию и архитектуру, теоретически невозможно создать транзистор или подобный ему элемент с размером менее    10^-8 см (диаметр атома водорода) и рабочей частотой более 10¹⁵ Гц (частота атомных переходов). А потому, хотим мы того или нет, настанет тот день, когда закон Мура просто перестанет действовать (если, конечно, его в очередной раз не подкорректируют до неузнаваемости).

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

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

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

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

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

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

Если требуется  разложить на простые множители  число х, имеющее n знаков в двоичной записи, то очевидный способ решения этой задачи заключается в том, чтобы попробовать последовательно разделить его на числа от 2 до   Для этого придется перебрать 2^n/2 вариантов. К примеру, если рассматривается число, у которого 100 000 знаков (в двоичной записи), то потребуется перебрать 3x10¹⁵⁰⁵¹  вариантов. Если предположить, что для одного перебора требуется один процессорный такт, то при скорости в 3 ГГц для перебора всех чисел будет нужно время, превышающее возраст нашей планеты. Существует, правда, хитроумный алгоритм, решающий ту же задачу за exp(n^1/3) шагов, но даже в этом случае с задачей разложения на простые множители числа, имеющего миллион знаков, не справится ни один современный суперкомпьютер.

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

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

 

1.2. Идея создания квантового компьютера

Автор идеи о создании квантового компьютера — американский физик Ричард Фейнман, известный в СССР по популярному курсу «Фейнмановские лекции по физике». В 1958 году, моделируя на компьютере квантовые процессы, он понял, что для решения многочастичных квантовых задач объем памяти классического компьютера совершенно недостаточен. Уже при решении задачи с 1000 электронными спинами в памяти должно быть достаточно ячеек, чтобы хранить 2 в степени 1000 переменных. А гигабайт — это всего лишь 2 в степени 30. Все квантовые задачи, которые сейчас рассчитываются на классических компьютерах, — очень грубые приближения. Тогда Фейнман высказал мысль о том, что квантовые задачи должен решать квантовый компьютер: природе задачи должен соответствовать способ ее решения. И предложил один из вариантов квантового компьютера. Но настоящий бум начался в 1995 году, когда американский математик Шор переложил для квантового компьютера алгоритм вычисления простых множителей больших чисел. Шор показал, что если классический компьютер для нахождения множителей числа из 1000 двоичных знаков должен сделать 2 в степени 1000 операций, то квантовому компьютеру для этого понадобится всего 1000 в степени 3 операций. Квантовый алгоритм факторизации Шора стал одним из основных факторов, приведших к интенсивному развитию квантовых методов вычислений и появлению алгоритмов, позволяющих решать некоторые NP-проблемы.( NP-полная задача — Nondeterministic polynomial-time complete такие задачи входят в класс невычисляемых в том смысле, что они не могут быть решены на классических компьютерах за время, полиномиально зависящее от числа битов n, представляющих задачу.)????

Естественно, возникает  вопрос: почему, собственно, предложенный Шором квантовый алгоритм факторизации привел к таким последствиям? Дело в том, что задача разложения числа на простые множители имеет прямое отношение к криптографии, в частности к популярным системам шифрования RSA. Благодаря возможности разложения числа на простые множители за полиномиальное время квантовый компьютер теоретически позволяет расшифровывать сообщения, закодированные при помощи многих популярных криптографических алгоритмов, таких как RSA. До сих пор этот алгоритм считался сравнительно надежным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Шор придумал квантовый алгоритм, позволяющий разложить на простые множители n-значное число за n3(log n)k шагов (k = const). Естественно, практическая реализация такого алгоритма могла иметь скорее негативные, чем позитивные последствия, поскольку позволяла подбирать ключи к шифрам, подделывать электронные подписи и т.п. Впрочем, до практической реализации настоящего квантового компьютера еще далеко, а потому в течение ближайших десяти лет можно не опасаться, что шифры могут быть взломаны с помощью квантовых компьютеров. 

2. Принцип работы квантового компьютера

2.1. Квантовые вычисления (математический аппарат квантового компьютера)

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

Прежде чем  рассматривать обобщенные квантовые  понятия вектора состояния и  принципа суперпозиции, разберем простой  пример поляризованного фотона. Поляризованный фотон — это пример двухуровневой квантовой системы. Состояние поляризации фотона можно задать вектором состояния, определяющим направление поляризации. Поляризация фотона может быть направлена вверх или вниз, поэтому говорят о двух основных, или базисных, состояниях, которые обозначают как |1 и |0 .

Данные обозначения (бра/кэт-обозначения) были введены  Дираком и имеют строго математическое определение (векторы базисных состояний), которое обусловливает правила работы с ними, однако, дабы не углубляться в математические дебри, мы не станем детально рассматривать эти тонкости.

Возвращаясь к  поляризованному фотону, отметим, что  в качестве базисных состояний можно было бы выбрать не только горизонтальное и вертикальное, но и любые взаимно ортогональные направления поляризации. Смысл базисных состояний заключается в том, что любая произвольная поляризация может быть выражена как линейная комбинация базисных состояний, то есть a|1 +b|0 . Поскольку нас интересует только направление поляризации (величина поляризации не важна), то вектор состояния можно считать единичным, то есть |a|²+|b|² = 1.