Вычисление квантов времени выдаваемых на процесс. Квантовые компьютеры. Путь к реализации

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

Ограниченные возможности современных компьютеров

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

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

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

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

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

Как мы увидим в дальнейшем, квантовые компьютеры никоим образом не представляют собой попытку решения проблемы миниатюризации базовых элементов процессоров.

Решение проблемы миниатюризации транзисторов, поиск новых материалов для создания элементной базы микроэлектроники, поиск новых физических принципов для приборов с характерными размерами, сравнимыми с длиной волны Де-Бройля, имеющей величину порядка 20 нм, - эти вопросы стоят на повестке дня уже почти два десятилетия. В результате их решения была разработана нанотехнология. Серьезной проблемой, с которой пришлось столкнуться при переходе в область наноэлектронных устройств, является уменьшение рассеиваемой энергии в процессе вычислительных операций. Мысль о возможности «логически обратимых» операций, не сопровождающихся рассеянием энергии, впервые высказал Р.Ландауер еще в 1961 году. Существенный шаг в решении данной задачи был сделан в 1982 году Ч.Беннеттом, который теоретически доказал, что универсальный цифровой компьютер может быть построен на логически и термодинамически обратимых вентилях таким образом, что энергия будет рассеиваться только за счет необратимых периферийных процессов ввода информации в машину (приготовление исходного состояния) и соответственно вывода из нее (считывание результата). К типичным обратимым универсальным вентилям относятся вентили Фредкина и Тоффоли.

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

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

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

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

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

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

Забегая вперед, отметим, что с квантовыми вычислениями связывают перспективы решения NP-полных задач за полиномиальное время.

Квантовая физика

Конечно, квантовая физика слабо связана с тем, что называют элементной базой современных компьютеров. Однако, говоря о квантовом компьютере, избежать упоминания некоторых специфических терминов квантовой физики просто невозможно. Мы понимаем, что далеко не все изучали легендарный третий том «Теоретической физики» Л.Д.Ландау и Е.М.Лифшица и для многих такие понятия, как волновая функция и уравнение Шредингера, - это что-то из потустороннего мира. Что же касается специфического математического аппарата квантовой механики, то это сплошные формулы и малопонятные слова. Поэтому мы постараемся придерживаться общедоступного уровня изложения, избегая по возможности тензорного анализа и прочей специфики квантовой механики.

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

История квантовой физики началась 14 декабря 1900 года. Именно в этот день немецкий физик и будущий нобелевский лауреат Макс Планк доложил на заседании Берлинского физического общества о фундаментальном открытии квантовых свойств теплового излучения. Так в физике появилось понятие кванта энергии, а среди других фундаментальных постоянных - постоянная Планка.

Открытие Планка и появившаяся затем, в 1905 году, теория фотоэлектрического эффекта Альберта Эйнштейна, а также создание в 1913 году Нильсом Бором первой квантовой теории атомных спектров стимулировали создание и дальнейшее бурное развитие квантовой теории и экспериментальных исследований квантовых явлений.

Уже в 1926 году Эрвин Шредингер сформулировал свое знаменитое волновое уравнение, а Энрико Ферми и Поль Дирак получили квантово-статистическое распределение для электронного газа, учитывающее заполнение отдельных квантовых состояний.

В 1928 году Феликс Блох произвел анализ квантово-механической задачи о движении электрона во внешнем периодическом поле кристаллической решетки и показал, что электронный энергетический спектр в кристаллическом твердом теле имеет зонную структуру. Фактически это стало началом нового направления в физике - теории твердого тела.

Весь XX век - это период интенсивного развития квантовой физики и всех тех разделов физики, для которых квантовая теория стала прародителем.

Появление квантовых вычислений

Идея использования квантовых вычислений впервые была высказана советским математиком Ю.И. Маниным в 1980 году в его знаменитой монографии «Вычислимое и невычислимое». Правда, интерес к его труду возник лишь два года спустя, в 1982 году, после опубликования статьи на ту же тему американского физика-теоретика нобелевского лауреата Ричарда Фейнмана. Он заметил, что определенные квантово-механические операции нельзя в точности переносить на классический компьютер. Это наблюдение привело его к мысли, что подобные вычисления могут быть более эффективными, если их осуществлять при помощи квантовых операций.

Рассмотрим, к примеру, квантово-механическую задачу об изменении состояния квантовой системы, состоящей из n спинов, за определенный промежуток времени. Не вникая в подробности математического аппарата квантовой теории, отметим, что общее состояние системы из n спинов описывается вектором в 2 n -мерном комплексном пространстве, а изменение ее состояния - унитарной матрицей размером 2 n x2 n . Если рассматриваемый промежуток времени очень мал, то матрица устроена очень просто и каждый из ее элементов легко вычислить, зная взаимодействие между спинами. Если же необходимо узнать изменение состояния системы за большой промежуток времени, то нужно перемножать такие матрицы, причем для этого требуется экспоненциально большое количество операций. Опять мы сталкиваемся с PN-полной задачей, нерешаемой за полиномиальное время на классических компьютерах. В настоящее время способа упростить данное вычисление не существует, и, скорее всего, моделирование квантовой механики является экспоненциально сложной математической задачей. Но если классические компьютеры не способны решать квантовые задачи, то, возможно, для этого целесообразно использовать саму квантовую систему? И если это действительно возможно, то подходят ли квантовые системы для решения других вычислительных задач? Подобные вопросы как раз и рассматривались Фейнманом и Маниным.

Уже в 1985 году Дэвид Дойч предложил конкретную математическую модель квантовой машины.

Однако вплоть до середины 90-х годов направление квантовых вычислений развивалось довольно вяло. Практическая реализация квантовых компьютеров оказалась весьма сложной. К тому же в научном сообществе с пессимизмом относились к тому, что квантовые операции способны ускорить решение определенных вычислительных задач. Так продолжалось вплоть до 1994 года, когда американский математик Питер Шор предложил для квантового компьютера алгоритм разложения n -значного числа на простые множители за время, полиномиально зависящее от n (квантовый алгоритм факторизации). Квантовый алгоритм факторизации Шора стал одним из основных факторов, приведших к интенсивному развитию квантовых методов вычислений и появлению алгоритмов, позволяющих решать некоторые NP-проблемы.

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

Идея квантовых вычислений

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

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

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

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

Теперь обобщим пример с поляризацией фотона на любую двухуровневую квантовую систему.

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

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

Вообще, понятие измерения в квантовой физике играет особую роль, и не стоит рассматривать его как измерение в классическом понимании. Измерение квантовой системы происходит всякий раз, когда она приходит во взаимодействие с «классическим» объектом, то есть с объектом, подчиняющимся законам классической физики. В результате такого взаимодействия состояние квантовой системы изменяется, причем характер и величина этого изменения зависят от состояния квантовой системы и потому могут служить его количественной характеристикой.

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

Итак, чтобы измерить квантовую систему, необходимо каким-то образом подействовать на нее классическим объектом, после чего ее первоначальное состояние будет нарушено. Кроме того, можно утверждать, что в результате измерения квантовая система будет переведена в одно из своих базисных состояний. К примеру, для измерения двухуровневой квантовой системы требуется как минимум двухуровневый классический объект, то есть классический объект, который может принимать два возможных значения: 0 и 1. В процессе измерения состояние квантовой системы будет преобразовано в один из базисных векторов, причем если при измерении классический объект принимает значение равное 0, то квантовый объект преобразуется к состоянию |0, а в случае если классический объект принимает значение равное 1, то квантовый объект преобразуется к состоянию |1.

Таким образом, хотя квантовая двухуровневая система может находиться в бесчисленном множестве состояний суперпозиции, но в результате измерения она принимает только одно из двух возможных базисных состояний. Квадрат модуля амплитуды |a| 2 определяет вероятность обнаружения (измерения) системы в базисном состоянии |1, а квадрат модуля амплитуды |b| 2 - в базисном состоянии |0.

Однако вернемся к нашему примеру с поляризованным фотоном. Для измерения состояния фотона (его поляризации) нам потребуется некоторое классическое устройство с классическим базисом {1,0}. Тогда состояние поляризации фотона a|1+b|0 будет определено как 1 (горизонтальная поляризация) с вероятностью |a| 2 и как 0 (вертикальная поляризация) с вероятностью |b| 2 .

Поскольку измерение квантовой системы приводит ее к одному из базисных состояний и, следовательно, разрушает суперпозицию (к примеру, при измерении получается значение равное |1), то это означает, что в результате измерения квантовая система переходит в новое квантовое состояние и при следующем измерении мы получим значение |1 со стопроцентной вероятностью.

Вектор состояния двухуровневой квантовой системы называется также волновой функцией квантовых состояний y двухуровневой системы, или, в интерпретации квантовых вычислений, кубитом (quantum bit, qubit). В отличие от классического бита, который может принимать только два логических значения, кубит - это квантовый объект, и число его состояний, определяемых суперпозицией, неограниченно. Однако еще раз подчеркнем, что результат измерения кубита всегда приводит нас к одному из двух возможных значений.

Теперь рассмотрим систему из двух кубитов. Измерение каждого из них может дать значение классического объекта 0 или 1. Поэтому у системы двух кубитов имеется четыре классических состояния: 00, 01, 10 и 11. Аналогичные им базисные квантовые состояния: |00, |01, |10 и |11. Соответствующий вектор квантового состояния записывается в виде a |00+ b |01+ c |10+ d |11, где |a | 2 - вероятность при измерении получить значение 00, |b | 2 - вероятность получить значение 01 и т.д.

В общем случае если квантовая система состоит из L кубитов, то у нее имеется 2 L возможных классических состояний, каждое из которых может быть измерено с некоторой вероятностью. Функция состояния такой квантовой системы запишется в виде:

где |n - базисные квантовые состояния (например, состояние |001101, а |c n | 2 - вероятность нахождения в базисном состоянии |n .

Для того чтобы изменить состояние суперпозиции квантовой системы, необходимо реализовать селективное внешнее воздействие на каждый кубит. С математической точки зрения такое преобразование представляется унитарными матрицами размера 2 L x2 L . В результате будет получено новое квантовое состояние суперпозиции.

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

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

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

Квантовый регистр представляет собой совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты квантового регистра должны быть приведены в базисные состояния |0. Эта операция называется подготовкой, или инициализацией. Далее определенные кубиты (не все) подвергаются селективному внешнему воздействию (например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером), которое изменяет значение кубитов, то есть из состояния |0 они переходят в состояние |1. При этом состояние всего квантового регистра перейдет в суперпозицию базисных состояний |n с, то есть состояние квантового регистра в начальный момент времени будет определяться функцией:

Понятно, что данное состояние суперпозиции можно использовать для бинарного (двоичного) представления числа n .

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

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

Схематическая структура квантового компьютера

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

Для того чтобы понять, чем различаются в работе классический и квантовый компьютеры, давайте вспомним, что классический компьютер хранит в памяти L бит, которые за каждый такт работы процессора подвергаются изменению. В квантовом компьютере в памяти (регистр состояния) хранятся значения L кубитов, однако квантовая система находится в состоянии, являющемся суперпозицией всех базовых 2L состояний, и изменение квантового состояния системы, производимое квантовым процессором, касается всех 2L базовых состояний одновременно. Соответственно в квантовом компьютере вычислительная мощность достигается за счет реализации параллельных вычислений, причем теоретически квантовый компьютер может работать в экспоненциальное число раз быстрее, чем классическая схема.

Считается, что для реализации полномасштабного квантового компьютера, превосходящего по производительности любой классический компьютер, на каких бы физических принципах он ни работал, следует обеспечить выполнение следующих основных требований:

• физическая система, представляющая собой полномасштабный квантовый компьютер, должна содержать достаточно большое число L >103 хорошо различимых кубитов для выполнения соответствующих квантовых операций;
• необходимо обеспечить максимальное подавление эффектов разрушения суперпозиции квантовых состояний, обусловленных взаимодействием системы кубитов с окружающей средой, в результате чего может стать невозможным выполнение квантовых алгоритмов. Время разрушения суперпозиции квантовых состояний (время декогерентизации) должно по крайней мере в 104 раз превышать время выполнения основных квантовых операций (время такта). Для этого система кубитов должна быть довольно слабо связана с окружением;
• необходимо обеспечить измерение с достаточно высокой надежностью состояния квантовой системы на выходе. Измерение конечного квантового состояния является одной из основных проблем квантовых вычислений.

Практическое применение квантовых компьютеров

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

На данный момент наибольший квантовый компьютер составлен всего из семи кубитов. Этого достаточно, чтобы реализовать алгоритм Шора и разложить число 15 на простые множители 3 и 5.

Если же говорить о возможных моделях квантовых компьютеров, то их, в принципе, довольно много. Первый квантовый компьютер, который был создан на практике, - это импульсный ядерный магнитно-резонансный (ЯМР) спектрометр высокого разрешения, хотя он, конечно же, как квантовый компьютер не рассматривался. Лишь когда появилась концепция квантового компьютера, ученые поняли, что ЯМР-спектрометр представляет собой вариант квантового компьютера.

В ЯМР-спектрометре спины ядер исследуемой молекулы образуют кубиты. Каждое ядро имеет свою частоту резонанса в данном магнитном поле. При воздействии импульсом на ядро на его резонансной частоте оно начинает эволюционировать, остальные же ядра не испытывают никакого воздействия. Для того чтобы заставить эволюционировать другое ядро, нужно взять иную резонансную частоту и дать импульс на ней. Таким образом, импульсное воздействие на ядра на резонансной частоте представляет собой селективное воздействие на кубиты. При этом в молекуле есть прямая связь между спинами, поэтому она является идеальной заготовкой для квантового компьютера, а сам спектрометр представляет собой квантовый процессор.

Первые эксперименты на ядерных спинах двух атомов водорода в молекулах 2,3-дибромотиофена SCH:(CBr) 2:CH и на трех ядерных спинах - одном в атоме водорода H и двух в изотопах углерода 13 C в молекулах трихлорэтилена CCl 2:CHCl - были поставлены в 1997 году в Оксфорде (Великобритания).

В случае использования ЯМР-спектрометра важно, что для селективного воздействия на ядерные спины молекулы необходимо, чтобы они заметно различались по резонансным частотам. Позднее были осуществлены квантовые операции в ЯМР-спектрометре с числом кубитов 3, 5, 6 и 7.

Главным преимуществом ЯМР-спектрометра является то, что в нем можно использовать огромное количество одинаковых молекул. При этом каждая молекула (точнее, ядра атомов, из которых она состоит) представляет собой квантовую систему. Последовательности радиочастотных импульсов, выполняющие роль определенных квантовых логических вентилей, осуществляют унитарные преобразования состояний соответствующих ядерных спинов одновременно для всех молекул. То есть селективное воздействие на отдельный кубит заменяется одновременным обращением к соответствующим кубитам во всех молекулах большого ансамбля. Компьютер такого рода получил название ансамблевого (bulk-ensemble quantum computer) ЯМР квантового компьютера. Такие компьютеры могут работать при комнатной температуре, а время декогерентизации квантовых состояний ядерных спинов составляет несколько секунд.

В области ЯМР квантовых компьютеров на органических жидкостях к настоящему времени достигнуты наибольшие успехи. Они обусловлены в основном хорошо развитой импульсной техникой ЯМР-спектроскопии, обеспечивающей выполнение различных операций над когерентными суперпозициями состояний ядерных спинов, и возможностью использования для этого стандартных ЯМР-спектрометров, работающих при комнатной температуре.

Основным ограничением ЯМР квантовых компьютеров является сложность инициализации начального состояния в квантовом регистре. Дело в том, что в большом ансамбле молекул исходное состояние кубитов различно, что осложняет приведение системы к начальному состоянию.

Другое ограничение ЯМР квантовых компьютеров связано с тем, что измеряемый на выходе системы сигнал экспоненциально убывает с ростом числа кубитов L . Кроме того, число ядерных кубитов в отдельной молекуле с сильно различающимися резонансными частотами ограничено. Это приводит к тому, что ЯМР квантовые компьютеры не могут иметь больше десяти кубитов. Их следует рассматривать лишь как прототипы будущих квантовых компьютеров, полезные для отработки принципов квантовых вычислений и проверки квантовых алгоритмов.

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

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

Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 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, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

Шифрование, однако, только одно возможное применение квантового компьютера. Шор разработал целый набор математических операций, которые могут быть выполнены исключительно на квантовом компьютере. Некоторые из этих операций используются в его алгоритие факторизации. Далее, Фейнман утверждал, что квантовый компьютер может действовать как моделирующее устройство для квантовой физики, потенциально открывая двери ко многим открытиям в этой области. В настоящее время мощь и возможности квантового компьютера, в основном, предмет теоретических рассуждений; появление первого по-настоящему функционального квантового компьютера, несомненно, принесет много новых и волнующих практических применений.

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

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

Что такое квантовые вычисления?

Начнём с того, что квантовые вычисления - это новая очень модная тема, которая там у них развивается семимильными шагами по нескольким направлениям (а у нас, как всякая фундаментальная наука пребывает в запустении и отдана на откуп нескольким учёным, сидящим в своих башнях из слоновой кости). И вот уже говорят о появлении первых квантовых компьютеров (D-Wave, но это не универсальный квантовый компьютер), ежегодно публикуются новые квантовые алгоритмы, создаются языки квантового программирования, сумрачный гений Международных Деловых Машин в тайных подземных лабораториях производит квантовые вычисления на десятках кубитов.

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

Как такое может быть? Всё просто. Квантовая вычислительная модель основана на нескольких довольно простых правилах преобразования входной информации, которые обеспечивают массовую параллелизацию вычислительных процессов. Другими словами, можно одновременно вычислить значение функции для всех её аргументов (и это будет единственный вызов функции). Это достигается специальной подготовкой входных параметров и специальным же видом функции.

Светитель Проц учит, что всё это суть синтаксическая манипуляция с математическими символами, за которой, по сути, нет никакого смысла. Есть формальная система с правилами преобразования входа в выход, и эта система позволяет при помощи последовательного применения этих правил получать из входных данных выходные. Всё это в конечном итоге сводится к перемножению матрицы и вектора. Да, да, да. Вся модель квантовых вычислений основана на одной простой операции - умножении матрицы на вектор, в результате чего на выходе получается другой вектор.

Светитель Халикаарн в противоположность учит, что существует объективный физический процесс, который выполняет указанную операцию, и только лишь существование которого и обуславливает возможность массовой параллелизации вычислений функции. То, что мы воспринимаем это как умножение матрицы на вектор, является всего лишь способом нашего далеко не совершенного отражения объективной реальности в нашем разуме.

Мы в нашей научной лаборатории имени светителей Проца и Халикаарна объединяем эти два подхода и говорим, что модель квантовых вычислений есть математическая абстракция, которая отражает объективный процесс. В частности, числа в векторах и матрицах являются комплексными, хотя это совершенно не увеличивает вычислительную мощность модели (она бы была такой же мощной и с действительными числами), однако выбраны именно комплексные числа потому, что найден объективный физический процесс, который осуществляет такие преобразования, как описывает модель, и в котором используются именно комплексные числа. Этот процесс называется унитарной эволюцией квантовой системы.

В основе квантовой вычислительной модели лежит понятие кубита. Это практически то же самое, что и бит в классической теории информации, однако кубит может одновременно принимать несколько значений. Говорят, что кубит находится в суперпозиции своих состояний, то есть значение кубита есть линейная комбинация его базовых состояний, и коэффициенты при базовых состояниях как раз являются комплексными числами. Базовыми же состояниями являются известные по классической теории информации значения 0 и 1 (в квантовых вычислениях их принято обозначать |0> и |1>).

Пока не очень-то и понятно, в чём фишка. А фишка вот в чём. Суперпозиция одного кубита записывается как A|0> + B|1>, где A и B - некоторые комплексные числа, единственное ограничение на которые заключается в том, что сумма квадратов их модулей всегда должна равняться 1. А если рассмотреть два кубита? Два бита могут получать 4 возможных значения: 00, 01, 10 и 11. Резонно предположить, что два кубита представляют собой суперпозицию четырёх базовых значений: A|00> + B|01> + C|10> + D|11>. И так оно и есть. Три кубита представляют собой суперпозицию восьми базовых значений. Другими словами, квантовый регистр из N кубитов одновременно хранит в себе 2N комплексных чисел. Ну а с математической точки зрения это есть 2N -мерный вектор в комплекснозначном пространстве. Именно этим достигается экспоненциальная мощность модели квантовых вычислений.

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

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

Что происходит дальше? Вот у нас есть входной вектор, который представляет собой суперпозицию различных вариантов значений входного параметра функции. Есть функция в виде эрмитовой матрицы. Квантовый алгоритм представляет собой умножение матрицы на вектор. В результате получается новый вектор. Что же это за ерунда-то такая?

Дело в том, что в модели квантовых вычислений есть ещё одна операция, которая называется измерением . Мы можем измерить вектор и получить из него конкретное значение кубита. То есть суперпозиция схлопывается в конкретное значение. И вероятность получения того или иного значения равна квадрату модуля комплекснозначного коэффициента. И теперь понятно, почему сумма квадратов должна равняться 1, поскольку при измерении всегда будет получено какое-то конкретное значение, а потому сумма вероятностей их получения равна единице.

То есть что получается? Имея N кубитов можно одновременно обработать 2N комплексных чисел. И в выходном векторе будут результаты обработки всех этих чисел одновременно. В этом мощь модели квантовых вычислений. Но получить можно только одно значение, и оно может быть каждый раз различное в зависимости от распределения вероятностей. В этом ограничение модели квантовых вычислений.

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

В подавляющем большинстве источников по квантовым вычислениям читатель найдёт описания нескольких алгоритмов, которые, собственно, обычно используются для демонстрации мощи вычислительной модели. Здесь мы тоже кратко и поверхностно рассмотрим такие алгоритмы (два из них, которые демонстрируют различные базовые принципы квантовых вычислений). Ну а для детального ознакомления с ними опять адресую к своей новой книге.

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

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

Итак, пусть есть некоторая функция, которая получает на вход один бит и возвращает на выходе тоже один бит. Честно говоря, таких функций может быть всего 4. Две из них являются константными, то есть одна всегда возвращает 0, а другая всегда возвращает 1. Две другие являются сбалансированными, то есть возвращают 0 и 1 в равных количествах случаев. Вопрос: как за один вызов этой функции определить, константная она или сбалансированная?

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

Как уже было написано, мы подготовим равновероятностную суперпозицию всех возможных значений входного параметра функции. Поскольку на входе у нас один кубит, то его равновероятностная суперпозиция готовится при помощи одного применения гейта Адамара (это такая специальная функция, которая и готовит равновероятностные суперпозиции:). Далее снова применяется гейт Адамара, который работает таким образом, что если ему на вход подаётся равновероятностная суперпозиция, то он преобразует её назад в состояния |0> или |1> в зависимости от того, в какой фазе находится равновероятностная суперпозиция. После этого производится измерение кубита, и если он равен |0>, то рассматриваемая функция константна, а если |1>, то сбалансирована.

Что получается? Как уже было сказано, при измерении мы не можем получить все значения функции. Но мы можем сделать определённые выводы о её свойствах. Задача Дойча как раз и спрашивает о свойстве функции. И это свойство очень простое. Ведь как выходит? Если функция константна, то сложение по модулю 2 всех её выходных значений всегда даёт 0. Если же функция сбалансирована, то сложение по модулю 2 всех её выходных значений всегда даёт 1. Именно этот результат мы и получили в результате выполнения алгоритма Дойча. Мы не знаем, какое именно значение вернула функция на равновероятностной суперпозиции всех входных значений. Мы знаем только, что это тоже суперпозиция результатов, и если теперь эту суперпозицию преобразовать специальным образом, то будут сделаны однозначные выводы о свойстве функции.

Вот как-то так.

Алгоритм Гровера

Другой алгоритм, который показывает квадратичный выигрыш по сравнению с классической вычислительной моделью, решает более приближённую к реальности задачу. Это алгоритм Гровера, или, как называет его сам Лов Гровер, алгоритм поиска иголки в стоге сена. Этот алгоритм основан на другом принципе, лежащем в основе квантовых вычислений, а именно амплификации .

Уже упоминалась некая фаза, которая может быть у квантового состояния в составе кубита. Как таковой фазы нет в классической модели, это что-то новенькое именно в рамках квантовых вычислений. Фазу можно понимать как знак у коэффициента при квантовом состоянии в суперпозиции. Алгоритм Гровера основан на том, что специально подготовленная функция меняет фазу у состояния |1>.

Алгоритм Гровера решает обратную задачу. Если есть неупорядоченый набор данных, в котором надо найти один элемент, удовлетворяющий критерию поиска, алгоритм Гровера поможет это сделать эффективнее, чем простой перебор. Если простой перебор решает задачу за O(N) обращений к функции, то алгоритм Гровера эффективно находит заданный элемент за O(√N ) обращений к функции.

Алгоритм Гровера состоит из следующих шагов:

1. Инициализация начального состояния . Опять готовится равновероятностная суперпозиция всех входных кубитов.

2. Применение итерации Гровера . Данная итерация состоит из последовательного применения функции поиска (она определяет критерий поиска элемента) и специального гейта диффузии. Гейт диффузии меняет коэффициенты при квантовых состояниях, вращая их вокруг среднего. Тем самым производится амплификация, то есть увеличение амплитуды искомого значения. Фишка в том, что осуществить применение итерации необходимо определённое количество раз (√2n ), иначе алгоритм вернёт не те результаты.

3. Измерение . После измерения входного квантового регистра с большой вероятностью будет получен искомый результат. Если необходимо увеличить достоверность ответа, то алгоритм прогоняется несколько раз и вычисляется совокупная вероятность правильного ответа.

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

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

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

Классические вычисления: AND, OR, NOT

Чтобы разобраться с квантовыми вычислениями, стоит для начала освежить знания о классических. Здесь единицей обрабатываемой информации является бит. Каждый бит может находиться только в одном из двух возможных состояний – 0 или 1. Регистр из N бит может содержать одну из 2 N возможных комбинаций состояний и представляется в виде их последовательности.

Для обработки и преобразования информации используются побитовые операции, пришедшие из булевой алгебры. Основные операции - это однобитная NOT и двубитные AND и OR. Битовые операции описываются через таблицы истинности. В них приводится соответствие входных аргументов получаемому значению.

Алгоритм классических вычислений - это набор последовательных битовых операций. Удобней всего воспроизводить его графически, в виде схемы из функциональных элементов (СФЭ), где каждая операция имеет свое обозначение. Вот пример СФЭ для проверки двух бит на эквивалентность.

Квантовые вычисления. Физическая основа

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

Вероятностный характер измерений, присущий квантовым вычислениям, лежит в основе многих алгоритмов – например, поиск в неструктурированной БД. Алгоритмы данного типа пошагово увеличивают амплитуду правильного результата, позволяя получить его на выходе с максимальной вероятностью.

Кубиты

В квантовых вычислениях физические свойства квантовых объектов реализованы в так называемых кубитах (q-bit). Классический бит может находиться только в одном состоянии – 0 или 1. Кубит до измерения может находиться одновременно в обоих состояниях, поэтому его принято обозначать выражением a|0⟩ + b|1⟩, где A и B - комплексные числа, удовлетворяющие условию |A| 2 +|B| 2 =1. Измерение кубита мгновенно «схлопывает» его состояние в одно из базисных – 0 или 1. При этом «облако» коллапсирует в точку, первоначальное состояние разрушается, и вся информация о нем безвозвратно теряется.

Одно из применений этого свойства – кот Шредингера генератор истинно случайных чисел. Кубит вводится в такое состояние, при котором результатом измерения могут быть 1 или 0 с одинаковой вероятностью. Это состояние описывается так:

Квантовые и классические вычисления. Первый раунд

Начнем с основ. Имеется набор исходных данных для вычислений, представленный в двоичном формате векторами длиной N.

В классических вычислениях в память компьютера загружается только один из 2 n вариантов данных и для этого варианта вычисляется значение функции. В результате одновременно обрабатывается только один из 2 n возможных наборов данных.

В памяти квантового компьютера одновременно представлены все 2 n комбинации исходных данных. Преобразования применяются ко всем этим комбинациям сразу. В результате за одну операцию мы вычисляем функцию для всех 2 n возможных вариантов набора данных (измерение в итоге все равно даст только одно решение, но об этом позже).

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

Рассмотрим реальную задачу. Нужно определить, эквивалентны ли два бита.

Если при классических вычислениях на выходе получаем единицу, значит эквивалентны, иначе нет:

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

В примере мы сравниваем значения первого и второго кубитов. Результат будет в нулевом кубите - кубите-флаге. Данный алгоритм применим только к базовым состояниям – 0 или 1. Вот порядок квантовых преобразований.

1. Воздействуем на кубит-флаг гейтом «Не», выставляя его в 1.
2. Два раза применяем двухкубитный гейт «Контролируемое Не». Этот гейт меняет значение кубита-флага на противоположное только в случае, если второй кубит, участвующий в преобразовании, находится в состоянии 1.
3. Измеряем нулевой кубит. Если в результате получили 1, значит и первый, и второй кубиты либо оба в состоянии 1 (кубит-флаг два раза поменял свое значение), либо в состоянии 0 (кубит-флаг так и остался в состоянии 1). Иначе кубиты находятся в разных состояниях.

Следующий уровень. Квантовые однокубитные гейты Паули

Попробуем сравнить классические и квантовые вычисления в более серьезных задачах. Для этого нам потребуется еще немного теоретических знаний.

В квантовых вычислениях обрабатываемая информация закодирована в квантовых битах – так называемых кубитах. В простейшем случае кубит, как и классический бит, может находиться в одном из двух базисных состояний: |0⟩ (краткое обозначение для вектора 1|0⟩ + 0|1⟩) и |1⟩ (для вектора 0|0⟩ + 1|1⟩). Квантовый регистр представляет собой тензорное произведение векторов кубит. В простейшем случае, когда каждый кубит находится в одном из базисных состояний, квантовый регистр эквивалентен классическому. Регистр из двух кубит, находящихся в состоянии |0>, можно расписать в таком виде:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

Для обработки и преобразования информации в квантовых алгоритмах используются так называемые квантовые вентили (гейты). Они представляются в виде матрицы. Для получения результата применения гейта, нам необходимо умножить вектор, характеризующий кубит, на матрицу гейта. Первая координата вектора – множитель перед |0⟩, вторая координата – множитель перед |1⟩. Матрицы основных однокубитных гейтов выглядит так:

А вот пример применения гейта Not:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Множители перед базисными состояниями называются амплитудами и являются комплексными числами. Модуль комплексного числа равен корню из суммы квадратов действительной и мнимой частей. Квадрат модуля амплитуды, стоящей перед базисным состоянием, равен вероятности получить это базисное состояние при измерении кубита, поэтому сумма квадратов модулей амплитуд всегда равна 1. Мы могли бы использовать произвольные матрицы для преобразований над кубитами, но из-за того, что норма (длина) вектора всегда должна быть равна 1 (сумма вероятностей всех исходов всегда равна 1), наше преобразование должно сохранять норму вектора. Значит преобразование должно быть унитарным и соответствующая ему матрица унитарной. Напомним, что унитарное преобразование обратимо и UU † =I.

Для более наглядной работы с кубитами их изображают векторами на сфере Блоха. В такой интерпретации однокубитные гейты представляют собой вращение вектора кубита вокруг одной из осей. Например гейт Not (X) поворачивает вектор кубита на Pi относительно оси X. Таким образом, состояние |0>, представляемое вектором, направленным строго вверх, переходит в состояние |1>, направленное строго вниз. Состояние кубита на сфере Блоха определяется формулой cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Квантовые двухкубитные гейты

Для построения алгоритмов нам недостаточно только однокубитных гейтов. Необходимы гейты, которые осуществляют преобразования в зависимости от некоторых условий. Основным таким инструментом является двухкубитный гейт CNOT. Этот гейт применяется к двум кубитам и инвертирует второй кубит только в том случае, если первый кубит находится в состоянии |1⟩. Матрица гейта CNOT выглядит так:

А вот пример применения:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Применение гейта CNOT эквивалентно выполнению классической операции XOR с записью результата во второй кубит. Действительно, если посмотреть на таблицу истинности оператора XOR и CNOT, то увидим соответствие:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

У гейта CNOT есть интересное свойство – после его применения кубиты запутываются или распутываются, в зависимости от исходного состояния. Это будет показано в следующей статье, в разделе про квантовый параллелизм.

Построение алгоритма - классическая и квантовая реализация

Имея полный арсенал квантовых гейтов, мы можем приступать к разработке квантовых алгоритмов. В графическом представлении кубиты представляются прямыми линиями – «струнами», на которые накладываются гейты. Однокубитные гейты Паули обозначаются обычными квадратами, внутри которых изображается ось вращения. Гейт CNOT выглядит немного сложнее:

Пример применения гейта CNOT:

Одним из важнейших действий в алгоритме является измерение полученного результата. Измерение обычно обозначается дуговой шкалой со стрелкой и обозначением, относительно какой оси идет измерение.

Итак, попробуем построить классический и квантовый алгоритм, который прибавляет 3 к аргументу.

Суммирование обычных чисел столбиком подразумевает совершение двух действий над каждым разрядом – сумму самих цифр разряда и сумму результата с переносом с предыдущей операции, если таковой перенос был.

В двоичном представлении чисел операция суммирования будет состоять из тех же действий. Приведем код на языке python:

Arg = #задаем аргумент result = #инициализируем результат carry1 = arg & 0x1 #складываем с 0b11, так что перенос от младшего бита появится в том случае, если у агрумента младший бит = 1 result = arg ^ 0x1 #складываем младшие биты carry2 = carry1 | arg #складываем с 0b11, так что перенос от старшего бита появится в том случае, если у агрумента старший бит = 1 или был перенос с младшего бита result = arg ^ 0x1 #складываем старшие биты result ^= carry1 #применяем перенос с младшего бита result ^= carry2 #применяем перенос со старшего бита print(result)
Теперь попробуем разработать аналогичную программу для квантового вычислителя:

В этой схеме первые два кубита – это аргумент, следующие два – переносы, оставшиеся 3 – результат. Вот как работает алгоритм.

1. Первым шагом до барьера мы выставляем аргумент в то же состояние, как и в классическом случае – 0b11.
2. С помощью оператора CNOT вычисляем значение первого переноса – результат операции arg & 1 равен единице только тогда, когда arg равен 1, в этом случае мы инвертируем второй кубит.
3. Следующие 2 гейта реализуют сложение младших бит – мы переводим кубит 4 в состояние |1⟩ и результат XOR записываем в него же.
4. Большим прямоугольником обозначен гейт CCNOT – расширение гейта CNOT. В этом гейте два управляющих кубита и третий инвертируется только в том случае, если первые два находятся в состоянии |1. Комбинация из 2 гейт CNOT и одного CCNOT дает нам результат классической операции carry2 = carry1 | arg. Первые 2 гейта выставляют перенос в единицу в том случае, если один из них равен 1, а гейт CCNOT обрабатывает случай, когда они оба равны единице.
5. Складываем старшие кубиты и кубиты переноса.

Промежуточные выводы

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

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

По материалам

Историческая справка

Квантовые вычисления немыслимы без контроля над квантовым состоянием отдельных элементарных частиц. Двум физикам - французу Сержу Лрошу и американцу Дэвиду Вайнленду - это удалось. Лрош ловил в резонатор одиночные фотоны и надолго «отцеплял» их от внешнего мира. Вайнленд собирал в ловушку одиночные ионы с опреденными квантовыми состояниями и изолировал их от внешнего воздействия. Арош использовал атомы, чтобы наблюдать за состоянием фотона. Вайнленд применял фотоны, чтобы изменять состояния ионов. Им удалось продвинуться в изучении взаимоотношения квантового и классического миров. В 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" базовых состояний одновременно. Теоретически новая схема может работать в экспоненциальное число раз быстрее классической. Практически квантовый алгоритм поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов.