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

В представлении Шредингера изменение кубита во времени под действием унитарных операторов удобно представить графически. Данный подход широко используется в области квантовых вычислений. Так называемые квантовые цепи служат аналогом графического представления электрических цепей. Они также строятся из набора вентилей или гейтов по аналогии с цифровыми вентилями «И», «ИЛИ», «НЕ», триггерами, регистрами, сумматорами и так далее.

Пусть у нас имеется кубит в базисном состоянии «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 частях.

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

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

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

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

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

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

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

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

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

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

Классические вычисления: 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 наносекунды. Так что алгоритмы для квантового вычислителя должны не копировать классические, а по максимуму использовать уникальные свойства квантовой механики. В следующей статье мы разберем одно из основных таких свойств - квантовый параллелизм - и поговорим о квантовой оптимизации в целом. Затем определим наиболее подходящие сферы для квантовых вычислений и расскажем об их применении.

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

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

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

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

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

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

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

В ближайшие несколько лет ожидается значительное улучшение квантового как аппаратного, так и программного обеспечения. По мере того, как расчеты становятся все более точными, все больше отраслей могут воспользоваться преимуществами приложений квантовых компьютеров, включая и квантовую химию. Gartner прогнозирует, что уже через четыре года у 20% корпораций будет бюджет на квантовые вычисления. Через десять лет они станут неотъемлемым компонентом технологий.