Выполнил студент группы 09-ОЗИ1
Постникова А.Н.

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

Введение

«Начало прошлого века совпало с рождением квантовой теории излучения, что привело вскоре и к появлению ряда новых, основанных на квантовых представлениях, областей физики, таких как атомная и ядерная физика, квантовая физика твердого тела и физика полупроводников, квантовая физика электронного и ядерного магнетизма и ряда других. Уже в середине века физика полупроводников стала научной базой быстроразвивающейся микро- и наноэлектроники, которая обеспечила бурный рост информационных технологий. Однако развитие электронной вычислительной техники, несмотря на то, что в качестве элементной базы использовались полупроводниковые приборы с определенными квантовыми свойствами, шло в основном по пути организации вычислительных операций на основе классической булевой логики.
Идея квантовых вычислений, по-видимому, впервые высказанная Ю.И.Маниным в 1980 году, активно стала обсуждаться в мире с 1982 года, после опубликования статьи американского физика-теоретика, нобелевского лауреата Р.Фейнмана. Эти авторы обратили внимание на то, что каждое состояние квантовой системы из L двухуровневых квантовых элементов (позднее они получили наименование квантовых битов – кубитов (qubits)), в отличие от классической системы с тем же числом классических битов, может представлять собой произвольную когерентную суперпозицию из 2L базисных состояний. Иначе говоря, состояние квантовой системы характеризуется вектором состояния в 2L-мерном гильбертовом пространстве. Для описания такой квантовой суперпозиции в классическом вычислительном устройстве потребовалось бы задать 2L комплексных чисел. Уже для L = 100 их число исключительно велико — порядка 1030! Отсюда следовал и обратный вывод о том, что эффективное моделирование квантовых систем, содержащих до сотни двухуровневых квантовых элементов, практически не доступно классическим компьютерам. Но оно может эффективно осуществляться на основе использования квантовых операций, действующих в 2L–мерном гильбертовом пространстве состояний. Элементарной унитарной квантовой операцией является поворот вектора состояния всей L–кубитовой системы в гильбертовом пространстве. Для выполнения этой операции на классическом компьютере потребовалось бы выполнить 2L элементарных шагов по вычислению всех коэффициентов суперпозиции. При любой мыслимой скорости элементарных операций это потребует нереально большого времени классических вычислений.
Существенное значение в процессе выполнения квантовых вычислительных операций, кроме того, имеют состояния, представляющие собой когерентную интерференцию между множеством суперпозиций. Эта особенность квантовых вычислений называется квантовым параллелизмом. Этим они принципиально отличаются от операций над классическими булевыми состояниями. Квантовый параллелизм — главное преимущество квантовых вычислений по сравнению с цифровыми классическими вычислениями.
Квантовый компьютер является открытой физической системой. Благодаря взаимодействию квантовой системы с окружением, а также в случае случайно неоднородной структуры ансамбля кубитов, имеет место процесс разрушения или декогерентизации (decoherence) когерентных квантовых состояний, приводящий к нарушению унитарности квантовых процессов, механизма квантовой интерференции, искажению обрабатываемой квантовой информации и уменьшению «объема» квантовых состояний в результате их перехода в классические состояния. Подавление декогерентизации до необходимого уровня является одной из основных проблем, стоящих на пути реализации квантовых компьютеров.
Перспективы квантовых вычислений обычно связывают с ожидаемым экспоненциальным ускорением решения так называемой NP-полной (Nondeterministic polynomial-time complete) проблемы, связанной с решением таких задач, для которых это решение очень трудно найти, но очень просто его проверить. Такие задачи относят к классу невычисляемых задач в том смысле, что они не могут быть решены на классических компьютерах за время, полиномиально зависящее от числа битов L, представляющих задачу.
Среди важных задач, решения которых можно было бы ожидать от квантового компьютера, отметим задачу моделирования многочастичных квантовых систем, к которым можно отнести как сложные молекулы, биологические объекты, так и элементы современной наноэлектроники. Это могут быть и сами многокубитовые квантовые системы, где существенную роль играют такие квантовые эффекты, как суперпозиция, запутанность состояний, особенности квантовой динамики.
Следовательно, уже сейчас потребность в квантовых компьютерах существует и с появлением новых задач она, несомненно, будет возрастать. Ограничением, однако, здесь может стать экономическая сторона вопроса.
Кроме того, развитие квантовых вычислений и квантовой информатики в целом имеет неоценимое общенаучное значение. Оно способствуют более глубокому познанию фундаментальных законов, как физики, так и других естественных наук. А это рано или поздно неизбежно приводит к новым самым неожиданным открытиям и практическим приложениям.
В настоящее время полномасштабные многокубитовые квантовые компьютеры, превосходящие по своим возможностям любой работающий на булевой логике классический компьютер, являются пока умозрительной конструкцией. Они должны иметь квантовые регистры, включающие не менее 1000 кубитов, а также удовлетворять ряду других требований, в частности, вытекающих из условия помехозащищенности квантовых вычислений. Такого большого числа кубитов в квантовом регистре можно достигнуть, вероятнее всего, лишь при твердотельном исполнении квантовых компьютеров, работающих в условиях низких температур. Это могут быть, в частности, твердотельные ядерные магнито-резонансные (ЯМР) квантовые компьютеры, использующие в качестве кубитов ядерные спины со спиновым квантовым числом I = 1/2.

Однако пока созданы лишь простейшие прототипы жидкостных ЯМР квантовых компьютеров на органических молекулах с числом ядерных спинов-кубитов L ~ 7, молекулы в которых представляют собой большой ансамбль независимо работающих компьютеров. На них были экспериментально продемонстрированы некоторые квантовые алгоритмы решения трудно разрешимых на классических компьютерах задач (алгоритмы Гровера, Дойча-Джозса, Шора) и уникальные свойства квантовых систем связи, таких как телепортация, новые возможности в криптографии, опробованы эффективные методы коррекции квантовых ошибок. Однако создание на этом пути полномасштабного ЯМР квантового компьютера оказывается невозможным из-за быстро уменьшающегося с числом кубитов выходного сигнала ЯМР.
Разработка квантовых кодов коррекции ошибки для многокубитовых систем предоставила возможность выполнять коррекцию ошибок в процессе квантовых операций с произвольной точностью, что может позволить реализовать надежную работу полномасштабных многокубитовых квантовых компьютеров и такие действия, которые до сих пор считались вообще неосуществимыми.
Количество публикаций по квантовым вычислениям и квантовой теории передачи информации в настоящее время приобрело лавинообразный характер. Это в свою очередь способствовало, с одной стороны, более глубокому осмысливанию физических основ самой квантовой теории, ее связи с квантовой теорией информации, а с другой стороны, стимулировало усилия по реализации квантовых компьютеров — этого нового направления в вычислительной технике, а также других совершенно новых квантовых технологий. Детальный анализ состояния исследований в области квантовых компьютеров и квантовых вычислений на начало 2001 года был дан в монографиях.
Постоянно растущее число предложенных вариантов многокубитовых квантовых компьютеров и предпринимаемые уже в этом направлении первые успешные экспериментальные шаги, использующие достижения современной нанотехнологии, внушают определенный оптимизм относительно возможности осуществления полномасштабного квантового компьютера. К этим шагам, следует отнести работы по созданию кремниевого многокубитового ЯМР квантового компьютера, основанные как на схеме Б.Кейна, так и с использованием других твердотельных вариантов, в Австралийском Центре технологии квантовых компьютеров.
Однако на пути к реализации полномасштабных квантовых компьютеров необходимо решить целый ряд проблем как общефизического, так технического и технологического характера, благодаря чему ни один из предложенных вариантов многокубитовых квантовых компьютеров пока не удалось осуществить.
Рассмотрение путей решения основных проблем полномасштабного ЯМР квантового компьютера составляет основное содержание предлагаемой книги. Она состоит из двух частей. В первой части излагаются физические основы ЯМР квантовых компьютеров, общие принципы построения квантовых компьютеров и организации квантовых вычислительных операций. Во второй части рассмотрены варианты твердотельных ЯМР квантовых компьютеров различной архитектуры, проанализированы преимущества и недостатки отдельных вариантов и дана оценка их перспективности.» /2/

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

«Квантовый компьютер — вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе классической механики. Полномасштабный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьезным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики. Ограниченные (до 10 кубитов) квантовые компьютеры уже построены; элементы квантовых компьютеров могут применяться для повышения эффективности вычислений уже на существующей приборной базе.
Идея построения квантового компьютера была предложена в 1980 году советским математиком Ю. Маниным (эту идею поддержали физики, в частности, П. Бениоф и Нобелевский лауреат Р. Фейнман). Необходимость в квантовом компьютере возникает тогда, когда мы пытаемся исследовать методами физики сложные многочастичные системы, подобные биологическим. Пространство квантовых состояний таких систем растет как экспонента от числа n составляющих их реальных частиц, что делает невозможным моделирование их поведения на классических компьютерах уже для n = 10. Поэтому Фейнман и предложил построение квантового компьютера.
Квантовый компьютер использует для вычисления не обычные (классические) алгоритмы, а процессы квантовой природы, так называемые квантовые алгоритмы, использующие квантовомеханические эффекты, такие как квантовый параллелизм и квантовая запутанность.
Если классический процессор в каждый момент может находиться ровно в одном из состояний 0, 1, …, (N-1), (обозначения Дирака) то квантовый процессор в каждый момент находится одновременно во всех этих базисных состояниях, при этом в каждом состоянии j — со своей комплексной амплитудой λj. Это квантовое состояние называется «квантовой суперпозицией» данных классических состояний и обозначается как

Базисные состояния могут иметь и более сложный вид. Тогда квантовую суперпозицию можно проиллюстрировать, например, так: "Вообразите атом, который мог бы подвергнуться радиоактивному распаду в определённый промежуток времени. Или не мог бы. Мы можем ожидать, что у этого атома есть только два возможных состояния: «распад» и «не распад», /…/ но в квантовой механике у атома может быть некое объединённое состояние — «распада — не распада», то есть ни то, ни другое, а как бы между. Вот это состояние и называется «суперпозицией».
Квантовое состояние ψ может изменяться во времени двумя принципиально различными путями:

1. Унитарная квантовая операция (квантовый вентиль (англ. quantum gate), в дальнейшем просто операция).
2. Измерение (наблюдение).

Если классические состояния j есть пространственные положения группы электронов в квантовых точках, управляемых внешним полем V то унитарная операция есть решение уравнения Шредингера для этого потенциала.
Измерение есть случайная величина, принимающая значения j, j = 0,1, …, N-1, с вероятностями | λj | 2 соответственно. В этом состоит квантово-механическое правило Борна (англ.). Измерение есть единственная возможность получения информации о квантовом состоянии, так как значения λj нам непосредственно не доступны. Измерение квантового состояния не может быть сведено к унитарной шредингеровской эволюции, так как, в отличие от последней, оно необратимо. При измерении происходит так называемый коллапс волновой функции ψ , физическая природа которого до конца не ясна. Спонтанные вредоносные измерения состояния в ходе вычисления ведут к декогерентности, то есть отклонению от унитарной эволюции, что является главным препятствием при построении квантового компьютера.
Квантовое вычисление есть контролируемая классическим управляющим компьютером последовательность унитарных операций простого вида (над одним, двумя или тремя кубитами). В конце вычисления состояние квантового процессора измеряется, что и дает искомый результат вычисления.» /4/

Квантовая теория твердого тела - научная база микроэлектроники и наноэлектроники

«Прикладное значение p-n-переходов не сразу было должным образом оценено. Электроника того времени развивалась исключительно на основе вакуумных электронных ламп и специалисты-электронщики мало интересовались полупроводниками. Только после изобретения в 1948 году сотрудниками Bell Laboratories Дж.Бардиным и В.Брэттеном точечно-контактного кристаллического триода на основе германия n-типа, названного ими транзистором, и появления работы В.Шокли в 1949 году по квантовой теории плоскостных диодов и транзисторов начался беспрецедентный качественный прорыв в полупроводниковой электронике. Авторы этих работ были отмечены Нобелевской премией. Позднее Дж. Бардин получил вторую Нобелевскую премию за создание вместе с Л.Купером и Дж.Шриффером квантовой теории сверхпроводимости.
Заметим, что этот прорыв не мог быть достигнут на пути дальнейшего развития только вакуумной электроники, для этого потребовались совершенно новые идеи, которые и появились в результате исследований в совершенно другой области физики - в квантовой теории полупроводников. Новой технической области потребовались специалисты с глубоким знанием физики полупроводников и ее квантовых основ.
Важную роль в дальнейшем развитии полупроводниковой электроники сыграло позднее изобретение кремниевой планарной технологии, основанной на контролируемой диффузии примесей в локальных областях в приповерхностном слое кремниевой пластины, и создание в 1959 году на фирме Fairchild Semiconductor первого планарного биполярного транзистора на кремнии. Рождение микроэлектроники принято относить именно к этой дате. Несколько позже был создан первый полевой транзистор со структурой металл-окисел-полупроводник (МОП-транзистор) на кремнии, выполненный также по планарной технологии. Он стал в дальнейшем одним из основных элементов больших интегральных схем - элементной базы современных цифровых электронных компьютеров. Первые советские планарные биполярные транзисторы были изготовлены в НИИ "Пульсар" в Москве и в НИИ Молекулярной Электроники (тогда п/я 2021) в Зеленограде в 1965 году. В том же году начал готовить специалистов в области микроэлектроники новый ВУЗ - Московский Институт Электронной Техники в Зеленограде.
Успехи в развитии кремниевой микроэлектроники наглядно выражаются так называемым законом Г.Мура, согласно которому число транзисторов в кристалле одной интегральной схемы (ИС), начиная с 1959 года, в течение первых 15 лет удваивалось каждый год, а затем и до сих пор такое удвоение происходит приблизительно за 1,5 года. По экспоненциальному закону уменьшаются со временем и характерные размеры элементов ИС. В декабре 1999 года появилось сообщение о разработке в Калифорнийском университете в Беркли технологии изготовления МОП-транзистора на островке кремния в форме плавника с рекордной эффективной длиной канала 18 нм и хорошими характеристиками, а также матрицы соответствующих тестовых структур. Экстраполяция тенденции уменьшения размеров приборов показывает, что атомные размеры в твердотельной технологии могут быть достигнуты уже через 20 лет.
Основой современного цифрового компьютера является совокупность макроскопических полупроводниковых базисных элементов - классических битов с двумя возможными логическими булевыми состояниями "0" и "1" и логических элементов-вентилей, которые производят локальные логические операции над состояниями этих элементов для того, чтобы получить в результате определенное конечное состояние на выходе.
Логические состояния в каждом бите - это, например, два значения тока в определенном проводнике или потенциала на нем, рассматриваемые как макроскопические некогерентные классические величины. В этом смысле современные цифровые компьютеры, несмотря на исходную квантовую природу физических процессов, происходящих в полупроводниковых элементах, рассматриваются как классические. Вычисление в любом компьютере представляет собой процесс, в ходе которого происходит определенные для каждой логической операции нелинейные взаимодействия потоков информации друг с другом и их преобразование. Соответствующие процессы происходят на физическом уровне и с носителями информации - некогерентными сигналами, то есть с токами и напряжениями.
Последние два десятилетия характеризовалось также освоением новых не кремниевых материалов и интенсивными поисками новых физических принципов для приборов с характерными размерами, сравнимыми с длиной волны Де-Бройля, имеющей величину порядка 20 нм, для которых существенны более тонкие по сравнению с массивными полупроводниками квантовые свойства. Это квантовые ямы, нити и точки. Такие структуры потребовали новой технологии, которая получила название нанотехнологии.
Примером наноэлектронных полупроводниковых приборов могут служить, в частности, транзисторы с резонансным туннелированием и транзисторы на горячих электронах с резонансным туннелированием, характеристики которых существенным образом определяются свойствами электронных квантовых состояний и квантовым характером эволюции этих состояния в полупроводниковых структурах. Существует и много других типов наноэлектронных приборов, физические процессы внутри которых имеют квантовый характер и требуют для своего описания применения квантовых методов. Однако по-прежнему в наноэлектронных приборах, как и в традиционных микроэлектронных приборах, обрабатывается информация, передаваемая некогерентными классическими сигналами, носителями которых являются электрические токи и напряжения.
Важной проблемой, с которой пришлось столкнуться особенно при переходе в область наноэлектронных устройств, является проблема уменьшения рассеиваемой энергии в процессе вычислительных операций. Мысль о возможности "логически обратимых" операций, не сопровождающихся рассеянием энергии, впервые высказал Р.Ландауер еще в 1961 году. Существенный шаг в ее решении был сделан в 1982 году Ч.Беннеттом, который показал, что универсальный цифровой компьютер типа вычислительной машины Тьюринга может быть построен на логически и термодинамически обратимых вентилях таким образом, что энергия будет рассеиваться только за счет необратимых периферийных процессов ввода информации в машину (приготовление исходного состояния) и, соответственно, вывода из нее (считывание результата). К типичным обратимым универсальным вентилям относятся вентили Фредкина и Тоффоли.» /3/

Возникновение идеи о квантовых вычислениях

«Дальнейший прогресс микроэлектроники и вычислительной техники до недавнего времени виделся на пути дальнейшего увеличения степени интеграции, быстродействия интегральных схем и использования логически обратимых вентилей. Кардинально новые идеи и принципы построения вычислительных устройств должны были прийти из других областей физики, подобно тому как в электронику из физики полупроводников пришел принцип действия полупроводникового транзистора, на основе которого были построены различные логические элементы и элементы памяти.
Любая классическая двухуровневая система, как и квантовая, имеет основное |0с и не основное |1с базисные состояния. Примером классической двухуровневой системы является известный в микроэлектронике инвертор, осуществляющий операцию НЕ. В зависимости от того заняты ли эти состояния с вероятностями P(0) = 1, P(1) = 0 или P(0) = 0, P(1) = 1, мы имеем булевые логические состояния "0" или "1".
В квантовом случае возникает намного более богатая ситуация. Волновая функция квантовых состояний двухуровневой системы - квантового бита, получившего в дальнейшем название кубита (quantum bit или qubit), может представлять собой суперпозицию базисных состояний (вектор состояния) следующего вида |yc = a|0c + b|1c, где a,b - комплексные амплитуды состояний, при этом |a|2 + |b|2 = 1. Помимо вероятностей P(0) = |a|2 и P(1) = |b|2, заполнения базисных состояний |0c и |1c, состояние кубита характеризуется когерентными или интерференционными слагаемыми в вероятности состояния |yc, определяемых произведениями комплексных амплитуд ab* и a*b. Состояние квантового бита в отличие от классического может изменяться не только путем изменения вероятностей P(0) и P(1), но и более тонко путем изменения амплитуд состояний a и b, что соответствует поворотам вектора состояния |yc в так называемом гильбертовом двухмерном пространстве состояний. В этом и состоит принципиальное различие классического и квантового бита.
Кардинально новой оказалась идея о квантовых вычислениях, впервые высказанная советским математиком Ю.И.Маниным в 1980 году, и которая стала активно обсуждаться лишь после опубликования в 1982 году статьи американского физика-теоретика нобелевского лауреата Р.Фейнмана. Он обратил внимание на способность изолированной квантовой системы из L двухуровневых квантовых элементов находиться в когерентной суперпозиции из 2L булевых состояний, характеризующейся 2L комплексными числами и увеличенной до 2L размерностью соответствующего гильбертова пространства. Ясно, что для описания такого квантового состояния в классическом вычислительном устройстве потребовалось бы задать 2L комплексных чисел, то есть понадобились бы экспоненциально большие вычислительные ресурсы. Отсюда был сделан обратный вывод о том, что эффективное численное моделирование квантовых систем, содержащих до сотни двухуровневых элементов, практически недоступно классическим компьютерам, но может эффективно осуществляться путем выполнения логических операций на квантовых системах, которые действуют на суперпозиции многих квантовых состояний.
Поскольку законы квантовой физики на микроскопическом уровне являются линейными и обратимыми, то и соответствующие квантовые логические устройства, производящие операции с когерентными (чистыми) квантовыми состояниями отдельных кубитов, оказываются также логически и термодинамически обратимыми, а квантовые вычислительные операции представляются унитарными операторами в 2L-мерном гильбертовом пространстве. Квантовые вентили аналогичны соответствующим обратимым классическим вентилям, но в отличие от классических они способны совершать унитарные операции над суперпозициями состояний. Выполнение унитарных логических операций над кубитами предполагается осуществлять с помощью соответствующих внешних воздействий, которыми управляют классические компьютеры. Р.Фейнман предложил и первую схему квантового обратимого компьютера.» /3/

Структура квантового компьютера

«Квантовые методы выполнения вычислительных операций, а также передачи и обработки информации, уже начинают воплощаться в реально функционирующих экспериментальных устройствах, что стимулирует усилия по реализации квантовых компьютеров - этого нового направления в вычислительной технике.
Количество публикаций по квантовой теории информации и квантовым вычислениям приобрело в последнее время лавинообразный характер, появились и экспериментальные работы.
Принципиальная схема работы любого квантового компьютера может быть представлена следующим образом (см. рис.1). Основной его частью является квантовый регистр - совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты регистра должны быть приведены в основные базисные (булевые) состояния, то есть в состояние |01с,|02с,|03с,...|0Lс є |01,02,03,...0Lс. Эта операция называется подготовкой начального состояния или инициализацией (initializing). Далее каждый кубит подвергается селективному воздействию, например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером, которое переведет основные базисные состояния определенных кубитов в не основное состояния |0с Ю |1с. При этом состояние всего регистра перейдет в суперпозицию базисных состояний вида |nс = |n1,n2,n3,...nLс, где ni = 0,1, задающую бинарное представление числа n = .

При вводе информации в квантовый компьютер состояние входного регистра, с помощью соответствующих импульсных воздействий преобразуется в соответствующую когерентную суперпозицию базисных ортогональных состояний. В таком виде информация далее подвергается воздействию квантового процессора, выполняющего последовательность квантовых логических операций, определяемую унитарным преобразованием действующим на состояние всего регистра.
Совокупность всех возможных операций на входе данного компьютера, формирующих исходные состояния, а также осуществляющих унитарные локальные преобразования, соответствующие алгоритму вычисления, способы подавления потери когерентности - так называемой декогерентизации (decoherence) квантовых состояний и исправления случайных ошибок, играют здесь ту же роль, что и "программное обеспечение" (software) в классическом компьютере.» /3/

Квантовые вычисления

Основные квантовые логические операции

«В квантовом компьютере логические операции производятся в системе кубитов. Они разбиваются на дискретную совокупность последовательных во времени базисных квантовых логических операций – квантовых вентилей ( guantum gates ). Каждый квантовый вентиль за фиксированный промежуток времени выполняет унитарное преобразование с выделенными кубитами. Квантовый вентиль осуществляет обратимые операции и с этой точки зрения классический обратимый компьютер является аналогом квантового компьютера. Одним из основных условий для построения квантового компьютера является наличие универсального набора квантовых вентилей, с помощью которого может быть выполнено любое унитарное преобразование в 2L-мерном гильбертовом пространстве.
К однокубитовым квантовым операторам, действующим только на один кубит, относятся различные операторы поворота вектора состояния кубита в двухмерном гильбертовом пространстве. Это, в частности, такие вентили, как NOT, описываемый матрицей 2х2 или оператором Паули:

,

оператор Адамара (H. Hadamard), осуществляющий самообратимую операцию формирования суперпозиции состояний

, ,

которую можно записать также в виде

.

Оператор Адамара Ĥ описывается матрицей

.

Аналогичное преобразование в системе L кубитов осуществляется с помощью N=2L-мерного оператора Уолша-Адамара (Walsh-Hadamard), представляющего собой прямое произведение однокубитовых операторов Адамара:

,

Используя выражение , для него получим
:::
Двухкубитовые вентили соответствуют операциям поворота в гильбертовом пространстве двух взаимодействующих кубитов, которые не могут быть представлены в виде прямого произведения независимых однокубитовых операций. Основным двухкубитовым вентилем является обратимый контролируемый инвертор или оператор контролируемое НЕ (CNOT), который в совокупности с относительно простыми однокубитовыми операциями может быть базовым для формирования любой унитарной операции в системе из более двух кубитов.
Этот вентиль описывается матрицей 4х4 следующего вида:
:::.
С помощью CNOT можно осуществлять операцию копирования или неразрушающее измерение состояния контролирующего кубита.» /1, c. 66-69/

Основные квантовые алгоритмы

Алгоритм Шора

«Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время, O(log2Nlog3(logN)) используя O(log N) логических кубитов.
Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Наилучший из известных классических алгоритмов факторизации требует времени порядка N1 / 3. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера в случае ее успеха поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).
Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (умножением) в квадратичное время, алгоритм может быть модифицирован так, что ответ будет верным с единичной вероятностью.
Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.
Основным достижением П. Шора является реализация им дискретной версии преобразования Фурье на квантовом компьютере - так называемое квантовое преобразование Фурье (QFT - Quantum Fourier Transform). Ключевая роль преобразования Фурье для проблемы факторизации была известна до Шора. С другой стороны, реализованное Шором QFT имеет многочисленные применения и помимо факторизации.
Квантовое преобразование Фурье действует на базисных векторах a, a = 0, 1, …, N-1 согласно формуле
:::
QFT продолжается по линейности на все гильбертово пространство состояний H. QFT является унитарным оператором в H, обратное к нему задается аналогичной формулой, только без знака "-" в экспоненте.
Алгоритм Шора основан на возможности быстро вычислить собственные значения унитарного оператора с высокой точностью, если можно эффективно вычислять любые его степени. Взяв в качестве такого оператора умножение на x по модулю N (этот оператор действует в 2n мерном пространстве, где 2n-1˂N≤2n преобразуя базисный вектор, соответствующий числу a, в базисный вектор, соответствующий числу xa(modN)), мы сможем вычислить такое n, что xn = 1(modN), что позволяет (с высокой вероятностью) разложить N на множители на обычном компьютере.» /4/

Алгоритм Дойча-Джоза

«Алгоритм Дойча — Джоза — это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой запутанности и принципа суперпозиции обладают значительным приростом скорости выполнения по сравнению с соответствующими классическими алгоритмами.
Задача Дойча — Джоза заключается в определении, является ли функция двоичной переменной f(n) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1).
Для решения этой задачи классическому детерминированному алгоритму необходимо произвести 2n − 1 + 1 вычислений функции f в худшем случае. Классическому вероятностному алгоритму потребуется меньше времени, чтобы дать верный ответ с высокой вероятностью. Но в любом случае для получения верного ответа с единичной вероятностью потребуется 2n − 1 + 1 вычислений. Алгоритм Дойча — Джоза всегда дает верный ответ, совершив лишь одно вычисление значения функции f.
Алгоритм Дойча — Джоза основан на разработанном Давидом Дойчем в 1985 году схожем алгоритме, являющемся частным случаем первого. В этом алгоритме функция f(x1) являлась функцией одной переменной, в отличие от функции многих переменных f(x1, x2, …, xn), используемой в более позднем алгоритме.» /4/

Квантовая телепортация

«Квантовая телепортация — передача квантового состояния на расстояние при помощи разъединённой в пространстве сцепленной пары и классического канала связи, при которой состояние разрушается в точке отправления при проведении измерения, после чего воссоздаётся в точке приёма. Термин установился благодаря статье в 1993 году Phys.Rev.Lett. 70, 1895—1899 (1993), где описано, какое именно явление предлагается так называть и чем оно отличается от популярного в научной фантастике слова «телепортация». Квантовая телепортация не передаёт энергию или вещество на расстояние. Обязательным этапом при квантовой телепортации является передача информации между точками отправления и приёма по классическому, неквантовому каналу, которая может осуществляться не быстрее, чем со скоростью света, тем самым не нарушая принципов современной физики.
Квантовая телепортация осуществляется за счёт разделения информации на «квантовую часть» и «классическую часть» и независимой передаче этих двух компонентов. Для передачи «квантовой части» используются характерные для квантово-запутанных частиц корреляции Эйнштейна — Подольского — Розена, а для передачи классической информации годится любой обычный канал связи.
Для простоты будем иметь в виду квантовую систему с двумя возможными состояниями ψ1 и ψ2 (например, проекцию спина электрона или фотона на заданную ось). Такие системы часто называют кубитами. Однако, описанный способ пригоден для передачи состояния любой системы, имеющей конечное число состояний.
Пусть у отправителя есть частица А, находящаяся в произвольном квантовом состоянии ψA = αψ1 + βψ2, и он хочет передать это квантовое состояние получателю, то есть сделать так, чтобы у получателя оказалась в распоряжении частица B в том же самом состоянии. Иными словами, необходимо передать отношение двух комплексных чисел α и β (с бесконечной точностью). Заметим, что главная цель здесь — это передать информацию не как можно быстрее, а как можно аккуратнее. Для достижения этой цели выполняются следующие шаги.

1. Отправитель и получатель договариваются заранее о создании пары квантово-запутанных частиц C и B, причём C попадёт отправителю, а B — получателю. Поскольку эти частицы запутаны, то каждая из них не обладает своей волновой функцией (вектором состояния), но вся пара целиком (а точнее, интересующие нас степени свободы) описываются единым четырёхмерным вектором состояния ψBC.
2. Квантовая система частиц A и C имеет четыре состояния, однако мы не можем описать её состояние вектором — чистым (полностью определённым) состоянием обладает лишь система из трёх частиц A, B, C. Когда отправитель совершает измерение, имеющее четыре возможных исхода, над системой из двух частиц A и C, он получает одно из 4 собственных значений измеряемой величины. Поскольку при этом измерении система из трёх частиц A, B, C коллапсирует в некое новое состояние, причём состояния частиц A и C становятся известны полностью, то сцепленность разрушается и частица B оказывается в некотором определённом квантовом состоянии.
3. Именно в этот момент происходит как бы "передача" «квантовой части» информации. Однако восстановить передаваемую информацию пока невозможно: получатель знает, что состояние частицы B как-то связано с состоянием частицы A, но не знает как именно.
4. Для выяснения этого необходимо, чтобы отправитель сообщил получателю по обычному классическому каналу результат своего измерения (затратив при этом два бита, соответствующие зацепленному состоянию AC, измеренному отправителем). По законам квантовой механики получается, что имея результат измерения, проведённого над парой частиц A и C и плюс к тому запутанную с C частицу B, получатель сможет совершить необходимое преобразование над состоянием частицы B и восстановить исходное состояние частицы A.

Полная передача информации осуществится только после того, как получатель будет обладать данными, полученными по обоим каналам. До того, как получен результат по классическому каналу, получатель ничего не может сказать о переданном состоянии.
Фантастическое понятие телепортации происходит из специфичной интерпретации эксперимента: «исходное состояние частицы A после всего произошедшего разрушается. То есть, состояние было не скопировано, а перенесено из одного места в другое».» /4/

Список литературы

1. Валиев К.А., Кокин А.А. Квантовые компьютеры: надежды и реальность. M.: Ижевск: РХД, 2001. – 352с
2. Твердотельные квантовые компьютеры на ядерных спинах. URL: http://aakokin.chat.ru/qc_book2.htm (дата обращения: 05.06.2011)
3. Из итогов XX века: От кванта к квантовым компьютерам. URL: http://aakokin.chat.ru/xx.htm (дата обращения: 05.06.2011)
4. Википедия: свободная энциклопедия. URL: http://ru.wikipedia.org/wiki/ (дата обращения: 05.06.2011)