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

на классическом компьютере. Это наблюдение привело к более общему утверждению,

что для проведения вычислений квантовые процессы являются более эффективными, чем классические. Данное предположение было подтверждено Питером Шором, который разработал квантовый алгоритм разложения целых чисел на простые множители за полиномиальное время.
В 1960-е годы американский физик Р. Ландауэр, работавший в корпорации IBM, пытался обратить внимание научного мира на то, что вычисления - это всегда некоторый физический процесс, а значит, невозможно понять пределы наших вычислительных возможностей, не уточнив, какой физической реализации они соответствуют.
Русский математик Ю. И. Манин, указал в 1980 году на необходимость разработки теории квантовых вычислительных устройств. В 1980-е годы эту же проблему изучали американский физик П. Бенев, явно показавший, что квантовая система может производить вычисления, а также английский ученый Д. Дойч, теоретически разработавший универсальный квантовый компьютер, превосходящий классический аналог. Большое внимание к проблеме разработки квантовых компьютеров привлек лауреат Нобелевской премии по физике Р. Фейнман. Благодаря его авторитетному призыву число специалистов, обративших внимание на квантовые вычисления, увеличилось во много раз.
В 1994 году американский математик, сотрудник фирмы Lucent Technologies (США) Питер Шор ошеломил научный мир, предложив квантовый алгоритм, позволяющий проводить быструю факторизацию больших чисел.
В 1995 году П. Шор разработал схему кодирования квантовых состояний и коррекции в них ошибок.
В 1996 году коллега Шора по работе в Lucent Technologies Л. Гровер предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных.

механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на

основе классической механики. Квантовый компьютер использует для вычисления не обычные (классические) алгоритмы, а процессы квантовой природы, так называемые квантовые алгоритмы, использующие квантовомеханические эффекты, такие как квантовый параллелизм и квантовая запутанность.
Квантовый параллелизм — принцип, лежащий в основе работы квантовых компьютеров и позволяющий им потенциально превзойти в производительности классические компьютеры. В основе квантового параллелизма лежит использование при вычислениях суперпозиций базовых состояний, что позволяет одновременно производить большое количество вычислений с различными исходными данными.
Ква́нтовая сце́пленность (англ. entanglement «запу́танность, перепу́танность») — квантовомеханическое явление, при котором квантовое состояние двух или большего числа объектов должно описываться во взаимосвязи друг с другом, даже если отдельные объекты разнесены в пространстве.
Спин (от англ. spin — вертеть[-ся]) — собственный момент импульса элементарных частиц, имеющий квантовую природу и не связанный с перемещением частицы как целого. Спином называют также собственный момент импульса атомного ядра или атома; в этом случае спин определяется как векторная сумма (вычисленная по правилам сложения моментов в квантовой механике) спинов элементарных частиц, образующих систему, и орбитальных моментов этих частиц, обусловленных их движением внутри системы.

наименьший элемент для хранения информации в квантовом компьютере. Как и

бит, кубит допускает два собственных состояния, обозначаемых 0 и 1, но при этом может находиться и в их суперпозиции, то есть в состоянии , где A*|0 > и B*|1 > любые комплексные числа, удовлетворяющие условию | A | ^2 + | B |^ 2 = 1. Двум значениям кубита могут соответствовать, например, основное и возбужденное состояния атома, направления вверх и вниз спина атомного ядра, направление тока в сверхпроводящем кольце, два возможных положения электрона в полупроводнике и т.п. При любом измерении состояния кубита он случайно переходит в одно из своих собственных состояний. Вероятности перехода в эти состояния равны, соответственно | A |^2 и | B |^2, то есть косвенно, по наблюдениям за множеством кубитов, мы всё-таки можем судить об исходном состоянии. Кубиты могут быть «запутаны» друг с другом, то есть, на них может быть наложена ненаблюдаемая связь, выражающаяся в том, что при всяком измерении над одним из нескольких кубитов, остальные меняются согласованно с ним. То есть, совокупность запутанных между собой кубитов может интерпретироваться как заполненный квантовый регистр.
Квантовый регистр в квантовых компьютерах устроен почти так же, как и классический. Это цепочка квантовых битов, над которыми можно проводить одно- и двухбитовые логические операции (подобно применению операций НЕ, 2И-НЕ и т.п. в классическом регистре).

же как и в классическом, все возможные последовательности нулей и

единиц длиной L. Всего может быть 2L различных комбинаций. Их можно считать записью чисел в двоичной форме от 0 до 2L-1 и обозначать 0,1,2,3, ... 2L -1. Однако эти базовые состояния не исчерпывают всех возможных значений квантового регистра (в отличие от классического), поскольку существуют еще и состояния суперпозиции, задаваемые комплексными амплитудами, связанными условием нормировки. Классического аналога у большинства возможных значений квантового регистра (за исключением базовых) просто не существует.

нахождения решения уравнения f(x)=1, где f есть булева функция от

n переменных) позволяет найти решение уравнения f(x)=1, 0 < x < N за время O(√N). Классический алгоритм решения такой задачи (линейный поиск), O(N/L)требует обращений к f.
Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log(n) время.
Алгоритм Залки - Визнера позволяет моделировать унитарную эволюцию квантовой системы системы n частиц за почти линейное время с использованием O(n) кубит.
Алгоритм Дойча — Джоза позволяет «за одно вычисление» определить, является ли функция двоичной переменной f(n) постоянной (f1(n) = 0, f2(n) = 1 независимо от n) или «сбалансированной» (f3(0) = 0, f3(1) = 1; f4(0) = 1, f4(1) = 0).
Стоит, однако, отметить, что существует класс задач, для которых квантовые алгоритмы не дают значительного ускорения по сравнению с классическими. Одним из первых это показал российский математик Ю. Ожигов, построивший ряд примеров алгоритмов, принципиально не ускоряемых на квантовом компьютере ни на один такт.

ионных ловушек, ядерного магнитного резонанса (ЯМР), оптики и твёрдого тела.

Все текущие предложения сводятся к решению проблемы увеличения числа кубитов. Необходим качественно новый уровень вычислений, чтобы обрабатывать не десятки, а сотни кубитов информации. На сегодняшний день технологии с использованием ЯМР и ионных ловушек являются наиболее разрабатываемыми, однако использование оптики и твёрдого тела также подаёт надежды. В квантовых компьютерах с ионной ловушкой [Ширак и Золлер 1995; Стин 1996] линейная последовательность ионов, представляющих кубиты, ограничена электрическим полем. Для того, чтобы произвести однокубитовые квантовые операции, лазеры направляются на отдельные ионы. Двухкубитовые операции осуществляются при использовании лазера, направленного на отдельный кубит для создания колебания, которое распространяется по цепи ионов до второго кубита, где другой лазер останавливает движение и завершает двухкубитовую операцию. При данном методе требуется, чтобы ионы находились в предельно чистом вакууме при максимально низких температурах. Преимущество метода использования ЯМР заключается в том, что его можно применять при комнатной температуре. Тем более, что технология ЯМР в целом уже добилась некоторого успеха. Суть метода в том, чтобы использовать макроскопическое количество материи и закодировать квантовый бит в среднем состоянии спина большего количества ядер. Состояниями спина можно управлять посредством магнитных полей, а среднее состояние спина можно измерить при помощи техники ЯМР. Основная проблема при использовании этого метода заключается в трудностях при увеличении квантового регистра. Мощность измеряемого сигнала падает как 1/2n, где n - число кубитов.

журнале Nature, IBM продемонстрировала использование созданного в лабораториях компании семикубитового

квантового компьютера для факторизации чисел по так называемому алгоритму Шора. Хотя решённая им задача вряд ли способна поразить воображение (компьютер верно определил, что делителями числа 15 являются числа 5 и 3), это самое сложное вычисление за всю историю квантовых компьютеров.
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит (устройство получило название Orion[13]). Информация об этом устройстве не отвечала требованиям достоверного научного сообщения, поэтому новость не получила научного признания. Более того, дальнейшие планы компании — создать уже в ближайшем будущем 1024-кубитный компьютер — вызвали скепсис у членов экспертного сообщества.

4 апреля 2011 Создано запутанное состояние 14 кубитов. Рекордно большой квантовый регистр был получен физиками из Австрии и Канады в эксперименте с ионами кальция, помещёнными в ловушку Пауля.