квантовый кубит что такое
Как устроен и зачем нужен квантовый компьютер
Это прорыв в технологиях или очередной биткоин?
Сейчас много говорят о новых технологиях вычисления — в частности, то и дело звучат слова «квантовые вычисления», «квантовый интернет» и даже «квантовая криптография». Посмотрим, что это такое и нужно ли оно нам. Начнём с квантового компьютера.
Биты и кубиты
В обычном компьютере все вычисления основаны на понятии «бит». Это такой элемент, который может принимать значения 0 или 1. Физически это реализовано так:
Транзистор в компьютере может принимать значение 1 или 0, то есть «включён» или «выключен». С точки зрения компьютерной логики, этот транзистор называется битом. Это минимальная единица информации в компьютере. Физически бит может быть в процессоре, на чипе памяти, на магнитном диске, но суть одна: это какое-то физическое пространство, которое определённо либо включено, либо выключено.
Ключевое слово здесь — «определённо». Программист и инженер может точно узнать, в каком состоянии находится тот или иной бит. Заряд в нём либо есть, либо нет, никаких промежуточных состояний там не существует.
В квантовом компьютере вместо битов — кубиты. Кубиты — это квантовые частицы, у которых есть интересная особенность: кроме стандартных 0 и 1 кубит может находиться между нулём и единицей — это называют суперпозицией. Нагляднее это видно на рисунке:
Кубит может принимать все значения, которые видны на цветной сфере
Все решения уже известны
Ещё одна особенность кубитов — зависимость значения от измерения. Это значит, что программист не узнает значение кубита до тех пор, пока его не измерит, а сам факт измерения тоже влияет на значение кубита. Звучит странно, но это особенность квантовых частиц.
Именно благодаря тому, что кубит находится во всех состояниях одновременно до тех пор, пока его не измерили, компьютер мгновенно перебирает все возможные варианты решения, потому что кубиты связаны между собой. Получается, что решение становится известно сразу, как только введены все данные. Суперпозиция и даёт ту параллельность в вычислениях, которая ускоряет работу алгоритмов в разы.
Вся сложность в том, что результат работы квантового компьютера — это правильный ответ с какой-то долей вероятности. И нужно строить алгоритмы таким образом, чтобы максимально приблизить вероятность правильного ответа к единице.
Рабочая температура внутри таких компьютеров — минус 273 градуса по Цельсию
Как делают кубиты и в чём сложность
Максимально упрощённо: чтобы получить рабочий кубит, нужно взять один атом, максимально его зафиксировать, оградить от посторонних излучений и связать с другим атомом специальной квантовой связью.
Чем больше таких кубитов связано между собой, тем менее стабильно они работают. Для достижения «квантового превосходства» над обычным компьютером нужно не менее 49 кубитов — а это очень неустойчивая система.
Основная сложность — декогеренция. Это когда много кубитов зависят друг от друга и на них может повлиять всё что угодно: космические лучи, радиация, колебания температуры и все остальные явления окружающего мира.
Такой «фазовый шум» — катастрофа для квантового компьютера, потому что он уничтожает суперпозицию и заставляет кубиты принимать ограниченные значения. Квантовый компьютер превращается в обычный — и очень медленный.
С декогеренцией можно бороться разными способами. Например, компания D-Wave, которая производит квантовые компьютеры, охлаждает атомы почти до абсолютного нуля, чтобы отсечь все внешние процессы. Поэтому они такие большие — почти всё место занимает защита для квантового процессора.
Квантовый процессор на девяти кубитах от Google
Зачем нужны квантовые компьютеры
Одно из самых важных применений квантового компьютера сейчас — разложение на простые числа. Дело в том, что вся современная криптография основана на том, что никто не сможет быстро разложить число из 30–40 знаков (или больше) на простые множители. На обычном компьютере на это уйдёт миллиарды лет. Квантовый компьютер сможет это сделать примерно за 18 секунд.
Это означает, что тайн больше не будет, потому что любые алгоритмы шифрования можно будет сразу взломать и получить доступ к чему угодно. Это касается всего — от банковских переводов до сообщений в мессенджере. Возможно, наступит интересный момент, когда обычное шифрование перестанет работать, а квантовое шифрование ещё не изобретут.
Ещё квантовые компьютеры отлично подходят для моделирования сложных ситуаций, например, расчёта физических свойств новых элементов на молекулярном уровне. Это, возможно, позволит быстрее находить новые лекарства или решать сложные ресурсоёмкие задачи.
Все что вы хотели знать о кубитах, но боялись спросить
Квантовые вычисления — непростая тема. С просьбой объяснить, что это такое, мы обратились к ученому, который создает квантовые процессоры. Завлабораторией сверхпроводящих метаматериалов МИСиСа, руководитель группы «Сверхпроводящие квантовые цепи» в Российском квантовом центре, профессор Алексей Устинов помог разобраться в том, какова материальная основа единицы квантовой информации — кубита — и как действуют процессоры на базе сверхпроводников.
СЛОВАРЬ
Кубит — квантовый разряд, наименьший элемент для хранения информации в квантовом компьютере. Как и бит, кубит допускает два состояния — 0 и 1, но при этом может находиться в суперпозиции — может принимать одновременно оба значения.
Фотон — фундаментальная частица, квант электромагнитного поля. В виде фотонов испускается и поглощается электромагнитное излучение. Фотон имеет свойства как частицы, так и волны. У него нет ни электрического заряда, ни массы.
Физически кубит на базе сверхпроводников представляет собой пластинку из кремния, на которую нанесены две тонкие, меньше микрона, пленки алюминия. Между ними — диэлектрик из окиси алюминия. В этом месте находится джозефсоновский переход, или контакт, в котором происходит эффект Джозефсона: протекание сверхпроводящего тока через слой диэлектрика, разделяющий два сверхпроводника. Для удобства пластинка из кремния закрепляется на медной подложке.
Почему алюминий
Он становится сверхпроводником при температуре 1,2 К. В сверхпроводнике электрический ток течет без сопротивления — оно равно нулю.
Сверхпроводник по своим физическим свойствам становится системой, минимальная энергия которой хорошо определена, а следующее возможное значение энергии кольца с джозефсоновским переходом отделяется небольшой щелью. Такая система фактически имеет два уровня энергии. Это и есть материальная основа кубита — квантовая система с двумя уровнями энергии, которая нужна для того, чтобы делать вычисления.
Сколько живет кубит
Чтобы проводить вычисления, необходимо управлять переходами с минимального уровня энергии на следующий и удерживать систему на этом уровне как можно дольше.
В отличие от обычных компьютеров, для сверхпроводниковых кубитов потеря кванта энергии — это потеря информации, то есть конец жизни кубита как единицы информации. Квантовая система теряет энергию легко: она улетучивается в пространство в виде фотонов или переходит в тепло — сверхпроводник нагревается, а энергия теряется.
Удержать кубит в возбужденном состоянии — большая технологическая и пока до конца не решенная проблема. В первых экспериментах в Японии в 1999 году кубит жил (удерживал энергию на верхнем уровне) лишь наносекунду. Благодаря исследованиям физиков всего мира за последние годы произошел экспоненциальный рост срока жизни кубитов. Сейчас они живут несколько десятков, иногда даже сотен микросекунд. Рост стал возможен благодаря тому, что ученые тщательно изолируют кубиты от окружения и воздействия неблагоприятных факторов.
Минимальный набор для квантового вычисления — пара кубитов, которая управляется двухкубитными вентилями. Вентили — логические операции по обработке информации («и», «или», «нет» и т. д.), они есть и в обычных компьютерах. Благодаря объединению фотон (читай — энергия и информация) не теряется, а передается от одного кубита к другому.
Переход с минимально возможного уровня энергии на следующий инициируется за счет воздействия на кубит коротким импульсом микроволн с частотой в несколько гигагерцев, что соответствует длине волны в несколько сантиметров. У таких волн энергия фотонов низкая (энергия излучения, напомним, обратно пропорциональна длине волны). Но температурные флуктуации (отклонение от среднего значения случайной величины) могут легко разрушить квантовую систему. Чтобы это не произошло, температура системы должна быть еще ниже, чем это необходимо для того, чтобы сделать алюминий сверхпроводником. Вместо 1 К требуется порядка 20 мК.
Создают и поддерживают такую температуру специальные холодильники, работающие на смеси изотопов гелия. В нашей стране такие есть во ВНИИА, МГТУ, МФТИ, МИСиСе и Российском квантовом центре.
Как избавиться от ошибок
Чтобы кубиты могли взаимодействовать, необходимо объединить их в цепи, по аналогии с транзисторами. Когда кубиты соединены в схему, работающую по алгоритму, в ней можно запустить сложное вычисление.
Создание цепей — задача не только математическая (надо написать алгоритм), но и аппаратная. Нужна электроника, которая может управлять взаимодействием множества кубитов. Для иллюстрации физики приводят такой пример: представьте, что у вас два капризных ребенка. Сложно ими управлять? Сложно, но возможно. А теперь представьте, что у вас их 50. Физикам, как и родителям, нужны все более сложные средства управления квантовыми «капризными детьми».
Помимо самого выполнения вычислений нужно, чтобы итог этих вычислений был корректным. В России безошибочность выполнения однокубитных операций (контролируемых изменений состояний кубитов) — 99,9 %, двухкубитных — 89 %, а точность считывания — 85–90 %. У Google, в лаборатории Джона Мартиниса в Университете Санта-Барбары, у однокубитных операций показатель тот же, у двухкубитных — 99,5 %. По точности считывания лидер с показателем 99 % — лаборатория IBM в Цюрихе.
Для обычных компьютеров задача избавления от ошибок уже решена, для квантовых решение только предстоит найти. Один из вариантов — создать логический кубит. «С помощью некоторых ухищрений (предлагаю не вдаваться в подробности) можно соединить несколько физических кубитов. Объединенные в систему физические кубиты теоретически могут жить бесконечно долго, потому что физические кубиты «умирают» (теряют информацию) в разное время. Здесь используется принцип двух наблюдателей: когда два наблюдателя смотрят на кубит, они одновременно заметят, что ошибка возникла. Как только возникает совпадение этих двух событий, мы говорим: да, произошла ошибка», — поясняет Алексей Устинов. Правда, пока ни одна из команд, работающих над квантовыми процессорами на сверхпроводниках, к решению этой задачи на практике не приблизилась.
Квантовые технологии. Модуль 4
Узнайте, как выглядит практическая реализация квантовых компьютеров
В этом модуле вы узнаете:
• как и из чего создают составные элементы квантовых компьютеров — кубиты;
• какие преимущества и недостатки есть у разных типов квантовых систем;
• как устроены и как создают самый распространенный тип кубитов — сверхпроводящие кубиты на базе контактов Джозефсона;
• о конкретных попытках создания квантовых вычислительных устройств;
• о путях преодоления ошибок в квантовых устройствах.
Элементы квантовых компьютеров — кубиты — могут представлять собой самые разные объекты: холодные атомы, фотоны, дефекты в кристаллической решетке, но самым популярным и перспективным типом кубита сегодня считаются сверхпроводящие кубиты на базе контактов Джозефсона. Именно на базе кубитов такого типа сегодня чаще всего разрабатывают квантовые вычислительные устройства. Их использует для своих симуляторов компания D-Wave, на них основаны процессоры IBM и Intel.
Однако пока существующие квантовые вычислители — либо симуляторы, способные решать только одну задачу, либо экспериментальные компьютеры с небольшим количеством кубитов. Ни те, ни другие еще не способны показать результаты, однозначно свидетельствующие о том, что удалось достичь квантового превосходства, — рубежа, где квантовые компьютеры покажут, что им под силу задачи, которые либо вовсе недоступны для обычных компьютеров, либо требуют значительно больших ресурсов. Главное препятствие — декогеренция, потеря кубитами квантового состояния, и неизбежные вследствие этого ошибки.
Типы кубитов
Оглавление
Модуль 4. Практическая реализация квантовых компьютеров
Кубиты — квантовые биты, из которых строится квантовый компьютер, — можно создавать на базе очень разных физических объектов. Главное, чтобы система могла находиться в состоянии суперпозиции.
Это могут быть ультрахолодные атомы, сверхпроводящие квантовые цепи, фотоны и другие квантовые системы. У каждой из этих систем есть свои преимущества и недостатки.
На этой видеозаписи эксперты Сколтеха рассказывают, из чего можно создать квантовый симулятор:
Нейтральные атомы
В качестве кубита можно использовать атомы, в которых данные «кодируются» в состояниях электронов. Как было рассказано в предыдущих модулях, электроны в атомах находятся в дискретном наборе энергетических состояний и могут переходить с одного уровня на другой, поглощая или испуская фотон определенной энергии.
В состояниях атомов можно кодировать информацию — например, невозбужденное состояние атома можно считать «нулем» (обозначается как |0>), а «единицей» — возбужденное состояние (обозначается как |1>). Как любой другой квантовый объект, атом может находиться в суперпозиции этих двух состояний, а значит, может работать как кубит.
Для кубитов удобно использовать атомы с неспаренным электроном на внешней орбите, где возможны сверхтонкие (hyperfine) энергетические переходы (те же самые, что используются в атомных часах). Наиболее удобны здесь атомы цезия, лития или рубидия.
Однако создать массив таких атомов-кубитов, привести их все в нужное состояние и удержать в нем — непростая технологическая задача.
Прежде всего необходимо избавиться от лишнего тепла, поскольку тепловой шум не позволит контролировать состояния атомов. Для того чтобы довести кубиты до температуры, близкой к абсолютному нулю, используется лазерное охлаждение, то есть облучение лазером определенной длины волны, заставляющим атомы поглощать и испускать фотоны, что влияет на их момент и, следовательно, на температуру.
Вторая проблема — удержать атомы на месте. Ученые подвешивают их в оптических ловушках, представляющих собой серии скрещивающихся лазерных лучей, на пересечении которых образуются стоячие электромагнитные волны.
Во впадинах этих волн и «висят» атомы. Их квантовым состоянием управляют с помощью еще одного лазера.
Атомы в оптической решетке
При этом атомы оказываются в состоянии ультрахолодного ферми-газа, если они являются фермионами, то есть суммарный спин электронов и нуклонов в них оказывается дробным.
Если атомы являются бозонами (с целым спином), как, например, атомы цезия, то они переходят в состояние бозе-эйнштейновского конденсата (специфическое квантовое состояние вещества, в котором все множество составляющих его частиц начинает вести себя как единый квантовый объект, поскольку все они обладают одинаковыми — минимальными — параметрами).
Странное поведение конденсата можно наблюдать даже макроскопически — оно проявляет себя, например, в сверхтекучести жидкого гелия, в сверхпроводимости.
Поэтому газ ультрахолодных атомов используют в качестве квантового симулятора для решения задач моделирования и изучения сверхпроводимости, а также других сильно взаимодействующих систем.
Примером квантового симулятора на базе холодных атомов может служить созданное группой под руководством профессора Гарварда Михаила Лукина 51-кубитное устройство. С его помощью ученые моделировали хорошо известную квантовую систему — модель Изинга, обычно используемую для описания магнитных свойств системы.
Схема квантового симулятора Лукина
Кубиты на NV-центрах
Разновидностью «атомных» кубитов можно считать так называемые NV-центры (или «центры окраски») в алмазах.
В некоторых случаях в регулярной кристаллической решетке алмазов могут возникать дефекты — например, один из атомов углерода может быть замещен атомом азота. В этом случае рядом с азотом в кристаллической решетке возникает «пустое место», вакансия.
Такого типа дефекты и называют NV-центрами. Именно они придают некоторым кристаллам алмазов желтоватый оттенок.
Вакансия заполняется электроном, чьим спином можно управлять с помощью магнитного поля. И как любой другой квантовый объект, электрон в NV-центре может находиться в суперпозиции двух спиновых состояний, а значит, может играть роль кубита.
Главное преимущество «алмазных» кубитов — хорошая устойчивость, электроны в них могут удерживать нужное состояние несколько секунд, что очень много по сравнению с другими типами кубитов. Кроме того, они могут успешно работать даже при комнатной температуре, то есть не требуют, как другие кубиты, громоздкого криогенного оборудования.
Вместе с тем, пока больших установок на базе NV-центров не создано, речь идет об отдельных логических элементах.
Наноалмазы с центрами окраски чувствительны к давлению и температуре и сегодня играют большую роль в создании квантовых сенсоров, поскольку они очень компактны и могут мерить температуру в единичной клетке.
Похожим образом работают одиночные атомы фосфора в кремнии, которыми управляют с помощью инфракрасного лазера, — кремний прозрачен в инфракрасном диапазоне.
Хотя спиновые кубиты на базе холодных атомов, NV-центров и атомов фосфора в кремнии достаточно удобны (они вполне устойчивы к декогеренции, могут «выживать» иногда несколько часов), создание из них больших массивов кубитов может порождать сложности.
Дело в том, что для работы таких массивов необходимо «организовать» взаимодействие между электронами, например для формирования пространственной суперпозиции. Но для формирования этой суперпозиции необходимы расстояния менее 30 нанометров, что слишком мало даже для самых современных нанотехнологических методов.
Выходом может быть создание кубитов на базе молекул. В частности, физики сегодня экспериментируют даже с кубитами на базе органических молекул — пептидов.
Сверхпроводящие квантовые цепи
Хотя у кубитов на базе единичных атомов есть ряд преимуществ — в частности, некоторые из них обладают подавленной декогерентностью, или достаточно большой устойчивостью к шумам, — наиболее широко применяются в качестве кубитов системы на базе так называемых искусственных атомов. Главным образом это сверхпроводящие квантовые системы.
Такие системы, как и кубиты других типов, могут находиться в состоянии суперпозиции, однако имеют значительно бóльшие размеры, а для их изготовления могут использоваться стандартные для современной микроэлектроники технологии литографии и напыления.
Ключевым элементом таких сверхпроводниковых кубитов является джозефсоновский контакт размером от нескольких десятков до нескольких сотен нанометров. Он представляет собой два слоя проводника (сверхпроводящего металла), разделенные тонким слоем диэлектрика, чаще всего оксида металла.
Прежде считалось, что сверхпроводящий ток не может преодолевать этот слой, однако в 1962 году Брайан Джозефсон обнаружил, что ток может течь через барьер диэлектрика.
Электроны (а точнее, куперовские пары) могут переходить из одного слоя металла в другой сквозь диэлектрический слой оксида благодаря квантовому эффекту туннелирования, и в закольцованном проводнике ток может течь бесконечно долго.
Состояние контактов Джозефсона очень чувствительно к магнитным полям, поэтому их используют в качестве высокочувствительных магнитных сенсоров (SQUID).
Кроме того, состояние джозефсоновских контактов начинает квантоваться, то есть в состоянии кубитов появляются четко выраженные уровни, связанные с направлением циркулирующего тока (у потоковых кубитов), электрическим зарядом (зарядовые кубиты) или его фазой (фазовые кубиты). Управлять такими кубитами можно с помощью микроволнового излучения.
Технология создания сверхпроводящих кубитов
Обычно джозефсоновский переход формируется при помощи напыления алюминия на подложку кремния или сапфира через маленькие (с размерами от 30 до 300 нанометров) окошки — маску, сделанную при помощи электронной литографии.
Алюминий разогревается в вакуумной установке до высоких температур, испаряется и затем осаждается на подложке.
После напыления на подложку тонкого слоя алюминия (толщиной несколько десятков нанометров) он окисляется в кислородной атмосфере, и возникает слой диэлектрика, близкого по химической формуле к сапфиру. Затем сверху напыляется другой слой алюминия, формируя два металлических слоя сверхпроводника, разделенных туннельным барьером.
Кубит в квантовых вычислениях
Как и бит, который является основным объектом информации в классических вычислениях, кубит (квантовый бит) является основным объектом информации в квантовых вычислениях. Для разъяснения этой аналогии в этой статье рассматривается простейший пример: одиночный кубит.
Представление кубита
$$0\equiv \begin
хотя противоположный выбор также допустим. Таким образом, из-за неограниченного количества возможных векторов однокубитных квантовых состояний только два из них соответствуют состояниям классических битов, чего нельзя сказать об остальных квантовых состояниях.
Измерение кубита
Визуализация кубитов и преобразований с помощью сферы Блоха
Стрелки на этой схеме показывают направление, в котором указывает вектор квантового состояния, и каждое изменение стрелки можно представить как поворот относительно одной из основных осей. Рассмотрение квантовых вычислений как последовательности поворотов является многообещающей догадкой, однако эту догадку сложно применить в разработке и описании алгоритмов. Q# упрощает эту проблему за счет создания языка для описания таких поворотов.
Однокубитные операции
Квантовые компьютеры обрабатывают данные путем применения универсального набора квантовых ворот, которые могут эмулировать любой поворот вектора квантового состояния. Это понятие универсальности является аналогом универсальности для традиционных (например, классических) вычислений, когда набор ворот считается универсальным, если каждое преобразование входных битов может быть выполнено с использованием цепи ограниченной длины. В квантовых вычислениях допустимые преобразования, которые можно выполнять с кубитами, являются унитарными преобразованиями и измерениями. Смежная операция или комплексно сопряженное транспонирование имеет критически важное значение для квантовых вычислений, так как оно необходимо для инвертирования квантовых преобразований.
Дополнительные сведения об этих операциях, их представлении в сфере Блоха и реализациях Q# см. раздел Встроенные операции и функции.
Квантовые вычисления против классических: зачем нам столько цифр
Из-за всеобщего бума блокчейна и всякой бигдаты с первых строчек техноновостей сошла другая перспективная тема — квантовые вычисления. А они, между прочим, способны перевернуть сразу несколько ИТ-областей, начиная с пресловутого блокчейна и заканчивая инфобезопасностью. В двух ближайших статьях Сбербанк и Сбербанк-Технологии расскажут, чем круты квантовые вычисления и что вообще с ними делают сейчас.
Классические вычисления: 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. Вот порядок квантовых преобразований.
Следующий уровень. Квантовые однокубитные гейты Паули
Попробуем сравнить классические и квантовые вычисления в более серьезных задачах. Для этого нам потребуется еще немного теоретических знаний.
В квантовых вычислениях обрабатываемая информация закодирована в квантовых битах – так называемых кубитах. В простейшем случае кубит, как и классический бит, может находиться в одном из двух базисных состояний: |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:
Теперь попробуем разработать аналогичную программу для квантового вычислителя:
В этой схеме первые два кубита – это аргумент, следующие два – переносы, оставшиеся 3 – результат. Вот как работает алгоритм.
Промежуточные выводы
Запустив оба примера, мы получим один и тот же результат. На квантовом компьютере это займет больше времени, потому что необходимо провести дополнительную компиляцию в квантовоассемблерный код и отправить его на исполнение в облако. Использование квантовых вычислений имело бы смысл, если бы скорость выполнения их элементарных операций – гейтов – была бы во много раз меньше чем в классической модели.
Измерения специалистов показывают, что выполнение одного гейта занимает около 1 наносекунды. Так что алгоритмы для квантового вычислителя должны не копировать классические, а по максимуму использовать уникальные свойства квантовой механики. В следующей статье мы разберем одно из основных таких свойств — квантовый параллелизм — и поговорим о квантовой оптимизации в целом. Затем определим наиболее подходящие сферы для квантовых вычислений и расскажем об их применении.
По материалам Дмитрия Сапаева, старшего руководителя направления по развитию ИТ-систем в отделе разработки ЦТИ Сбербанк-Технологий, и Дмитрия Булычкова, директора проектов в Центре технологических инноваций Сбербанка.
UPD: Мы опубликовали вторую часть статьи, где погружаемся в квантовые вычисления более глубоко и рассказываем об их практическом применении.