Принципы квантовых вычислений. Квантовые компьютеры
Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 0 или 1 в вашем цифровом компьютере. Каждый классический бит физически реализуется макроскопической физической системой, такой как намагниченность на жестком диске или заряд конденсатора. Например, текст, составленный из n символов, и сохраненный на жестком диске типичного компьютера, описывается строкой из 8n нулей и единиц. Здесь и лежит фундаментальное отличие между вашим классическим компьютером и квантовым компьютером. В то время как классический компьютер подчиняется хорошо понятным законам классической физики, квантовый компьютер это устройство, которое использует квантово-механические явления (в особенности квантовую интерференцию ), чтобы осуществлять совершенно новый способ обработки информации. Квантовые вычисления: за и против. Под ред. В.А. Садовничего. - Ижевск: Издательский дом «Удмуртский университет», 1999. - 212 с.
В квантовом компьютере фундаментальная единица информации (называемая квантовый бит или кубит ), не двоична, а скорее четверична по своей природе. Это свойство кубита проистекает как прямое следствие его подчиненности законам квантовой механики, которые радикально отличаются от законов классической физики. Кубит может существовать не только в состоянии, соответствующем логическим 0 или 1, как классический бит, но также в состояниях, соответствующих смесли или суперпозиции этих классических состояний. Другими словами, кубит может существовать как ноль, как единица, и как одновременно 0 и 1. При этом можно указать некоторый численный коэффициент, представляющий вероятность оказаться в каждом состоянии. . Белонучкин В.E., Заикин Д.А., Ципенюк Ю.М., Основы физики.
Идеи о возможности построения квантового компьютера восходят к работам Р. Фейнмана 1982- 1986 гг. Рассматривая вопрос о вычислении эволюции квантовых систем на цифровом компьютере, Фейнман обнаружил "нерешаемость" этой задачи: оказывается, что ресурсы памяти и быстродействия классических машин недостаточны для решения квантовых задач. Например, система из n квантовых частиц с двумя состояниями (спины 1/2 ) имеет 2 n базисных состояний; для ее описания необходимо задать (и записать в память ЭВМ) 2 n амплитуд этих состояний. Отталкиваясь от этого негативного результата, Фейнман высказал предположение, что, вероятно, "квантовый компьютер" будет обладать свойствами, которые позволят решать на нем квантовые задачи. Валиев К.А. «Квантовые компьютеры: можно ли их сделать «большими»?», Успехи физических наук, т. 169, № 6, 1999г.
"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического, состоянию, - значение логической. Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии, где -- комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии. В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".
Доказано, что квантовая ЭВМ может быть построена всего из двух элементов (вентилей): однокубитового элемента и двухкубитового элемента контролируемое НЕ (CNOT). Матрица 2x2 элемента имеет вид:
Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если -- иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс. Если (контролирующий кубит в состоянии), то при указанных воздействиях контролируемый кубит совершает переходы (или). Если же (контролирующий кубит в состоянии), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин, эволюционирует по-разному при: здесь в - состояние контролирующего кубита. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.
При рассмотрении вопроса о реализации квантового компьютера на тех или иных квантовых системах в первую очередь исследуют реализуемость и свойства элементарных вентилей НЕ и контролируемое НЕ.
Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:
В технике магнитного резонанса эти вентили осуществляются импульсами:
Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние, т.е. в основное состояние. Это условие само по себе не тривиально.
Оно требует или глубокого охлаждения (до температур порядка милликельвина), или применения методов поляризации. Систему п кубитов в состоянии можно считать регистром памяти, приготовленным для записи входных данных и проведения вычислений. Кроме этого регистра обычно предполагают существование дополнительных (вспомогательных) регистров, необходимых для записи промежуточных результатов вычислений. Запись данных осуществляется путем того или иного воздействия на каждый кубит компьютера. Примем, например, что над каждым кубитом регистра совершается преобразование Адамара:
В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 -n/2 . Каждое базисное состояние представляет собой двоичное число от до. Горизонтальные линии на рисунке обозначают оси времени.
Выполнение алгоритма совершается путем унитарного преобразования суперпозиции. представляет собой унитарную матрицу размерности 2 п . При физическом осуществлении посредством импульсных воздействий на кубиты извне матрица должна быть представлена как векторное произведение матриц размерности 2 и . Последние могут быть выполнены последовательным воздействием на единичные кубиты или пары кубитов :
Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений. Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).
Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции
Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии. За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п -- 1 . Этот феномен получил название квантового параллелизма.
Измерение результата вычислений сводится к проецированию вектора суперпозиции в (4) на вектор одного из базисных состояний :
Здесь проступает одно из слабых мест квантового компьютера: число в процессе измерения "выпадает" по закону случая. Чтобы найти при заданном , надо много раз провести вычисления и измерения, пока случайно не выпадет .
При анализе унитарной эволюции квантовой системы, совершающей вычислительный процесс, выявляется важность физических процессов типа интерференции. Унитарные преобразования совершаются в пространстве комплексных чисел, и сложение фаз этих чисел носит характер интерференции. Известна продуктивность преобразований Фурье в явлениях интерференции и спектроскопии. Оказалось, что и в квантовых алгоритмах неизменно присутствуют преобразования Фурье. Преобразование Адамара является простейшим дискретным фурье-преобразованием. Вентили типа NOT и СNOT могут быть осуществлены непосредственно на интерферометре Маха-Зендера с использованием явления интерференции фотона и вращения его вектора поляризации.
Исследуются различные пути физической реализации квантовых компьютеров. Модельные эксперименты по квантовому компьютингу выполнены на импульсном ядерном магнитно-резонансном спектрометре. В этих моделях работало два или три спина (кубита), например два спина ядер 13 С и один спин протона в молекуле трихлорэтилена
Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 1020).
К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).
1. Нужно найти способы "инициализации" кубитов компьютера в состояние. Для спиновых систем в кристаллах очевидно применение сверхнизких температур и сверхсильных магнитных полей. Применение поляризации спинов накачкой может оказаться полезным при одновременном применении охлаждения и больших магнитных полей.
Для ионов в вакуумных ловушках сверхнизкое охлаждение ионов (атомов) достигается лазерными методами. Очевидна также необходимость холодного и сверхвысокого вакуума.
2. Необходимо иметь технологию избирательного воздействия импульсами на любой выбранный кубит. В области радиочастот и спинового резонанса это означает, что каждый спин должен обладать своей резонансной частотой (в терминах спектроскопического разрешения). Различия резонансных частот для спинов в молекулах обусловлены химическими сдвигами для спинов одного изотопа и одного элемента; необходимые различия частот имеются для спинов ядер различных элементов. Однако здравый смысл подсказывает, что эти дарованные природой различия резонансных частот вряд ли достаточны, чтобы работать с 103 спинов.
Более перспективными представляются подходы, когда можно управлять извне резонансной частотой каждого кубита. В предложении о кремниевом квантовом компьютере кубитом служит ядерный спин примесного атома 31 Р. Частота резонанса определяется константой А сверхтонкого взаимодействия ядерного и электронного спинов атома 31 Р. Электрическое поле на наноэлектроде, находящемся над атомом 31 Р, поляризует атом и изменяет константу А (соответственно резонансную частоту ядерного спина). Таким образом, наличие электрода встраивает кубит в электронную схему и настраивает его резонансную частоту.
3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида. Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов. Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31Р обусловливает возникновение взаимодействия вида между ядерными спинами.
Чтобы обеспечить операцию, где и -- отдаленные кубиты, между которыми взаимодействие вида отсутствует, необходимо применить в компьютере операцию обмена состояниями по цепочке так что обеспечивает операцию, поскольку состояние совпадает с состоянием.
4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения -- декогеренизацию. По существу, декогеренизация -- это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е0 и Е1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация -- это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10-5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.
Возможно и активное подавление процесса декогеренизации, если над системой кубитов проводить периодические измерения. Измерение с большой вероятностью обнаружит частицу в "правильном" состоянии, а малые случайные изменения вектора состояния при измерении коллапсируют (квантовый эффект Зенона). Однако трудно пока сказать, насколько полезным может быть такой прием, поскольку такие измерения сами по себе могут воздействовать на вычислительный процесс и нарушить его.
5. Состояния кубитов после завершения вычислительного процесса должны быть измерены, чтобы определить результат вычисления. Сегодня нет освоенной технологии таких измерений. Очевиден, однако, путь поисков такой технологии: надо использовать методы усиления в квантовом измерении. Например, состояние ядерного спина передается электронному спину; от последнего зависит орбитальная волновая функция; зная орбитальную волновую функцию, можно организовать передачу зарядов (ионизацию); присутствие или отсутствие заряда одиночного электрона можно обнаружить классическими электрометрическими методами. Большую роль в этих измерениях будут играть, вероятно, методы зондовой силовой микроскопии.
К настоящему времени открыты квантовые алгоритмы, приводящие к экспоненциальному ускорению вычислений по сравнению с вычислениями на классическом компьютере. К ним относится алгоритм Шора определения простых множителей больших (многоразрядных) чисел. Эта чисто математическая проблема тесно связана с жизнью общества, так как на "невычислимости" таких множителей построены современные шифровальные коды. Именно это обстоятельство вызвало сенсацию, когда был открыт алгоритм Шора. Для физиков важно, что и решение квантовых задач (решение уравнения Шрёдингера для многочастичных систем) экспоненциально ускоряется, если использовать квантовый компьютер.
Наконец, очень важно, что в ходе исследований задач квантового компьютинга подвергаются новому анализу и экспериментальной проверке основные проблемы квантовой физики: проблемы локальности, реальности, дополнительности, скрытых параметров, коллапса волновой функции.
Идеи квантового компьютинга и квантовой связи возникли спустя сто лет после рождения первоначальных идей квантовой физики. Возможность построения квантовых компьютеров и систем связи показана выполненными к настоящему времени теоретическими и экспериментальными исследованиями. Квантовая физика "достаточна" для проектирования квантовых компьютеров на различной "элементной базе". Квантовые компьютеры, если их удастся построить, будут техникой XXI века. Для их изготовления потребуется создание и развитие новых технологий на нанометровом и атомном уровне размеров. Эта работа может занять, по-видимому, несколько десятилетий. Построение квантовых компьютеров было бы еще одним подтверждением принципа неисчерпаемости природы: природа имеет средства для осуществления любой корректно сформулированной человеком задачи.
В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.
Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.
Шифрование, однако, только одно возможное применение квантового компьютера. Шор разработал целый набор математических операций, которые могут быть выполнены исключительно на квантовом компьютере. Некоторые из этих операций используются в его алгоритие факторизации. Далее, Фейнман утверждал, что квантовый компьютер может действовать как моделирующее устройство для квантовой физики, потенциально открывая двери ко многим открытиям в этой области. В настоящее время мощь и возможности квантового компьютера, в основном, предмет теоретических рассуждений; появление первого по-настоящему функционального квантового компьютера, несомненно, принесет много новых и волнующих практических применений.
В представлении Шредингера изменение кубита во времени под действием унитарных операторов удобно представить графически. Данный подход широко используется в области квантовых вычислений. Так называемые квантовые цепи служат аналогом графического представления электрических цепей. Они также строятся из набора вентилей или гейтов по аналогии с цифровыми вентилями «И», «ИЛИ», «НЕ», триггерами, регистрами, сумматорами и так далее.
Пусть у нас имеется кубит в базисном состоянии «0». Опять же мы его можем представить вектор-столбцом (1 0). Если подать его на вход гейта, назовем его Х, то вектор состояния изменится. Данный вентиль представляется матрицей Паули сигма-х. Да, матрицы Паули помимо того, что они эрмитовы, они также еще и унитарны. Не все эрмитовы матрицы унитарны, но матрицы Паули именно такие.
Итак, умножением X-матрицы Паули на исходный вектор получим вектор-столбец (0 1). Он является вторым базисным кет-вектором |1>. То есть данный гейт перевел 0 в единицу. Данный вентиль также называют NOT, поскольку он выполняет отрицание, инверсию. Действительно, если далее поставить еще один такой гейт, то мы вернемся к состоянию ноль.
В отличие от классических бит, кубит может находиться в суперпозиции базисных векторов. Следующий вентиль называется гейт Адамара и представляется следующей унитарной матрицей. Он переводит состояние ноль в суперпозицию |0>+|1>.
Заметьте, что при действии этой матрицы на кет-вектор |1>, она переводит его в |0>-|1>.
С помощью этих двух вентилей мы можем графически представить рассмотренный в предыдущем видео эксперимент с интерферометром Маха-Цендера. Приведенные нами матрицы идентичны рассматриваемым там операторам эволюции. Прохождению фотоном полупрозрачного зеркала соответствует гейт Адамара. Зеркалу вентиль инверсии X. Второе полупрозрачное зеркало также представляется вентилем Адамара. Первый гейт переводит кубит в суперпозицию, второй ничего не делает с получившимся состоянием, а третий переводит суперпозицию обратно в базисный вектор.
Двухкубитные состояния графически представляются добавлением еще одной горизонтальной линии. Сейчас исходный вектор находится в состоянии |00>, которое равно тензорному произведению соответствующих однокубитных векторов. Он представляется вектор-столбцом с четырьмя компонентами.
Можно, например, поставить гейт Адамара на каждый кубит. Фактически это означает, что на исходный вектор надо подействовать тензорным произведением двух матриц Адамара. Мы имеем матрицу 4х4, умножаемую на четырехкомпонентный вектор-столбец. Результатом также будет четырехкомпонентный вектор-столбец.
Однако не каждую унитарную матрицу 4х4 можно разложить на тензорное произведение матриц 2х2. Примером может служить распространенный гейт CNOT – контролируемое отрицание. Он должен применяться сразу ко всему вектору двухкубитного состояния. Обычно его обозначают такими двумя кружочками.
Наиболее общий двухкубитный вектор состояния описывается суперпозицией четырех базисных векторов. Поэтому для его описания необходимы 4 комплексных числа – амплитуды вероятности.
Для трехкубитного вектора суперпозиция будет состоять из 2 3 , то есть восьми слагаемых. Унитарные операторы, действующие на такой восьмикомпонентный вектор-столбец представляются матрицами 8х8. Именно поэтому в случае квантовых вычислений моделирование на классическом компьютере становится невозможным уже при небольшом количестве кубит.
Так для оперирования стокубитным состоянием необходимо хранить 2 100 комплексных чисел только для описания самого вектора. 2 100 это уже больше количества элементарных частиц в наблюдаемой части Вселенной. Именно поэтому человечеству нужен аппаратный квантовый компьютер, а не его классический имитатор.
В интернете можно найти симуляторы квантовых цепей и поэкспериментировать с ними. Вот один из них, называется quirk. На выходе он показывает вероятность при измерении кубита обнаружить единицу. Также сферу Блоха, графически отображающую кубит точкой на сфере. И графическое отображения амплитуд вероятностей — два комплексных числа для одного кубита, четыре для двухкубитного состояния.
Изначально двухкубитный вектор у нас находится в состоянии базисного вектора |00>. То есть соответствующая амплитуда вероятности равна единице, а три другие нулю. Но в общем случае все четыре амплитуды ненулевые. Поставим для наглядности, какие-нибудь гейты, матрицы которых сами меняются со временем. Ну и, например, CNOT гейт. Видим, что все четыре амплитуды вероятности меняют свое значение.
Давайте соберем цепь, соответствующую нашему опыту с интерферометром Маха-Цендера. Поставим гейт Адамара. Вероятность в результате измерения получить единицу стала 50%. Сами амплитуды вероятности стали 0.707, то есть для нуля и для единицы.
Поставим NOT-гейт, то есть матрицу Паули Х. Ничего не поменялось. Второй вентиль Адамара вернул вектор состояния в исходный базисный вектор. Заметьте, что при переходе к трехкубитному вектору, амплитуд становится уже восемь. Для четырехкубитного 16. Ну и так далее. Данный симулятор может работать максимум с 16-тикубитным состоянием. Для этого он использует как минимум 2 16 , то есть 64кБ памяти. Для 32 кубит надо уже минимум 4Гб памяти. Требуемые ресурсы растут очень быстро. В данном симуляторе есть и уже собранные схемы популярных алгоритмов. Вот, например, цепь для проверки неравенств Белла, которые мы рассматривали в 26 и 27 частях.
Не следует однако представлять себе квантовый компьютер как аналог классического, но с экспоненциально большими вычислительными мощностями. Как часто говорят в научпопе – встроенный квантовый параллелизм. Действительно, существуют алгоритмы, позволяющие решить некоторые задачи на квантовом компьютере за приемлемое время, тогда как на классическом понадобились бы миллиарды лет. Но эти задачи очень специфичны, например, взятие дискретного логарифма от больших чисел или разложение больших чисел на сомножители.
То есть квантовый компьютер не всегда намного быстрее классического. Скорее его можно рассматривать как специализированный процессор для узкого круга задач. Те же самые операции с матрицами или моделирование квантовых явлений, например, для задач химии.
Но кто знает как будет развиваться данная область когда технология дойдет до серийного производства дешевых многокубитных квантовых процессоров.
Время от времени мы видим шквал новостей о квантовых вычислениях. Этой теме уделяется очень много внимания: одна компания заявила, что у нее есть алгоритм шифрования, который вам скоро понадобится, так как квантовые компьютеры делают современные алгоритмы шифрования бесполезными.
У человека любознательного такие заявления вызывают вопросы. Что такое квантовые вычисления (рисунок 1)? Это реально? Если да, то как это работает? И как это связано с криптографией? Затем появляются более личные вопросы. Могут ли квантовые вычисления изменить мои методы проектирования? Должен ли я изучить этот материал?
Даже в визуализации художников квантовые вычислительные элементы не похожи ни на что из цифрового аппаратного мира.
Рисунок 1 – Визуализация квантовых вычислительных элементов
Оказывается, это не слишком простые вопросы для изучения. Соответствующая литература в основном относится к одному из двух жанров. Первый предназначен для широкой читательской аудитории и рассматривает квантовую механику как чертовщину: темная, возможно, опасная, и абсолютно не понятная. После чтения такой литературы довольно сложно сделать какие-либо выводы.
Второй жанр совершенно другой, но столь же «полезный», написанный экспертами, для того, чтобы произвести впечатление на других экспертов. Эта жанр характеризуется употреблением таких терминов как машина Тьюринга, имя Ричарда Фейнмана, Гильбертово пространство и преобразование Адамара, все вышеупомянутое и еще примерно 75 слов, за которыми следует путаница уравнений с незнакомой и необъяснимой терминологией. Конечно же, вы все хорошо помните, что означает |0>!
Три параллельные вселенные
Одной из причин, почему эта тема настолько сложна, является то, что квантовые вычисления охватывают три дисциплины с очень разной терминологией и интересами. Все началось с физиков-теоретиков. Еще в 1980 году физик Пол Бениофф (Paul Benioff ) из Национальной Аргоннской лаборатории описал, как некоторые квантовомеханические эффекты могут быть использованы для реализации машины Тьюринга. Два года спустя известный физик Ричард Фейнман также поднял вопрос о компьютере с использованием квантового поведения.
Но идея была подхвачена совершенно другой группой: компьютерными специалистами и математиками. Взяв из физики основные идеи квантового бита (кубита) и обратимых унитарных преобразований (которые они называли квантовыми вентилями или кувентилями), компьютерные специалисты изучили, какие вычисления могли бы быть выполнены, если бы существовали идеальные кубиты и квантовые вентили. Они обнаружили случаи, когда такие предполагаемые компьютеры могли быть намного быстрее, чем обычные цифровые компьютеры.
Этот результат побудил физиков-экспериментаторов – третью группу – начать попытки по созданию физических устройств, которые могли бы быть приближенны к идеальным кубитам и квантовым вентилям. Это были долгие, ресурсоемкие исследования, которое до сих пор не доказали, что реально работающий квантовый компьютер физически возможен. Но такая возможность чрезвычайно обнадеживает.
Некоторые пояснения
Итак, что это за воображаемый компьютер, который нас интересует? Давайте сначала проясним некоторые недоразумения. Квантовый компьютер не является обычным компьютером, имитирующим квантовомеханические явления. Также это и не обычный цифровой компьютер, построенный из некоторых транзисторов (эпохи окончания закона Мура), настолько крошечных, что они хранят или переключают отдельные кванты энергии.
Вместо этого, квантовые компьютеры – это машины, основанные на уникальном поведении, описываемом квантовой механикой, и совершенно отличающимся от поведения классических систем. Одно из таких отличий – способность частицы или группы частиц в некотором отношении находиться только в двух дискретных квантовых базовых состояниях – назовем их 0 и 1. Мы обойдемся здесь без забавных скобок (обозначений принятых в квантовой теории – добавлено переводчиком) Примерами такого рода могут быть спин электрона, поляризация фотона или заряд квантовой точки.
Во-вторых, квантовые вычисления зависят от свойства суперпозиции – контринтуитивной способности частицы находиться в некоторой комбинации обоих базовых состояниях 0 и 1 одновременно, до тех пор, пока не произведено измерение. Как только вы измеряете такое состояние, оно превращается в 0 или 1, и вся остальная информация исчезает. Квантовая механика правильно описывает такое комбинированное состояние как сумму двух базовых состояний, каждое из которых умножается на некоторый комплексный коэффициент. Полная величина этих коэффициентов всегда равна 1. Такое состояние можно представить как единичный вектор, начинающийся в начале координат и заканчивающийся где-то на сфере, называемой сферой Блоха, которая приведена на рисунке 2. Ключевым моментом здесь является то, что квадрат (модуля – добавлено переводчиком) комплексного коэффициента для базового состояния 0 представляет вероятность того, что в результате измерения кубит будет обнаружен в базовом состоянии 0, аналогично для базового состояния 1. И когда вы производите измерение, вы всегда получите или точно состояние 0, или точно состояние 1.
Рисунок 2 – Сфера Блоха – один из способов визуализации квантовой суперпозиции в кубите
Это (свойство суперпозиции – добавлено переводчиком) важно, потому что позволяет кубиту быть в обоих состояниях 0 и 1 одновременно. Следовательно, регистр, состоящий из n кубит, может одновременно «содержать» все возможные двоичные числа n бит длиной. Это позволяет квантовому компьютеру выполнять одну операцию не только с одним n-разрядным целым числом, но и со всеми возможными n-разрядными целыми числами сразу – очень существенный параллелизм по мере увеличения n.
В-третьих, квантовые вычисления зависят от способности квантового вентиля изменять эти коэффициенты и, следовательно, вероятность измерения какого-либо определенного числа – предсказуемым образом. Если вы начинаете с состояния, в котором все коэффициенты во всех кубитах равны, а затем измерите все кубиты в регистре, вы равновероятно найдете любую строку бит между строкой из одних нулей и строкой из одних единиц, включительно. Но запустив это начальное состояние через тщательно подобранную последовательность квантовых вентилей, квантовый компьютер может изменить эти коэффициенты так, что состояние, которое вы наиболее вероятно измерите на выходе, будет представлять собой результат некоторого вычисления, например, весьма вероятно, что вы измерите биты числа, которое является точным квадратом.
Компьютер на бумаге
Но какое отношение все это имеет к реальным вычислениям? Чтобы ответить на этот вопрос, мы должны перенести наше внимание с физиков-теоретиков на компьютерных специалистов и математиков. Чтобы получить практические результаты, мы должны иметь возможность перевести регистр кубитов в определенную суперпозицию состояний. Нам нужны квантовые вентили, возможно, провода и какие-то устройства вывода результатов.
Все это легко для компьютерных специалистов – они просто могут предположить, что эти идеи уже воплощены в реальной жизни. Однако им придется пойти на уступки квантовой механике. Чтобы не нарушить законы квантовой физики, компьютерные специалисты должны потребовать, чтобы квантовые вентили были обратимы – вы можете поместить результат на выход и получить правильные входные значения на входе. И они настаивают на том, чтобы квантовые вентили были унитарными преобразованиями. В соответствии с матричной алгеброй, это означает, что, когда вы пропускаете состояние кубита через квантовый вентиль, состояние, которое вы получите, даст при измерении либо 0, либо 1, а сумма вероятностей из квадратов (модулей – добавлено переводчиком) этих коэффициентов останется равной единице.
Обратите внимание, что эти квантовые вентили, даже в теории, очень не похожи на обычные логические элементы. Например, большинство булевых функций не обратимы. Невозможно вывести входные данные с логического элемента И-НЕ, если выход не будет равен 0. И, конечно, логические элементы работают только с единицами и нулями (состояниями 1 и 0), в то время как квантовые вентили работают, вращая вектор внутри сферы Блоха. На самом деле между ними не существует ничего общего кроме названия.
Компьютерные специалисты выяснили, что для эмуляции машины Тьюринга достаточно очень небольшого набора квантовых вентилей – всего лишь набор одновходовых квантовых вентилей и один двухвходовой квантовый вентиль. Наиболее часто используемым примером двухвходового квантового вентиля является «контролируемое НЕ» (Сontrolled NOT – CNOT). Эта обратимая функция либо переворачивает векторное состояние кубита, либо оставляет его неизменным, в зависимости от состояния второго кубита. Это скорее похоже на квантовую аналогию с «исключающим ИЛИ».
Возможные преимущества
Мы все еще не ответили на вопрос, как все это можно использовать. Ответ заключается в том, что если вы соедините подходящим образом достаточное количество квантовых вентилей вместе, и если вы можете приготовить входные кубиты представляющие все возможные числа в вашей области входных данных, тогда на выходе массива квантовых вентилей вы, теоретически, можете измерить биты, которые представляют значения некоторой полезной функции.
Приведем пример. В 1994 году математик Питер Шор, в Bell Labs, разработал алгоритм факторизации (разложения на простые сомножители – добавлено переводчиком) очень больших чисел с использованием квантовых подпрограмм. Такая факторизация является жизненно важной проблемой в прикладной математике, потому что не существует аналитического решения: единственный способ – метод проб и ошибок, и вы можете всего лишь сделать алгоритм быстрее, выбрав более искусным образом соответствующие пробные числа. Соответственно, когда вы делаете входное число очень большим, количество проб и ошибок становится огромным. Не случайно это является основой алгоритмов криптографии, подобных RSA. RSA и шифры на основе эллиптических кривых трудно взломать, особенно потому, что так трудно факторизовать огромные числа.
Алгоритм Шора объединил некоторые традиционные вычисления с двумя квантовыми функциями, которые непосредственно ускоряют алгоритм в части метода проб и ошибок, по сути, перебирая все возможные числа в одно и то же время, демонстрация работы алгоритма приведена на рисунке 3. Одна из этих квантовых функций выполняет модульное возведение в степень, а другая осуществляет квантовую версию быстрого преобразования Фурье (БПФ). По причинам, которые мог бы полюбить только математик, если бы мы ввели набор из n кубитов, подготовленных так, что вместе они представляют все возможные двоичные числа до длины n, то в квантовых вентилях различные состояния в суперпозиции взаимно компенсируют друг друга – подобно интерференции двух когерентных световых лучей – и мы остаемся с определенной структурой состояний в выходном регистре.
Рисунок 3 – Алгоритм Шора зависит от квантовых подпрограмм для модульного возведения в степень и операций БПФ. (рисунок предоставлен Tyson Williams)
Эта процедура не дает простой множитель – это лишь промежуточный шаг, который позволяет вычислить возможный простой множитель. Такое расчет выполняется путем измерения кубитов, – отметим, что здесь мы находимся в области возможности, но не точности, измерения наиболее вероятного состояния каждого кубита – а затем, чтобы убедиться в правильности результата, необходимо произвести множество обычных вычислений на обычном процессоре (CPU).
Все это может показаться безнадежно сложным и неосуществимым. Но способность квантового возведения в степень и квантового БПФ работать одновременно со всеми возможными степенями числа 2, чтобы найти наибольший простой множитель, делает алгоритм Шора быстрее, чем обычные вычисления для больших чисел, даже при использовании довольно медленных теоретических квантовых подпрограмм.
Алгоритм Шора являет собой яркий образец квантовых вычислений, потому что он одновременно не похож на обычные вычисления и потенциально чрезвычайно важен. Но он не одинок. Национальный институт стандартов и технологий США (NIST) поддерживает большую библиотеку алгоритмов квантовых вычислений в своем Зоопарке Квантовых Алгоритмов, по адресу math.nist.gov/quantum/zoo/ .
Являются ли эти алгоритмы просто математическими упражнениями? Пока еще слишком рано это утверждать. Но на практике исследователи действительно создали лабораторные квантовые калькуляторы с несколькими рабочими кубитами. Эти машины успешно разложили на простые множители число 15 (впервые это было сделано в IBM в 2001 году), вполне ожидаемо получив в результате 3 и 5, а текущий мировой рекорд составляет число 21 (сделано объединенной командой из нескольких институтов в 2012 году). Так что для небольших чисел идея работает. Пригодность такого подхода для больших чисел можно будет проверить только в будущем на машинах с большим количеством кубитов. И это переносит вопрос в практическую плоскость.
Путь к реализации
Для создания работоспособных квантовых вычислительных устройств необходимо пройти ряд этапов реализации. Мы должны построить рабочие кубиты – не только пять, но тысячи. Мы должны организовать структуру из квантовых вентилей и эквивалент проводов – если только мы не сможем заставить вентили действовать непосредственно на состояние во входном квантовом регистре. Все это сложные задачи, и график их решения непредсказуем.
К сожалению, проблемы связаны не столько с новизной проблем, сколько с законами квантовой механики и классической физики. Возможно, самая главная и наименее знакомая из них, называется декогеренцией. Роль кубит состоит в том, чтобы удерживать физический объект – например, ион, пакет фотонов или электрон — на месте, чтобы мы могли воздействовать на него и в конечном итоге измерять квантованную величину, такую как заряд или спин. Чтобы эта величина вела себя квантовым, а не классическим образом, мы должны иметь возможность ограничить ее состояние суперпозицией двух чистых базовых состояний, которые мы называли 0 и 1.
Но природа квантовых систем такова, что связывает их с вещами вокруг них, значительно увеличивая количество возможных базовых состояний. Физики называют такое размытие чистых состояний декогеренцией. Аналогией может быть когерентный лазерный луч в световоде, рассеивающийся на неоднородностях материала и размывающейся от суперпозиции двух мод в полностью некогерентный свет. Задачей создания физического кубита является как можно дольше предотвращать декогеренцию.
На деле это означает, что даже один кубит это сложный лабораторный инструмент, возможно, с использованием лазеров или высокочастотных радиопередатчиков, точно контролируемые электрические и магнитные поля, точные размеры, специальные материалы и, возможно, криогенное охлаждение. Его использование, по сути, является сложной экспериментальной процедурой. Даже при всех этих усилиях, сегодня это «как можно дольше» измеряется десятками микросекунд. Таким образом, у вас очень мало времени для выполнения квантовых вычислений, до того, как ваши кубиты потеряют свою согласованность. То есть, до того как информация исчезнет.
Сегодня эти ограничения исключают возможность больших квантовых регистров или проведения вычислений, для которых требуется более нескольких микросекунд. Тем не менее, в настоящее время в микроэлектронике ведутся исследования по созданию гораздо более обширных массивов кубитов и квантовых вентилей.
Однако сама эта работа несколько бессвязна, потому что пока нет определенности в отношении того, какое физическое явление использовать для хранения квантовых состояний. Существуют конструкции кубит, которые квантуют поляризацию фотонов, заряд электронов, захваченных квантовыми точками, чистый спин сверхохлажденных ионов в ловушке, заряд в устройстве, называемом трансмоном, и некоторые другие подходы.
Тип кубита, который вы выберете, естественно определит реализацию квантовых вентилей. Например, вы можете использовать взаимодействие радиоимпульсов с внутренними спинами в молекулах в ловушке или взаимодействие расщепителей пучков с фотонными модами в волноводах. Очевидно, что существо дела находится глубоко в области экспериментальной физики. И, как уже упоминалось, реализация кубитов или квантовых вентилей требует использования большого количества различного оборудования, от цифровой логики до лазеров или радиопередатчиков, антенн и до криогенных охладителей.
Реализация кубит также зависит, от того каким образом измеряется состояние кубит. Вам может потребоваться сверхчувствительный фотометр или болометр, мост сопротивлений или какое-либо другое невероятно чувствительное устройство для измерения кубитов и перевода состояния суперпозиции в базовое состояние. И, кроме того, этот процесс измерения состояния кубит вызывает еще одну проблему, незнакомую традиционным вычислениям: получение неправильного ответа.
Сомнения
Существует два основных типа проблем с извлечением базового состояния из кубита. Во-первых, вы измеряете квантовую суперпозицию, а не классическую величину. Предполагая, что кубит остался когерентным, вы получите одно или другое из базовых состояний, но вы не можете заранее быть уверены какое именно из них вы получите: вы можете быть уверены только в том, что вероятность того, что вы получите определенное состояние, будет квадратом (модуля – добавлено переводчиком) коэффициента этого состояния в суперпозиции. Если вы измеряете кубит в точно таком же состоянии сто раз, вы получите распределение нулей и единиц, которое сходится к квадратам (модулей) коэффициентов.
Таким образом, вы не знаете, действительно ли то базовое состояние, которое вы измерили в некоторой попытке, имеет наибольшую вероятность. После того, как вы считали квантовый выходной регистр, измерив биты, тем самым установив их все в базовые состояния – у вас есть три варианта. Вы можете усомниться, что у вас есть правильный ответ и продолжить дальше. Вы можете проверить традиционными вычислениями, как это делает алгоритм Шора, чтобы узнать, действительно ли число, которое вы считали, является правильным решением. Или же, вы можете повторить вычисление большое количество раз, последовательно или параллельно, и взять наиболее часто встречающийся результат. Также можно организовать свои вычисления таким образом, чтобы ответом было распределение вероятностей базовых состояний, а не конкретное двоичное число. В этом случае также необходимо повторение..
Это верно даже для теоретически совершенного квантового компьютера. Но в действительной реализации есть еще одна проблема: старый добрый классический шум. Даже если все идет хорошо, нет декогеренции кубитов, и вычисление предназначено для получения ответа с очень высокой вероятностью, вы все еще наблюдаете за кубитами, пытаясь измерить очень и очень маленькие физические величины. Шум все равно присутствует. Опять же, единственным решением является либо обнаружение ошибки путем дальнейших вычислений, либо выполнение вычислений столько раз, что вы готовы принять любую оставшуюся в результате этого неопределенность. Концепция гарантированного правильного ответа чужда самой сути квантовых вычислений.
Если все это не рисует розовую картину будущего квантовых вычислений, то к этому следует отнестись очень серьезно. Идут поиски наилучшего выбора для реализации кубитов, хотя ответ может оказаться зависящим от алгоритма. Специалисты по микроэлектронике работают над миниатюризацией квантовых компонентов на основе новых материалов и структур, которые позволили бы создавать очень большие массивы квантовых вычислительных устройств, и которые могли бы массово производиться подобно чипам традиционных процессоров. Компьютерные специалисты разрабатывают прототипы ассемблеров и компиляторов, которые могут преобразовать алгоритм в расположение квантовых регистров и квантовых вентилей в конкретной технологии.
Стоит ли оно того? Вот один факт. Шор подсчитал, что скромный гибридный, то есть квантовый плюс обычный, компьютер может взломать мощный алгоритм шифрования RSA быстрее, чем обычный компьютер может его зашифровать. Были получены аналогичные результаты для таких задач, как сортировка и распутывание других аналогичных сложных математических задач. Итак, в этой области присутствует достаточно перспектив, чтобы исследователи не теряли энтузиазм. Но было бы неплохо увидеть все это еще при жизни.
Причина того, что подобное моделирование имеет важное значение, заключается в том, что классические цифровые компьютеры практически ничего не могут поделать с мультиреференсными состояниями; во многих случаях классические методы вычислений не только количественно, но и качественно не в состоянии описать электронную структуру молекул.
Важная проблема, которая была недавно решена, заключалась в том, чтобы найти способы, которыми квантовый компьютер мог бы эффективно выполнять расчеты и с требуемой химической точностью для реального мира. Программа была запущена на 20-кубитном процессоре IBM.
Почему химия попала в поле такого интереса? Химия - одно из самых выгодных коммерческих приложений по ряду причин. Ученые рассчитывают найти более энергоэффективные материалы, которые можно будет использовать в аккумуляторах или солнечных панелях. Существуют также экологические преимущества: около двух процентов энергии в мире уходит на производство удобрений, которые ужасно неэффективны и могут быть улучшены путем сложного химического анализа.
Наконец, существуют приложения в персонализированной медицине, с возможностью предсказывать, как фармацевтические препараты будут влиять на людей, основываясь на их генетике. В долгосрочной перспективе - возможность разработать препарат для конкретного человека для максимально эффективного лечения и минимизации побочных эффектов.
У CQC и JSR Corp было две стратегии, которые позволили ученым осуществить этот прорыв. Во-первых, они использовали собственный компилятор CQC для наиболее эффективного преобразования компьютерной программы в инструкции для манипулирования кубитом. Такая эффективность особенно важна на современных малокубитных машиных, в которых каждый кубит важен и необходим, а скорость исполнения имеет решающее значение.
Во-вторых, они использовали квантовое машинное обучение, специальное подполе машинного обучения, которое использует векторные амплитуда, а не просто вероятности. Используемый метод квантового машинного обучения был специально разработан для малокубитных квантовых компьютеров, с частичной разгрузкой при помощи традиционных процессоров.
В ближайшие несколько лет ожидается значительное улучшение квантового как аппаратного, так и программного обеспечения. По мере того, как расчеты становятся все более точными, все больше отраслей могут воспользоваться преимуществами приложений квантовых компьютеров, включая и квантовую химию. Gartner прогнозирует, что уже через четыре года у 20% корпораций будет бюджет на квантовые вычисления. Через десять лет они станут неотъемлемым компонентом технологий.
Историческая справка
Квантовые вычисления немыслимы без контроля над квантовым состоянием отдельных элементарных частиц. Двум физикам - французу Сержу Лрошу и американцу Дэвиду Вайнленду - это удалось. Лрош ловил в резонатор одиночные фотоны и надолго «отцеплял» их от внешнего мира. Вайнленд собирал в ловушку одиночные ионы с опреденными квантовыми состояниями и изолировал их от внешнего воздействия. Арош использовал атомы, чтобы наблюдать за состоянием фотона. Вайнленд применял фотоны, чтобы изменять состояния ионов. Им удалось продвинуться в изучении взаимоотношения квантового и классического миров. В 2012 г. им была вручена Нобелевская премия по физике за «прорывные экспериментальные методы, которые сделали возможными измерение отдельных квантовых систем и управление ими».
В основе работы квантовых компьютеров лежат свойства квантового бита информации. Если в вычислительных процессах используется п кубитов, то гильбертово пространство состояний квантовой системы имеет размерность, равную 2". Под гильбертовым пространством будем понимать га-мерное векторное пространство, в котором определено скалярное произведение при условии стремления значения п к бесконечности.
В нашем случае это означает, что имеется 2" базовых состояний, а компьютер может оперировать суперпозицией из этих 2" базовых состояний.
Заметим, что воздействие на какой-либо кубит немедленно приводит к одновременному изменению всех 2” базовых состояний. Это свойство носит название «квантовый параллелизм ».
Квантовые вычисления являются унитарными преобразованиями. Это означает, что осуществляется линейное преобразование с комплексными коэффициентами, сохраняющее неизменной сумму квадратов преобразуемых переменных. Унитарное преобразование является ортогональным преобразованием, при котором коэффициенты образуют унитарную матрицу.
Под унитарной матрицей будем понимать квадратную матрицу ||aj|, произведение которой на комплексную сопряженную и транспонированную матрицу || aJI дает единичную матрицу. Числа a jk и a ki комплексные. Если числа a ik являются действительными числами, то унитарная матрица будет ортогональной. Некоторое число кубитов формирует квантовый регистр компьютера. В такой цепочке квантовых битов можно проводить одно- и двухбитовые логические операции подобно тому, как в классическом регистре проводятся операции НЕ, И-НЕ, 2 ИЛИ-HE и т.д. (рис. 5.49).
Определенное число N регистров формируют по существу квантовый компьютер. Работа квантового компьютера происходит в соответствии с разработанными алгоритмами вычислений.
Рис. 5.49.
NOT - булевское НЕ; CNOT - контролируемое НЕ
Кубиты как носители информации обладают рядом интересных свойств, совершенно отличающих их от классических битов. Одним из главных тезисов квантовой теории информации является запутывание состояний. Предположим, что имеется два двухуровневых кубита А и В, реализованных в виде атома с электронным или ядерным спином, молекулы с двумя ядер- ными спинами. Вследствие взаимодействия двух подсистем А и В возникает нелокальная корреляция, имеющая чисто квантовый характер. Такая корреляция может быть описана матрицей плотности смешанного состояния
где p i - населенность или вероятность i- го состояния, так что р { + р 2 + р 3 + + Ра = 1-
Свойство когерентных квантовых состояний иметь сумму вероятностей, равную единице, называется запутыванием, или сцеплением, состояний. Запутанные, или сцепленные, квантовые объекты связаны между собой независимо от того, насколько далеко они расположены друг от друга. Если измеряется состояние одного из сцепленных объектов, то немедленно получаются сведения о состоянии других объектов.
Если два кубита сцеплены между собой, то они лишены индивидуальных квантовых состояний. Они зависят друг от друга так, что измерение для одного тина дает «О», а для другого - «1» и наоборот (рис. 5.50). В этом случае говорят, что максимально сцепленная пара несет один e-бит сцеплснности.
Запутанные состояния являются ресурсом устройств квантового вычислителя, и для пополнения числа запутанных состояний необходимо разработать методы надежной генерации сцепленных кубитов. Одним из мето-
Рис. 5.50. Схема максимально сцепленной пары кубитов дов является алгоритмический способ получения запутанных кубитов на ионах в ловушках, ядерных спинах или паре фотонов. Весьма эффективным может быть процесс распада частицы в синглетном состоянии на две частицы. В этом случае генерируются пары частиц, запутанные по координате, импульсу или спину.
Разработка всеобъемлющей теории запутанности является ключевой задачей квантовой теории информации. С ее помощью можно будет приблизиться к решению проблем телепортации, сверхплотного кодирования, криптографии, сжатия данных. С этой целью разрабатываются квантовые алгоритмы, среди которых квантовые преобразования Фурье.
Схема вычисления на квантовом компьютере имеет следующий алгоритм: формируется система кубитов, на которой записывается начальное состояние. Посредством унитарных преобразований состояние системы и ее подсистем изменяется при выполнении логических операций. Завершается процесс измерением новых значений кубитов. Роль соединительных проводников классического компьютера играют кубиты, а логических блоков классического компьютера - унитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была сформулирована в 1989 г. Дэвидом Дойчем. Затем он предложил универсальный логический блок, с помощью которого можно выполнять любые квантовые вычисления.
Алгоритм Дойна - Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной /(/?) постоянной (f x {ri) = О, f 2 {ri) = 1 независимо от п) или «сбалансированной» (f 3 (0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).
Выяснилось, что для построения любого вычисления достаточно двух базовых операций. Квантовая система дает результат, только с некоторой вероятностью являющийся правильным. Но за счет небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице. С помощью базовых квантовых операций можно симулировать работу обычных логических элементов, из которых сделаны обычные компьютеры.
Алгоритм Гровера позволяет найти решение уравнения f(x) = 1 для 0 х за время O(VN) и предназначен для поиска в базе данных. Квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска на классическом компьютере.
Алгоритм факторизации Шора позволяет определить для простых множителей аиЬ заданное целое число М= a"Xb путем использования соответствующей квантовой схемы. Этот алгоритм позволяет находить сомножители А-значного целого числа. С его помощью можно оценить время вычислительного процесса. Одновременно алгоритм Шора можно интерпретировать как пример процедуры определения энергетических уровней квантовой вычислительной системы.
Алгоритм Залки - Визнера позволяет моделировать унитарную эволюцию квантовой системы п частиц за почти линейное время с использованием О(п) кубитов.
Алгоритм Саймона решает проблему «черного ящика» экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.
Алгоритм коррекции ошибок позволяет повысить помехоустойчивость квантовой вычислительной системы, подверженной разрушению хрупких квантовых состояний. Суть этого алгоритма заключается в том, что нс требуются клонирование кубитов и выяснение их состояния. Формируется квантовая логическая схема, которая способна фиксировать ошибку в любом кубите без фактического считывания индивидуального состояния. Например, проходящий через такое устройство триплет 010 обнаруживает неправильный средний бит. Устройство переворачивает его, не определяя конкретные значения ни одного их трех битов. Таким образом, на основе теории информации и квантовой механики возник один из фундаментальных алгоритмов - квантовая коррекция ошибок.
Перечисленные проблемы важны для создания квантового компьютера, однако они относятся к компетенции квантовых программистов.
Квантовый компьютер прогрессивнее классического по ряду показателей. Большинство современных компьютеров работают по фон-нейманов- ской либо по гарвардской схеме: п бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом компьютере система из п кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2" базовых состояний одновременно. Теоретически новая схема может работать в экспоненциальное число раз быстрее классической. Практически квантовый алгоритм поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов.
