Алгоритм Шора.
Наиболее известным квантовым алгоритмом является алгоритм Шора (придумал в 1994 году английский математик Питер Шор), который нацелен на решение задачи разложения чисел на простые множители (задача факторизации, дискретного логарифма).
Именно этот алгоритм приводят в пример, когда пишут о том, что ваши банковские системы и пароли скоро будут взломаны. Учитывая, что длина используемых на сегодняшний день ключей не менее чем 2048 бит, время для шапочки еще не пришло.
На сегодняшний день результаты более чем скромные. Лучшие результаты факторизации с помощью алгоритма Шора — числа 15 и 21, что сильно меньше, чем 2048 бит. Для остальных результатов из таблицы применялся иной алгоритм расчетов, но даже лучший по этому алгоритму результат (291311) сильно далек от реального применения.
Подробнее про алгоритм Шора можно почитать, например, вот тут. Про практическую реализацию — тут.
Одна из текущих оценок сложности и необходимой мощности для факторизации числа из 2048 бит это компьютер с 20 миллионами кубитов. Спим спокойно.
Симуляторы квантовых компьютеров
Симуляторы квантовых компьютеров работают существенно медленнее своих реальных собратьев. Происходит это потому, что симуляторы делают свою работу гораздо честнее. Когда в симуляторе вы создаете регистр из 8 кубитов, то в памяти сохраняются все возможные значения для этих кубитов (создается массив на 256 ячеек). Если вы создадите два регистра по 8 бит и выполните операцию A+B, то симулятор посчитает и сохранит в памяти все возможные комбинации сложений (создаст массив на 65536 ячеек). Это будет существенно дольше, чем единичная операция, но после этого симулятор может вернуть вам все эти значения, не уничтожая данные при каждом “измерении”.
Чтобы получить все варианты сложения на настоящем квантовом компьютере, вы будете запускать его как минимум 65536 раз (результат возвращается рандомно, могут быть повторы), и в целом, это займет даже больше времени, чем на симуляторе.
Но если кубиты – это просто магниты в 3D пространстве, можно ли создать симулятор, который вращает их в виртуальной реальности? Я попытался и создал библиотеку FastQubit. Большая часть операций действительно успешно работает (даже состояния Белла), и такой симулятор обладает существенным превосходством над обычным квантовым компьютером:
Но есть подвох. Phase Kickback в моей библиотеке работает не верно:
Если вы заставите этот короткий код работать верно, то можете смело претендовать на Нобелевскую премию. Но не пытайтесь костылить: вы конечно можете добавить хак, который доворачивает фазу на нужный угол при определенных условиях, но это перестанет работать, когда в квантовую программу добавят запутанность сразу между несколькими кубитами.
Дисклеймер
Автор не является специалистом в квантовых вычислениях, и целевая аудитория статьи — такие же ИТ-шники, не квантовые специалисты, которые тоже хотят собрать в голове картинку под названием “Как работают квантовые компьютеры”. Из-за этого многие понятия в статье сознательно упрощены для лучшего понимания квантовых технологий на “базовом” уровне, но без совсем уж сильного упрощения с потерей информативности и адекватности.
В статье, в некоторых местах используются материалы из других источников, список которых приведен в конце статьи. Везде где это было возможно, вставлены прямые ссылки и указания на оригинал текста, таблицы или рисунка. Если где-то что-то (или кого-то) забыл, пишите — поправлю.
Физические реализации кубитов
Как мы уже говорили, кубит может быть представлен квантовым объектом, то есть таким физическим объектом, который реализует описанные выше квантовые свойства. То есть грубо говоря, любой физический объект, в котором есть два состояния и эти два состояния находятся в состоянии суперпозиции можно использовать для построения квантового компьютера.
“Если мы умеем помещать атом в два разных уровня и управлять ими, то вот вам и кубит. Если мы можем это сделать с ионом, — кубит. С током то же самое. Если мы запускаем его по часовой стрелке и против часовой стрелки одновременно, вот вам кубит.” (С)
Из всего этого многообразия наиболее проработанным является первый метод получения кубитов, основанный на сверхпроводниках. Google, IBM, Intel и прочие ведущие игроки используют именно его для построения своих систем.
Ну и еще почитайте обзор возможных физических реализаций кубитов от Andrew Daley,2014.
Немного об эмуляции квантовых компьютеров
Квантовые вычисления можно эмулировать на обычном компьютере. Ведь действительно, смотрите:
Для сравнения, Summit (Top-1 из Top-500) несет на себе всего 2.8 Петабайт памяти.
Текущий рекорд симуляций — 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере (Sunway Taihu Light)
Предел симуляции квантового компьютера на классических системах обусловлен количеством оперативной памяти необходимой для хранения состояния кубитов.
По операциям — для точной эмуляции схемы на 49 кубитов из каких-то 39 “тактов” (независимых слоев вентилей) потребовалось 2^63 комплексных умножений — 4 Пфлопс суперкомпьютера на протяжении 4 часов
Эмуляция квантового компьютера из 50+ кубит на классических системах считается невыполнимой за разумное время. В том числе из-за этого факта Google использовал для своего эксперимента с квантовым превосходством процессор с 53-мя кубитами.
Quantum Phase Estimation
Поздравляю всех самых терпеливых читателей, пройдя долгий путь непонимания мы добрались до самой сути квантовых компьютеров. Когда мы вычисляем формулу F=axmod(N) на обычном компьютере, мы ждем появления значения F=1, чтобы объявить о взломе ключа RSA. Но когда мы работаем на квантовой машине, нам на самом деле не важно, что по итогу хранится в регистре F, решение задачи будет хранится во входном регистре X.
В классическом компьютере в операторе XOR (аналог CNOT) значение контролирующей переменной не меняется, но напомню, что когда в квантовой машине мы выполняем операцию CNOT, она меняет оба кубита:
Отклонения кубита по оси Z называется фазой. За время выполнения квантовой программы все кубиты накапливают некоторое изменение фазы. Математики доказали, что, измерив итоговую фазу всех кубитов во входном регистре, можно с очень высокой вероятностью найти делители числа N (взломать RSA), даже если в F получилась не единица. Для RSA-512 нужно всего порядка 2000 запусков алгоритма на квантовом компьютере. Но есть подвох. Даже два.
Первая проблема заключается в том, что надо как-то суметь измерить фазу. Для этого используется алгоритм QFE (Quantum Phase Estimation), который требует дополнительных вращений кубитов на очень маленькие углы поворота. Для N=15 нужно вращать кубиты на 1.4o, для N=35 повороты будут уже 0.175o. Для RSA-512 нужно повернуть кубит на ничтожные 180/21022 градуса, сделав это 1022 раза. Кубиты – это аналоговая система, если ошибиться с углом поворота – на выходе мы получим ошибку. Современные квантовые компьютеры не могут справиться с числом N=35, им уже на этом этапе не хватает точности поворотов. Но это еще не так страшно, совсем ничтожными поворотами можно просто пренебречь, почти не потеряв точность всего алгоритма.
Вторая проблема заключается в вычислении axmod(N). Да, для RSA-512 надо вычислить ее всего лишь 2000 раз, но посмотрите еще раз на два вложенных цикла: одно такое вычисление – это более 21022 последовательных вращений кубитов. Это более чем фуфло. Квантовые компьютеры не способны взломать RSA, даже если они вырастут до миллиона кубитов. Есть большое количество научных статей, которые рассказывают нам, как им удалось оптимизировать эту часть и выполнить ее в сотни раз быстрее, но они всегда скромно умалчивают, сколько именно операций требуется, когда N = 2512.
Ведущие игроки
Слайды для этого раздела взяты из статьи Квантовый компьютер: большая игра на повышение. Лекция в Яндексе, от научного сотрудника Российского квантового центра Алексея Фёдорова. Позволю себе прямые цитаты:
Все технологически успешные страны в данный момент активно занимаются развитием квантовых технологий. В эти исследования вкладывается огромное количество средств, создаются специальные программы поддержки квантовых технологий.
В квантовой гонке участвуют не только государства, но и частные компании. Суммарно Google, IBM, Intel и Microsoft вложили около 0,5 млрд долларов в развитие квантовых компьютеров за последнее время, создали крупные лаборатории и исследовательские центры.
На Хабре и в Сети есть множество статей, например, вот, вот и вот, в которых текущее состояние дел с развитием квантовых технологий в разных странах рассматривается более подробно. Для нас сейчас главное, что все ведущие технологически развитые страны и игроки вкладывают огромные средства в исследования в этом направлении, что дает надежду на выход из текущего технологического тупика.
Запутанность
Квантовая запутанность – второй кит, на котором держится квантовый компьютер, и это действительно любопытный эффект, который современная наука пока не может объяснить. Но мы пойдем издалека. Давайте взглянем на типичный кусок исходного кода для традиционного компьютера:
Данная операция позволяет выполнять банальное сложение целых чисел для двух регистров кубитов. Чтобы выполнить эту операцию два кубита кратковременно подносят поближе друг к другу, после чего выполняют серию отдельных вращений. Измерения не требуются, т.е. с кубитами можно работать дальше. После этой операции кубиты запутаны. Как это проявляется? Начнем с банального:
После того, как мы запутали кубиты, они становятся зависимыми друг от друга. Если кубит Q1 был измерен как Единица, то кубит Q2 будет измерен как Ноль. Но этот случай очевиден и не интересен, давайте перед CNOT уложим кубиты на бок:
Если контролирующий кубит лежит на боку, то контролируемый будет либо повернут на 180 градусов с вероятностью 50%, либо останется в прежнем состоянии. Точное итоговое положение кубитов в 3D пространстве после такой операции не известно (они якобы сразу во многих состояниях), ведь на кубиты нельзя посмотреть непосредственно. Но если запутанные кубиты измерить, то Q1 будет рандомно падать на сенсор 0 или 1, а Q2 будет всегда падать на противоположный сенсор.
Почему так происходит никто не знает. По логике, оба кубита лежат на боку, после операции CNOT они оба должны рандомно падать на оба сенсора, без какой-либо зависимости. По факту же прослеживается четкая связь при измерении (с некоторой погрешностью, система все-таки аналоговая). На этот счет есть две теории:
На мой взгляд само явление Запутанности является главным доказательством, что Суперпозиции не существует, но я не физик-теоретик, поэтому оставим эту тему. В конце концов когда-то официальная наука высмеивала теорию движения литосферных плит, но в конце концов ребята во всем разобрались.
Пара заключительных моментов про запутанность:
Алгоритм Гровера
Алгоритм Гровера — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году.
Алгоритм Гровера может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.(С)
Подробнее можно почитать вот тут, или тут. Еще вот тут есть хорошее объяснение алгоритма на примере ящиков и мяча, но, к сожалению, по независящим ни от кого причинам, данный сайт у меня из России не открывается. Если у вас этот сайт тоже заблокирован, то вот краткая выжимка:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу? Самым тупым способом, по очереди открывать коробки, и рано или поздно вы наткнетесь на коробку с мячиком. А сколько в среднем коробок нужно проверить до того, как будет обнаружена коробка с мячиком? В среднем нужно открыть примерно половину коробок N/2. Главное здесь то, что если мы увеличим число коробок в 100 раз, то в те же 100 раз увеличится и среднее число коробок, которые нужно открыть до того, как будет найдена коробка с мячиком.
Теперь сделаем ещё одно уточнение. Пусть мы не сами открываем коробки руками и проверяем наличие мячика в каждой, а имеется некий посредник, назовем его Оракул (Oracle). Мы говорим Оракулу — «проверь коробку номер 732», и Оракул честно проверяет и отвечает «в коробке номер 732 мячика нет». Теперь вместо слов о том, сколько коробок нам нужно в среднем открыть, мы говорим «сколько раз в среднем мы должны обратиться к Оракулу для того, чтобы найти номер коробки с мячиком»
Оказывается, что если перевести эту задачу с коробками, мячиком и Оракулом на квантовый язык, то выходит замечательный результат: для поиска номера коробки с мячиком среди N коробок нам нужно потревожить Оракула всего примерно SQRT(N) раз!
То есть сложность задачи перебора используя алгоритм Гровера снижается в квадратный корень раз.
Пути решения проблем
Для решения вышеуказанных проблем, в настоящее время используют следующие подходы и методы:
Также проводятся исследования, направленные на увеличение времени декогеренции, на поиск новых (и доработку известных) физических реализаций квантовых объектов, на оптимизацию схем коррекции и прочее и прочее. Прогресс есть (посмотрите выше на характеристики более ранних и топовых на сегодняшний день чипов), но пока идет медленно, очень очень медленно.
Прототипы
Выделю три прототипа, над которыми работают крупные компании. Google, IBM, Intel, Microsoft вкладываются в развитие квантовых компьютеров. Все вместе они вложили больше 500 млн долларов в разработку, лаборатории и исследовательские центры.
Первые классические компьютеры занимали целые комнаты, работали на вакуумных лампах и так нагревались, что для них требовалось отдельное мощное охлаждение. Квантовые компьютеры на них очень похожи — это шкафы высотой по 3 метра, большую часть которых занимают системы охлаждения. Компьютеры охлаждают до температуры близкой к абсолютному нулю, чтобы квантовые системы могли выполнять свои вычислительные функции.
Универсальные квантовые компьютеры
Это универсальные машины от Google и IBM с памятью примерно 20 кубит. Они выполняют любые операции, потому что полная универсальность доступна с относительно небольшим числом кубитов, дальше возникает практическое ограничение. Возможно, через год люди научатся работать с 30-40 кубитами.
Универсальные квантовые компьютеры способны реализовать произвольные квантовые алгоритмы, например, алгоритмы Шора и Гровера.
Современная криптография основана на разложении чисел на простые множители. В настоящее время неизвестно, существует ли полиномиальный не квантовый алгоритм для задачи факторизации. Однако 25 лет назад Питер Шор опубликовал статью, в которой объяснил, как квантовый компьютер может разложить очень большое целое число на простые множители.
Квантовый алгоритм компьютера работает не детерминистически, а угадывает простые множители с вероятностью правильного ответа больше 50% и находит простые множители экспоненциально быстрее, чем обычный.
С распространением квантовых компьютеров все современные методы шифрования окажутся уязвимы, и это основная мотивация в разработке квантовых алгоритмов последние 25 лет. Но пока применить метод Шора пока сложно, потому что алгоритм требует большой квантовый компьютер. Маленькие решают задачу только для небольших чисел.
Другим примером, демонстрирующим потенциал квантовых вычислений, является Алгоритм Гровера для задачи перебора или поиска решения уравнения
какая-то сложная функция.
Кроме упомянутых выше алгоритмов Шора и Гравера есть большое количество других квантовых алгоритмов. Любая физическая система хочет перейти в состояние равновесия — квантовая не исключение. С научной точки зрения правильнее говорить не о равновесии, а об основном состоянии системы. Классический аналог — состояние покоя. Система всегда стремится перейти в состояние покоя с минимальной энергией. В терминах вычислительных задач — это оптимизационная задача минимизации энергии. Квантовый компьютер как раз может решать подобные задачи.
Вся область применимости квантовых алгоритмов и компьютеров пока не понятна. Но уже есть десятки различных оптимизационных задач, с которыми квантовые компьютеры и алгоритмы могут справиться, и находятся новые.
Квантовые симуляторы ограниченной универсальности
Это другое направление: универсальность ограничивается, но поддерживается изоляция (когерентность). Это компьютеры на рубеже в 50-70 кубитов, что в смысле памяти уже больше, чем любой суперкомпьютер.
На этой границе возможности специализированного квантового компьютера превосходят возможности классического — возникает квантовое превосходство. Это значит, что квантовые компьютеры могут решать некоторые задачи, на которые у обычных (даже суперкомпьютеров) уйдут десятки, сотни или тысячи лет.
В октябре 2019 Google заявил, что достиг квантового превосходства. Новость появилась во всех ведущих газетах и журналах, соответствующая научная статья была опубликована в Nature. Тематические статьи выпустили многие газеты, даже New York Times и Wall Street Journal, которые далеки от науки.
В реальности Google разработал квантовый процессор с ограниченной универсальностью. У него достаточно большое количество кубитов, и он может выполнять некоторые узкие задачи лучше, чем любой классический компьютер. Другой вопрос, что это очень узкие и искусственные задачи.
Некогерентные процессоры с числом кубитов от 2 тысяч
Если забыть про универсальность и когерентность, можно добавлять 2 или даже 3-4 тысячи кубитов. Этим направлением занимается компания D-Wave из Канады. У них есть процессоры с тысячей кубитов, но без когерентности.
Сравнение квантового компьютера и обычного
Давайте теперь сравним обычный компьютер и квантовый.
В обычном компьютере это бит. Хорошо нам знакомый насквозь детерминированный бит. Может принимать значения либо 0 либо 1. Он прекрасно справляется с ролью логической единицы для обычного компьютера, но совершенно не подходит для описания состояния квантового объекта, который, как мы уже говорили, в дикой природе находится в суперпозиции своих граничных состояний.
На текущем технологическом уровне развития физической реализацией бита для обычного компьютера выступает полупроводниковый транзистор, для квантового, как мы уже говорили, любой квантовый объект. В следующем разделе мы поговорим о том, что сейчас используется в качестве физических носителей кубитов.
Для обычного компьютера это электрический ток — уровни напряжения, наличие или отсутствие тока, и т.д., для квантового — то самое состояние квантового объекта (направление поляризации, спин, и т.д.), которое может находится в состоянии суперпозиции.
Для реализации логических схем на обычном компьютере используются всем нам хорошо известные логические операции, для операций над кубитами пришлось придумывать совершенно иную систему операций, называемую квантовыми вентилями. Вентили бывают однокубитные и двухкубитные, в зависимости от того, над сколькими кубитами производится преобразование.
Примеры квантовых вентилей:
Есть понятие универсального набора вентилей, которых достаточно для выполнения любого квантового вычисления. Например, универсальным является набор, включающий вентиль Адамара, вентиль фазового сдвига, вентиль CNOT и вентиль π⁄8. С их помощью можно выполнить любое квантовое вычисление на произвольном наборе кубитов.
В этой статье мы не будем детально останавливаться на системе квантовых вентилей, более подробно про них и логические операции над кубитами можно почитать, например, вот тут. Главное, что надо запомнить:
Один транзистор нам совершенно бесполезен, чтобы производить вычисления нам надо соединить много транзисторов между собой, то есть создать полупроводниковый чип из миллионов транзисторов, на которых уже строить логические схемы, АЛУ и, в конечном счете, получить современный процессор в его классическом виде.
Один кубит нам тоже совершенно бесполезен (ну если только в академическом плане),
чтобы производить вычисления нам нужна система кубитов (квантовых объектов)
которая, как мы уже говорили, создается при помощи запутывания кубитов между собой так, чтобы изменения в их состояниях происходили согласованно.
Стандартные алгоритмы, которые накопило человечество к текущему моменту, совершенно не подходят для реализации на квантовом компьютере. Да в общем-то и незачем. Квантовые компьютеры, основанные на вентильной логике над кубитами, требуют создания совершенно иных алгоритмов, квантовых алгоритмов. Из наиболее известных квантовых алгоритмов можно выделить три:
И самое главное отличие — это принцип работы. У стандартного компьютера это цифровой, жестко детерминированный принцип, основанный на том, что если мы задали какое-то начальное состояние системы и пропустили его через заданный алгоритм, то результат вычислений будет один и тот же, сколько бы раз мы это вычисление не запускали. Собственно, такое поведение это именно то, что мы от компьютера и ждем.
Квантовый компьютер работает на аналоговом, вероятностном принципе. Результат работы заданного алгоритма на заданном начальном состоянии представляет собой выборку из вероятностного распределения конечных реализаций алгоритма плюс возможные ошибки.
Такая вероятностная природа квантовых вычислений обусловлена самой вероятностной сутью квантового мира. “ Бог не играет в кости со вселенной”, — говорил старик Эйнштейн, но все эксперименты и наблюдения пока (в текущей научной парадигме) подтверждают обратное.
Декогеренция
Описание от N+1.
Квантовое состояние очень хрупкая штука, кубиты в запутанном состоянии крайне нестабильны, любое внешнее воздействие может разрушить (и разрушает) эту связь. Изменение температуры на мельчайшую долю градуса, давление, пролетевший рядом случайный фотон — все это дестабилизирует нашу систему.
Для решения этой проблемы строят низкотемпературные саркофаги, в которых температура (-273.14 градуса цельсия) чуть-чуть выше абсолютного ноля, с максимальной изоляцией внутренней камеры с процессором от всех (возможных) воздействий внешней среды.
Максимальное время жизни квантовой системы из нескольких запутанных кубитов, в течение которого она сохраняет свои квантовые свойства и может быть использована для произведения вычислений, называют временем декогеренции.
На текущий момент время декогеренции в лучших квантовых решениях составляет порядка десятков и сотен микросекунд.
Есть прекрасный сайт, на котором можно посмотреть сравнительные таблицы параметров всех созданных квантовых систем. В эту статью для примера вынесены только два топовых процессора — от IBM IBM Q System One и от Google Sycamore. Как мы видим, время декогеренции (Т2) не превышает 200 мкс.
Я не нашел точных данных по Sycamore, но в самой статье о квантовом превосходстве приводятся две цифры — 1 миллион вычислений за 200 секунд, в другом месте — за 130 секунд без потерь на управляющие сигналы и прочее. В любом случае это дает нам время декогеренции порядка 150 мкс. Помните нашего экспериментатора с мешком? Ну так вот он.
Чем нам грозит декогеренция?
Основная проблема в том, что через 150 мкс наша вычислительная система из N запутанных кубитов начнет выдавать на выходе вместо вероятностного распределения правильных решений — вероятностный белый шум.
То есть нам надо:
И сделать все это за 150 мкс. Не успел — результат превратился в тыкву.
Без математики и философии
Время на прочтение
В этой статье я разберу по косточкам все тайны квантовых компьютеров: что такое суперпозиция (бесполезна) и запутанность (интересный эффект), могут ли они заменить обычные компьютеры (нет) и могут ли они взломать RSA (нет). При этом я не буду упоминать волновую функцию и столь раздражающих Bob и Alice, которых вы могли встречать в других статьях про квантовые машины.
Первое и самое главное, что нужно знать – квантовые компьютеры не имеют ничего общего с обычными. Квантовые компьютеры по своей природе – аналоговые, там нет бинарных операций. Вероятно, вы уже слышали про Кубиты, что у них есть состояние 0, 1 и 0-1 одновременно, и благодаря этому вычисления выполняются очень быстро: это заблуждение. Кубит – это магнит (обычно атом или электрон), подвешенный в пространстве, который может вращаться по всем трем осям. Собственно, вращение магнита в пространстве – это и есть операции квантового компьютера. Почему это может ускорить вычисления? Было очень сложно найти ответ, но самые стойкие читатели увидят его в конце статьи. Начнем разоблачения.
Оглавление
Пока что ничего. Мы находимся в так называемой эре NISQ — Noisy Intermediate-Scale Quantum technology. Это значит, что сейчас нет таких квантовых устройств, которые могли бы соперничать с классическими компьютерами. Пока нельзя создать квантовую систему, которая по всем параметрам превзойдет классическую: достаточно небольшую, универсальную и изолированную. Пока получаются только системы, которые выполняют узкоспециальные задачи определенного сорта лучше, чем вычислительный кластер. Квантовые технологии пока непрактичны. Хотелось бы использовать этот огромный потенциал для своих ежедневных задач, но неизвестно, как это сделать.
У квантовых технологий огромный «подрывной потенциал». Если научиться хорошо решать хотя бы одну из оптимизационных задач, о которых говорилось выше, это изменит одну конкретную индустрию, как минимум. Надеюсь, что через 5-10 лет в некоторых направлениях ситуация изменится.
Многие компании создают прообразы настоящих квантовых компьютеров — они уже что-то умеют делать, но пока этого недостаточно.
В Сколтехе мы пытаемся ответить на главный вопрос — как и для чего можно использовать квантовый компьютер. С моими коллегами Владимиром Антоновым и Олегом Астафьевым трудимся над проектом, в рамках которого работаем над маленьким квантовым компьютером. К сожалению, часть архитектурных и дизайнерских вопросов еще не решены, потому что мы все еще не уверены, какие именно задачи должен будет решать этот компьютер. Если этот вопрос вам интересен, приглашаю его обсудить.
То, с каким интересом участники HighLoad++ восприняли доклад о квантовых компьютерах и АЭС, натолкнуло нас на мысль уделить большее внимание подобным темам на наших конференциях. Поэтому на РИТ++ в мае в онлайне у нас будут секции научпопа и применения IT в смежных областях. И это только малая часть новинок фестиваля «Российские интернет-технологии» — подробнее смотрите на сайте и в рассылке.
Заявление Google о достижении квантового превосходства
54-кубитный процессор Sycamore
Итак, в октябре 2019 года разработчики Google опубликовали в научном издании Nature статью «Квантовое превосходство с применением программируемого сверхпроводящего процессора». Авторы объявили о достижении впервые в истории квантового превосходства с помощью 54-кубитного процессора «Sycamore».
В сети в статьях Sycamore часто упоминают то как 54-х кубитный процессор, то как 53-х. Истина в том, что согласно оригинальной статье, процессор физически состоит из 54-х кубитов, но один из них нерабочий и выведен из эксплуатации. Таким образом, в реальности мы имеем 53-х кубитный процессор.
В Сети тут же появилось множество материалов на эту тему, градус которых варьировался от восторженных до скептических.
Позднее сотрудники отдела квантовых вычислений компании IBM заявили, что Google ложно сообщила о достижении квантового превосходства. В компании утверждают, что обычный вычислитель справится с этой задачей в худшем случае за 2,5 дня, и при этом полученный ответ будет точнее, чем у квантового компьютера. Такой вывод был сделан по итогам проведенного теоретического анализа нескольких способов оптимизации.
Что же в реальности сделал Google? Для детального понимания почитайте Ааронсона, а кратко вот:
То есть Google реализовал синтетическую задачу на 53-х кубитном процессоре, и свое заявление о достижении квантового превосходства основывает на факте невозможности эмуляции такого процессора на стандартных системах за разумное время.
Для понимания — в этом разделе нисколько не умаляется достижение Google, инженеры действительно молодцы, а вопрос о том можно считать это реальным квантовым превосходством или нет, как уже говорилось ранее, скорее философский, чем инженерный. Но надо понимать, что достигнув такого вычислительного превосходства мы ни на шаг не продвинулись к возможности запускать алгоритм Шора на 2048-и битных числах.
Направления развития
На текущий момент (могу ошибаться, поправьте) основные усилия (и более-менее значимые результаты) у всех ведущих игроков сосредоточены на двух направлениях:
Прочие же вектора развития, которые дает нам квантовая физика, такие как:
безусловно тоже в списке направлений для исследований, но каких-то более-менее значимых результатов в настоящее время вроде как еще нет.
Дополнительно можно почитать дорожную карту развития квантовых технологий, ну и гуглите “развитие квантовых технологий”, например, вот, вот и вот.
Архитектура процессора
В теории мы строим и оперируем схемами из десятков запутанных кубитов, в реальности же все сложнее. Все существующие квантовые чипы (процессоры) построены таким образом, что обеспечивают безболезненное запутывание одного кубита только со своими соседями, которых не больше шести.
Если же нам надо запутать 1-й кубит, скажем, с 12-м, то нам придется строить цепочку дополнительных квантовых операций, задействовать дополнительные кубиты и прочее, что увеличивает общий уровень ошибок. Да, и не забывайте про время декогеренции, возможно к тому моменту, когда вы закончите связывать кубиты в нужную вам схему, время закончится и вся схема превратится в симпатичный генератор белого шума.
Также не забывайте, что архитектура у всех квантовых процессоров разная, и программу, написанную в эмуляторе в режиме “связность всех со всеми” нужно будет “перекомпилировать” в архитектуру конкретного чипа. Есть даже специальные программы оптимизаторы для выполнения этой операции.
Максимальная связность и максимальное количество кубитов для тех же топовых чипов:
И, для сравнения, таблица с данными предыдущего поколения процессоров. Сравните количество кубитов, время декогеренции и процент ошибок с тем, что мы имеем сейчас у нового поколения. Все-таки прогресс потихоньку, но движется.
Резюме
Квантовые компьютеры и квантовые вычисления — очень многообещающая, очень молодая и пока малоприменимая в промышленном плане область информационных технологий.
Развитие квантовых вычислений позволит (когда-нибудь) решать задачи:
Основные проблемы при создании и эксплуатации квантовых компьютеров:
Состояние дел на текущий момент:
Что может помочь:
На мой взгляд (исключительно личное мнение), в текущей научной парадигме знаний мы не добьемся значительных успехов в развитии квантовых технологий, тут нужен качественный прорыв в какой-либо области фундаментальной или прикладной науки, который даст толчок новым идеям и методам.
Ну а пока — нарабатываем опыт в квантовом программировании, собираем и создаем квантовые алгоритмы, тестируем идеи и прочее и прочее. Ждем прорыва.
D-Wave
Если коротко (взято из вики):
Компьютеры D-Wave работают на принципе квантовой релаксации (квантовый отжиг), могут решать крайне ограниченный подкласс задач оптимизации, и не подходят для реализации традиционных квантовых алгоритмов и квантовых вентилей.
Более подробно можно почитать, например, тут, тут (осторожно, может не открываться из России), или у Scott Aaronson в статье из его блога. Кстати, очень рекомендую почитать вообще его блог, там много хорошего материала
Вообще с самого начала анонсов у научного сообщества возникали вопросы к компьютерам D-Wave. Например, в 2014 году IBM поставила под сомнение факт, что D-Wave использует квантовые эффекты. Дело дошло до того, что в 2015 году Google вместе с NASA купила один из таких квантовых компьютеров и после исследований подтвердила, что таки да, компьютер работает и вычисляет задачу быстрее, чем обычный. Еще про заявление Google можно почитать тут и, например, тут.
Главное, что компьютеры D-Wave, с их сотнями и тысячами кубитов нельзя использовать для вычисления и запуска квантовых алгоритмов. На них нельзя запустить алгоритм Шора, например. Все, что они могут — это используя определенные квантовые механизмы решать определенную задачу оптимизации. Можно считать, что D-Wave это такой квантовый ASIC для конкретной задачи.
Ошибки
Как мы уже говорили, квантовые процессы и квантовые вычисления имеют вероятностную природу, мы не можем быть уверены на 100% ни в чем, а только с какой-то вероятностью. Ситуация усугубляется еще и тем, что квантовые вычисления подвержены ошибкам. Основные типы ошибок при квантовых вычислениях это:
Ошибки, связанные с декогерентностью, возникают сразу же, как только мы запутали наши кубиты и начали производить вычисления. Чем больше кубитов мы запутали, тем сложнее система, и тем легче ее разрушить. Низкотемпературные саркофаги, защищенные камеры, все эти технологические ухищрения как раз направлены на то, чтобы снизить число ошибок и продлить время декогеренции.
Вычислительные ошибки гейтов — любая операция (вентиль) над кубитами может с некоторой вероятностью завершиться с ошибкой, а нам для реализации алгоритма нужно выполнить сотни вентилей, вот и представьте, что мы получим в конце выполнения нашего алгоритма. Классический вариант ответа на вопрос — “Какова вероятность встретить динозавра в лифте?” — 50х50, или встретишь или нет.
Проблема еще усугубляется тем, что стандартные методы коррекции ошибок (дублирование вычислений и усреднение) в квантовом мире не работают из-за теоремы о запрете клонирования. Для коррекции ошибок в квантовых вычислениях пришлось придумать квантовые же методы коррекции. Грубо говоря мы берем N обычных кубитов и делаем из них 1 логический кубит с меньшим уровнем ошибок.
Но тут возникает другая проблема — общее количество кубитов. Смотрите, допустим у нас есть процессор со 100 кубитами, из которых 80 кубитов заняты коррекцией ошибок, тогда нам для вычислений остается только 20.
Ошибки считывания финального результата — как мы помним, результат квантовых вычислений нам представлен в виде вероятностного распределения ответов. Но считывание финального состояния тоже может завершиться с ошибкой.
На том же сайте есть сравнительные таблицы процессоров по уровням ошибок. Для сравнения возьмем те же процессоры, что и в предыдущем примере — IBM IBM Q System One и Google Sycamore:
Здесь фиделити — мера схожести двух квантовых состояний. Величину ошибки можно грубо представить как 1-Fidelity. Как мы видим, ошибки на 2-х кубитных гейтах и ошибки считывания являются главным препятствием к выполнению сложных и длинных алгоритмов на существующих квантовых компьютерах.
Еще можно почитать роадмап от 2016 года от NQIT по решению задачи коррекции ошибок.
Квантовое вычислительное превосходство.
Википедия дает нам следующее определение квантового вычислительного превосходства:
Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить.
Фактически достижение квантового превосходства означает, что, например, факторизацию больших чисел по алогритму Шора можно решать за адекватное время, или можно эмулировать на квантовом уровне сложные химические молекулы, и так далее. То есть новая эпоха наступила.
Но в формулировке определения есть некоторая лазейка, “которые классические компьютеры практически не могут решить”. Фактически это означает, что если создать квантовый компьютер из 50+ кубитов и запустить на нем некоторую квантовую схему, то, как мы рассматривали выше, результат работы этой схемы невозможно будет сэмулировать на обычном компьютере. То есть классический компьютер воссоздать результат работы такой схемы будет не в состоянии.
Является ли такой результат реальным квантовым превосходством или нет, вопрос скорее философский. Но понимать, что сделал Google, и на чем основано его недавнее заявление о достижении квантового превосходства на своем новом процессоре Sycamore надо.
Как работает обычный компьютер
Чтобы объяснить, что такое квантовый компьютер и как он работает, нужно начать издалека и рассказать, как работает компьютер обычный. Работа обычного компьютера определяется двумя параметрами: памятью, скоростью вычислений.
Память — основная характеристика вычислительной системы. Компьютер умеет читать, писать и обрабатывать информацию, которая хранится в памяти.
Компьютер выполняет простейшие операции: перемножения, вычитания, сложения чисел. Если выполнять эти операции много и быстро, то можно объединить их в программу, которая обрабатывает информацию. Так работают базы данных, поиск или нейронные сети. Здесь важна скорость вычислений или скорость выполнения операций (FLOPS).
Есть еще третий (дополнительный) параметр — детерминизм, общая характеристика для всех вычислительных систем. Означает, что все машины работают по программе, которая однозначна — ноль всегда ноль, а единица это точно единица. Никаких иных толкований не предусмотрено и нет элемента неопределенности.
Неопределенность можно внести только на уровне входных данных, например, случайными числами. Ввод может быть случайным, но программа всегда однозначно обрабатывает все входящие данные.
Квантовый алгоритм Шора
Квантовый алгоритм Шора также начинается с вычисления формулы axmod(N), но тут возникает очень много проблем:
Ребята не стали отчаиваться и придумали набор костылей. Число x на вход квантовой программы подается как рандомное. Если быть точнее, то набор кубитов (регистр) для хранения числа x переводится в суперпозицию (кубиты укладываются на бок). Начиная с этого момента официально заявляется, что axmod(N) будет выполнена сразу для всех возможных чисел x за одну операцию. Как мы видели выше, толку от этого мало, т.к. измерить мы сможем только один результат из всех, причем рандомный.
Далее, сама формула axmod(N) заменяется на очень странный код (показана симуляция квантового компьютера):
Полный исходный код доступен в моем репозитории.
Вы наверное очень удивлены, как это вообще может работать? Это костыль, который позволяет выполнять формулу axmod(N) для a=2 и N=15. Число x может быть любым. Есть отдельные методики, которые позволяют подобрать перечень вращений кубитов для любых чисел a и N. Как это работает, я не стал разбираться, поскольку документация на квантовые алгоритмы традиционно крайне низкого качества, но мои собственные опыты подтвердили, что вычисления выполняются корректно.
Соответственно, если мы хотим взломать какой-то ключ RSA-512, то сначала для этого конкретного ключа мы должны составить схему, которая будет включать в себя очень много вращений. Но сколько раз мы должны запустить такую схему? Вы обратили внимание на два вложенных цикла в исходном коде выше? Для числа N=15 схема запускается 255 раз, для N=21 – 511 раз, для пока недостижимого квантовым компьютерам N=35 будет 2047 запусков. Количество операций резко возрастает, в чем же профит квантового компьютера?