квантовое превосходство что это
Квантовое превосходство: как устроены и над чем работают квантовые компьютеры
В Китае 4 декабря заявили о создании квантового суперкомпьютера: таких успехов ранее смогла достичь только Google. Этот прорыв был назван квантовым превосходством — показателем, что суперкомпьютеры могут делать вычисления на недостижимых скоростях. Рассказываем, зачем это нужно и как открытие скажется на развитии технологий.
Читайте «Хайтек» в
Что такое квантовый компьютер
Основное отличие квантовых компьютеров от традиционных, транзисторных, которыми все мы пользуемся сейчас, — то, как они работают с данными. Привычные нам устройства — от смартфонов и ноутбуков до суперкомпьютера-шахматиста Deep Blue — хранят все в битах. Так называется мельчайшая единица информации, которая может принимать всего два значения: либо ноль, либо единица.
В классическом компьютере один бит может хранить только число: ноль или единицу. Квантовая физика, однако, допускает суперпозицию состояний. Квантовый бит может находиться в нулевом и единичном состояниях одновременно — и это открывает невероятные возможности для сверхбыстрых вычислений.
Для этого ему нужны тысячи супермощных процессоров. В результате вычисления, на которые у мощного игрового компьютера уйдет неделя, суперкомпьютер выполняет за день. Однако важно, чтобы программы работали корректно, с учетом технических особенностей машины. Иначе то, что корректно работает на 100 процессорах, сильно замедлится на 200.
Квантовые компьютеры хранят и обрабатывают данные с помощью квантовых битов — кубитов. Последние могут не только включаться и выключаться, но и находиться в переходном состоянии или даже быть включенными и выключенными одновременно. Продолжая аналогию с лампочками: кубит — это как светильник, который вы выключили, а он все равно продолжает моргать. Или кот Шредингера, который одновременно и жив, и мертв.
Поскольку лампочки в квантовом компьютере одновременно горят и не горят, это сильно экономит время. Поэтому он решает сложные задачи намного быстрее даже очень мощного классического устройства.
В 2001 году Айзек Чуанг, руководитель исследовательской группы лаборатории IBM, адъюнкт-профессор MIT и пионер в области квантовых вычислений, сконструировал квантовый компьютер, основанный на одной молекуле. Результаты, которые были опубликованы в Nature, представляли собой первую экспериментальную реализацию алгоритма Шора — квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число за время.
Когда у вас слишком много атомов, это похоже на большой лес. Было очень трудно контролировать один атом с помощью предыдущего. Сложность состоит в том, чтобы реализовать [алгоритм] в системе, которая достаточно изолирована: одновременно она должна оставаться квантово-механической достаточно долго, чтобы у вас действительно была возможность реализовать весь алгоритм.
Айзек Чуанг, руководитель исследовательской группы лаборатории IBM, адъюнкт-профессор MIT и пионер в области квантовых вычислений
Квантовые компьютеры выглядят не так, как обычные. Это большие цилиндры из металла с закрученными проводами, которые опущены в холодильные установки.
Они могут использоваться для разных задач, включая вычисления в области химии и физики или для создания новых материалов. Ещё одна область применения квантового компьютера — криптография и вопросы безопасности. Эти вопросы наиболее остро чувствуют финансовые организации, банки, что неудивительно: в последнее время только и гремят скандалы об утечках и взломах.
Возможности квантового компьютера позволят получить доступ к любой информации, поэтому пора задуматься о её защите с помощью релевантных технологий, либо использовании квантового компьютера для создания улучшенного шифрования.
Что означает формулировка «квантовое превосходство»?
Квантовое превосходство — способность решить задачу, находящуюся за пределами возможностей самых современных суперкомпьютеров.
В последние годы значительный прогресс был достигнут в развитии сверхпроводниковой платформы. Суть квантового превосходства заключается в том, что квантовый вычислитель оперативно решает задачу, на которую классическому суперкомпьютеру требуется колоссальное время.
Первый прорыв случился в конце октября 2019 года, когда в компании Google заявили о том, что они разработали квантовый компьютер Google Sycamore: по их данным, система за 200 секунд справилась с задачей, которая потребует порядка 10 тыс. лет работы классических суперкомпьютеров. Вот это и назвали термином «квантовое превосходство».
Однако работа компании была встречена с долей скепсиса, а конкуренты из IBM подсчитали, что на деле использованная задача может быть решена и за пару дней — достаточно для преимущества, но не для полноценного превосходства.
Следующая веха развития квантовых компьютеров пришлась на начало декабря 2020 года. 4 декабря стало известно, что китайские ученые создали прототип квантового компьютера «Цзючжан», который справился со стандартным проверочным алгоритмом в 10 млрд раз быстрее, чем Sycamore – 53-кубитный прототип квантового компьютера от компании Google. В компании заявили, что их разработка также достигла квантового превосходства.
Ученые проверили вычислительные способности «Цзючжана» с помощью специального алгоритма GBS. Система справилась с ним в 100 трлн раз быстрее самого мощного из существующих суперкомпьютеров. Кроме того, разработчики заявили, что вычислительные способности их аппарата в 10 млрд раз превышают Sycamore.
В 2001 году Чуанг, пионер в области квантовых вычислений, сконструировал квантовый компьютер, основанный на одной молекуле, которую можно было удерживать в суперпозиции и манипулировать ядерным магнитным резонансом, чтобы множить число 15. Результаты, которые были опубликованы в Nature, представляли собой первая экспериментальная реализация алгоритма Шора. Но система не была масштабируемой; по мере добавления новых атомов управлять системой становилось все труднее.
Как будут использоваться новые квантовые компьютеры?
Одно из самых важных применений квантового компьютера сейчас — разложение на простые числа. Дело в том, что вся современная криптография основана на том, что никто не сможет быстро разложить число из 30–40 знаков (или больше) на простые множители. На обычном компьютере на это уйдёт миллиарды лет. Квантовый компьютер сможет это сделать примерно за 18 секунд.
Если допустить тот факт, что наличие квантового компьютера через некоторое время станет общественной нормой, в таком случае во всем киберпространестве не будет тайн, так как любые алгоритмы шифрования можно будет сразу взломать и получить доступ к чему угодно. Это касается всего — от банковских переводов до сообщений в мессенджере.
Ещё квантовые компьютеры отлично подходят для моделирования сложных ситуаций, например, расчёта физических свойств новых элементов на молекулярном уровне. Это, возможно, позволит быстрее находить новые лекарства или решать сложные ресурсоёмкие задачи.
Чем еще он может заниматься?
Работа с BigData станет невероятно быстрой. Shazam, прокладывание маршрутов, нейронные сети, искусственный интеллект — все это получит невероятный толчок. Еще появится возможность строить модели взаимодействия сложных белковых соединений. Это станет очень важным шагом для медицины, открывающим просторы для создания будущих лекарств, понимания того как на нас влияют разные вирусы и так далее.
Благодаря огромной скорости разложения на простые множители квантовый компьютер позволит расшифровывать сообщения, зашифрованные широко применяемым криптографическим алгоритмом RSA. До сих пор этот алгоритм считается сравнительно надёжным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Благодаря квантовому алгоритму Шора эта задача становится вполне осуществимой, если квантовый компьютер будет построен.
Квантовые компьютеры, в теории, хорошо подходят для нужд машинного обучения. Они манипулируют большими объёмами данных за один проход и способны моделировать нейронную сеть экспоненциального размера. В 2013 году корпорация Google объявила об открытии лаборатории по квантовым исследованиям в области искусственного интеллекта. Концерн Volkswagen ведёт исследования в сфере применения квантовых компьютеров для разработки беспилотного автомобиля и новых типов аккумуляторных батарей (используя квантовые компьютеры Google и D-Wave). В ноябре 2018 года концерн объявил о разработке системы управления дорожным движением (с интеграцией в неё беспилотных машин), работающей с использованием квантовых компьютеров D-Wave.
Предполагается, что с помощью квантовых компьютеров станет возможным точное моделирование молекулярных взаимодействий и химических реакций. Химические реакции являются квантовыми по своей природе. Для классических компьютеров доступен обсчёт поведения только относительно простых молекул. По прогнозам экспертов, моделирование на квантовых компьютерах открывает новые перспективы для развития химической отрасли, в частности, при создании лекарств
А что в России?
Россия активно включилась в квантовую гонку, об этом около года назад написал Nature. Принята также «дорожная карта развития квантовых вычислений». Если говорить о текущем статусе, в России созданы ключевые элементы для всех основных платформ квантовых вычислений.
Следующий шаг состоит в их масштабировании и демонстрации решения задач с помощью них. Стоит отметить, что программа ориентирована не только на «железо» и процессоры, но и на программное обеспечение. Для следующего прорыва в квантовых вычислениях определенно необходимы оригинальные идеи — традиционно сильная сторона российских ученых.
В конце ноября 2020 года стало известно о создании консорциума «Национальная квантовая лаборатория» (НКЛ). Консорциум, в который вошли структуры «Росатома», фонд «Сколково» и университеты, будет заниматься экспортом квантовых технологий и развивать инфраструктуру. Но главная задача — создать квантовый компьютер.
В рамках «дорожной карты» «Квантовые вычисления» планируется построить на территории Сколково центр нанофабрикации площадью 2 тыс. кв. м, а также передовой лабораторный комплекс площадью более 3,5 тыс. кв. м.
Среди основных показателей, указанных в «дорожной карте», которых планируется достичь в том числе с помощью создания НКЛ, — к концу 2024-го члены консорциума должны создать вычислительные системы на различных квантовых платформах мощностью от 30 до 100 кубитов, выйти на регистрацию 40 международных патентов в год.
Google достигла квантового превосходства
Пример элементов квантового компьютера Rigetti Computing
Квантовый компьютер Google смог за 3 минуты и 20 секунд выполнить расчет, на который самому мощному в мире суперкомпьютеру Summit (IBM) понадобилось бы примерно 10 тыс. лет. Информацию об этом научном открытии сотрудники компании изложили в публикации, которая была размещена на сайте НАСА. Однако через некоторое время данный доклад был удален с сайта без объяснения причин. Но в издании Financial Times успели изучить и проанализировать текст открытия.
В конце августа 2019 года специалисты Google подготовили доклад «Quantum Supremacy Using a Programmable Superconducting Processor» о своем открытии при использовании нового квантового компьютера — достижении квантового превосходства. Материал был опубликован в сентябре 2019 года на сайте НАСА, но позже удален. Данные этого доклада остались в кэше Bing и доступны по этой ссылке.
Квантовое превосходство – переломный момент, при котором квантовый компьютер сможет выполнить задачу, решить которую раньше считалось невозможным или на ее решение потребовалось бы невероятное количество времени, используя текущие передовые технические достижения цивилизации.
Квантовый компьютер — это вычислительное устройство, которое использует явления квантовой суперпозиции и квантовой запутанности для передачи и обработки данных. Квантовый компьютер (в отличие от обычного) оперирует не битами (способными принимать значение либо 0, либо 1), а кубитами, имеющими значения одновременно и 0, и 1. Теоретически, это позволяет обрабатывать все возможные состояния одновременно, достигая существенного превосходства над обычными компьютерами в ряде алгоритмов.
Многие компании и университеты во всем мире участвуют в создании квантовых компьютеров, но лидером в этой гонке уже несколько лет остается Google.
Уже в 2017 году инженеры подразделения Google по квантовым аппаратным средствам использовали квантовый компьютер с 22-кубитовым процессором.
Квантовые процессоры Google находятся в лаборатории компании в Санта-Барбаре. Там их держат в специальных резервуарах — криостатах. Сжатый гелий и жидкий азот, перекачиваемый из морозильного резервуара, охлаждают внутренности криостата до минус 273,11°C. Такая низкая температура необходима для сохранения сверхпроводимости.
Фактически, это квантовая интегральная система, включающая в себя помимо криостата с кубитами и классическую электронику, которая отвечает за удаленный доступ специалистов к системе для программных исследований и анализа полученных данных. При этом все элементы системы должны быть надежно защищены от взаимных и внешних помех.
Это сложная и дорогая система для проведения квантовых вычислений, а на ее обслуживание и эксплуатацию компания тратит немалые деньги.
Инженерную команду по разработке квантовых технологий в Google возглавляет Хартмут Невен. Невен в компании ранее курировал самые инновационные проекты — от программного обеспечения ИИ для распознавания лиц до запуска в производство Google Glass.
В конце 2017 года команда Невена в Южной Калифорнии готовилась к запуску квантового компьютера на 49-кубитовом процессоре, используя который планировалось преодолеть новый технологический рубеж, после которого квантовые компьютеры смогли бы достигнуть квантового превосходства.
Также в компании работают над созданием новой архитектуры квантового компьютера, чтобы была возможность работать с ним при более высоких температурах, а также с помощью новых инженерных решений уменьшить помехи во время передачи данных.
И вот, в сентябре 2019 года специалисты Google опубликовали доклад о своем открытии при использовании нового квантового компьютера — достижении квантового превосходства.
В научном эксперименте принимал участие квантовый компьютер Google с 53-кубитовым процессором, получивший название «Sycamore» (Платан). Для создания инфраструктуры Платана команде Google по разработке квантовых технологий даже пришлось даунгрейдить проект созданного ранее 72-кубитового процессора «Bristlecone».
В удаленном по неизвестным причинам материале на сайте НАСА утверждалось, что квантовый компьютер Google смог выполнить очень сложный программный расчет всего за двести секунд. Таким образом, была осуществлена экспериментальная демонстрация превосходства квантового компьютера над традиционным.
Для сравнения, самый современный мощный суперкомпьютер Summit смог бы произвести подобный результат лишь за 10 тыс. лет. Суперкомпьютер Summit был запущен в США в 2018 году. Его расчетная мощность составляет 200 тыс. трлн операций в секунду, он состоит из 4608 вычислительных серверов, на каждом из которых установлено два 22-ядерных процессора IBM Power9, а встроенная память достигает 10 петабайт.
Также по оценкам специалистов компании, выполнение того же эксперимента на сервере Google Cloud заняло бы 50 трлн часов (5.7 млрд лет).
В своей публикации специалисты Google уточнили, что их новая система может выполнять только один расчет, а использование квантовых компьютеров для решения практических задач находится еще в далеком будущем.
Был ли связан этот расчет с определенными исследованиями или математическими задачами, в компании не уточнили. Хотя специалисты компании пояснили в статье, что в эксперименте были использованы случайные числа, сгенерированные по специальному сценарию, связанному с квантовыми явлениями.
«Нами было достигнуто существенное ускорение по сравнению со всеми известными классическими алгоритмами, которое смогло обеспечить экспериментальную реализацию квантового превосходства в решенной вычислительной задаче, что знаменует появление столь ожидаемой вычислительной парадигмы», — утверждалось в докладе Google.
Так же в докладе было предположение, что мощность новых квантовых систем будет увеличиваться с «двойной экспоненциальной скоростью», опережая даже экспоненциальную скорость, которая определяла закон Мура — тенденции, при которой традиционные вычислительные мощности удваиваются примерно каждые два года.
По поводу удаления публикации с сайта НАСА — в Google отказались подтвердить подлинность доклада и его результатов, в НАСА также не ответили на запрос о комментарии по поводу этого странного снятия с публикации материала.
Однако, по данным издания Fortune источник в Google, знакомый с этой ситуацией, предположил, что в НАСА случайно слишком рано опубликовали данный документ.
Ведь результаты расчета и анализ хода вычислений квантового компьютера еще предстоит тщательно проверить экспертами и учеными. И такой процесс сложной научной экспертной оценки может продлиться от нескольких недель до месяцев. Также данная статья будет находится под пристальным вниманием научного сообщества, а если ее результаты подтвердятся, то это станет станет предвестником переломного момента в квантовой науке.
Почему данные об этом эксперименте были опубликованы на сайте НАСА? В 2018 году Google заключил соглашение с НАСА об использовании суперкомпьютеров агенства для проверки расчетов, выполненных компанией с помощью квантовых компьютеров.
В общем итоге, какие бы не были результаты в расчетах Google, многие разработчики в сфере квантовых технологий опасаются, что текущие результаты эксперимента могут быть преувеличены и они обеспокоены фактом, что повышенные ожидания от неминуемого прогресса в этой области в краткосрочной перспективе приведут к возникновению нового технологического пузыря, который может быстро лопнуть.
Дарио Джил (Dario Gil), руководитель IBM Research, не советует использовать термин «квантовое превосходство» в качестве метрики для измерения прогресса в этой области. «Данный эксперимент и термин «квантовое превосходство» будут неправильно поняты почти всеми», — предостерег Джил. По его словам, это был особый лабораторный эксперимент, который на данный момент не имеет практического применения.
«Квантовые компьютеры никогда не будут господствовать над классическими компьютерами, а будут работать вместе с ними, поскольку у каждого есть свои уникальные преимущества», — заявил Джил.
Джим Кларк, директор Intel Labs по квантовым технологиям, обозначил такое достижение Google как значительный маркер в развитии квантовых компьютеров. Однако, по его словам, коммерчески жизнеспособный квантовый компьютер еще потребует многих достижений и решений в области НИОКР, прежде чем станет реальностью.
«Несмотря на то, что эта разработка все еще находится на первом этапе своего марафона, мы твердо верим в потенциал этой технологии», — добавил Кларк.
Превосходный набор вопросов и ответов о квантовом превосходстве
Из блога Скотта Джоэла Аронсона, специалиста в области теории вычислительных машин и систем, преподавателя факультета компьютерных наук Техасского университета в Остине
Вы читали эти истории – в Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [на Хабре / прим. перев.] или где-то ещё – о том, что группа исследователей в Google достигла квантового вычислительного превосходства со своим сверхпроводящим устройством из 53 кубитов. Их легко найти, но ссылок на них я давать не буду – просто потому, что они пока не должны существовать.
Миру известно, что Google действительно готовит большой анонс квантового превосходства, который должен выйти одновременно с публикацией исследовательской работы в одном из уважаемых научных журналов. И это, скорее всего, произойдёт в течение месяца.
Тем временем НАСА, участвовавшее в этой разработке, случайно выложило старую версию работы Google на общедоступном сайте. Она пробыла там недолгое время, но достаточное для т ого, чтобы попасть в Financial Times, мою папку «входящие» и миллионы других мест. Рассуждения об этой работе, лишённые фактов, предсказуемо распространились повсюду.
Судя по всему, у нашего мира отняли возможность чётко объявить о новом моменте «выхода человека в космос», в котором в рамках пресс-конференции будет экспериментально опровергнут сильный тезис Чёрча — Тьюринга. Это больше будет похоже на полёт братьев Райт, отрывочные слухи о котором всплывали в промежутке начиная с 1903 и заканчивая 1908 годом, в котором Уилбур и Орвилл, наконец, согласились на демонстрационные полёты (только в нашем случае, к счастью, на разъяснение вопроса уйдёт куда как меньше времени!)
Я уже пару месяцев в курсе происходящего; мне было чрезвычайно сложно не писать об этом в блоге. Я пообещал молчать, но не мог сопротивляться желанию оставлять тут и там разные намёки – к примеру, во время моего выступления на последнем мероприятии, посвящённом Паулю Бернайсу, курс своих лекций я специально построил так, чтобы они подводили к данному моменту.
Эта запись – официальный анонс, подтверждающий данные факты. И если молния уже видна нам, то право озвучить гром принадлежит группе исследователей из Google, как и время и место для этого.
Вместо этого я решил прояснить этот вопрос, разгрести циркулирующую в интернете дезинформацию в своей роли блогера и «общественного интеллектуала», и представить вам «Превосходный набор вопросов и ответов о квантовом превосходстве от Скотта». Просто на случай, если вы вдруг заинтересовались квантовым превосходством, или захотели узнать, что будет, если какая-нибудь компания-поисковик из Маунтин-Вью или откуда-то ещё, гипотетически объявит о достижении квантового превосходства.
Ну, не будем тянуть кота за хвост:
Вопрос 1: что такое квантовое вычислительное превосходство?
Этот термин часто сокращают просто до квантового превосходства (КП). Он обозначает использование квантового компьютера (КК) для решения некоего чётко определённого набора задач, решение которых при помощи известных сегодня алгоритмов на существующих сегодня классических компьютеров займёт на порядки больше времени – и не просто так, а по причине асимптотической квантовой сложности. Упор здесь делается на то, чтобы быть на 100% уверенным в том, что задача решается на КК, и к ней реально нельзя подступиться при помощи классических компьютеров; в идеале, задача должна быть такой, чтобы её уже можно было решить в ближайшее время (при помощи зашумлённых, не универсальных КК, которые уже есть или появятся в скором времени). А если ещё эта задача окажется полезной, тем лучше – но это не обязательно. Самолёт братьев Райт или чикагская поленница сами по себе не были полезными.
В2: Если исследователи из Google и правда достигли КВ, значит ли это, что «любой код можно взломать», как недавно написал у себя в твиттере кандидат в президенты от демократической партии США Эндрю Янг?
Google achieving quantum computing is a huge deal. It means, among many other things, that no code is uncrackable. https://t.co/AghqDAYs66
Неправда (хотя как кандидат, Янг мне симпатичен).
Тут есть две проблемы. Во-первых, устройства, которые сегодня создают Google, IBM и другие, состоят из 50-100 кубитов и не имеют системы исправления ошибок. Для запуска алгоритма Шора для взлома RSA-шифрования потребуется несколько тысяч логических кубитов. А с известными на сегодня методами коррекции ошибок это легко может потребовать миллионов физических кубитов, причём качеством лучше существующих. Не думаю, что кто-либо приблизился к этому, и мы не знаем, сколько времени уйдёт на это.
Во-вторых, даже в гипотетическом будущем, масштабируемые КК с коррекцией ошибок смогут, как нам сегодня кажется, взламывать некоторые коды, но не все. По неудачному совпадению, к тем публичным ключам, что они способны взломать, относятся большая часть ключей, используемых нами сегодня для безопасности в интернете: RSA, протокол Диффи — Хеллмана, эллиптические кривые, и т.д. На шифрование с приватным ключом это окажет минимальное влияние. А ещё есть кандидаты на системы с открытыми ключами (к примеру, на основе решёток), способ взлома которых и за 20 лет попыток на КК никому не известен; кроме того, уже предпринимаются попытки по переходу на такие системы. Подробности – в моём письме к Ребекке Гольдштейн.
В3: Какие вычисления, считающиеся классически сложными, Google планирует проводить, или уже провёл?
Могу сказать, хотя и стесняюсь. Вычисления следующие: «испытатель» генерирует случайный квантовый контур С (случайную последовательность вентилей из 1 кубита и ближайшего к нему второго кубита, глубины около 20, на двумерной решётке из 50-60 кубитов). Затем испытатель отправляет C в квантовый компьютер и даёт ему задание применить контур к изначальному состоянию все-0, измерить результат по базе <0,1>, отправить наблюдаемую строку из n бит, и повторить это несколько тысяч или миллионов раз. Наконец, используя своё знание С, классический испытатель применяет статистический тест, чтобы проверить, что выходные данные подтверждают, что вычисления проводил КК.
То есть, то не задача вроде разложения на множители, имеющая один правильный ответ. Контур С выдаёт распределение вероятности, назовём его DC, по строкам из n бит, а задача состоит в выдаче выборок из этого распределения. На самом деле, в поддержку DC будет говорить 2 n строк — и их будет так много, что если КК работает, как надо, то одни и те же выходные данные мы никогда не увидим. Важно то, что распределение DC неоднородно. Некоторые строки будут испытывать конструктивную интерференцию амплитуд, и их вероятности будут больше, а другие будут страдать от деструктивной интерференции, и их вероятности будут меньше. И хотя мы увидим лишь несколько выборок, количество которых по сравнению с 2 n будет крохотным, мы можем проверить, тяготеют ли они к строкам, вероятность которых мы считаем большей, и в итоге это будет повышать нашу уверенность в том, что происходит нечто классически недостижимое.
Проще говоря, КК просто попросят выполнить случайную (но известную) последовательность операций – не потому, что нам нужен конкретный результат, а потому, что мы пытаемся доказать, что он может опередить классический компьютер в некоей чётко определённой задаче.
В4: Но если КК существует только для того, чтобы выдавать случайный мусор, единственный смысл которого состоит в том, что его сложно симулировать на классическом компьютере, тогда кому до этого есть дело? Разве это не распиаренный бутерброд с ничем?
Нет. Как я уже писал, это не бутерброд со всем сразу, но определённо бутерброд с чем-то!
Я постоянно вспоминаю самолёт братьев Райт потому, что меня поражает пропасть между тем, о чём мы говорим, и пренебрежение, оказываемое в интернете со всех сторон к данной теме. Это похоже на реакцию человека, свято верившего, что полезное путешествие по воздуху осуществить невозможно, а потом увидевшего невзрачный деревянный винтовой самолёт, парящий в воздухе – это зрелище не опровергнет его взгляды, но и не поддержит.
Неужто я не зря волновался все эти годы, что постоянная шумиха по поводу куда как менее значимых вех, достигнутых КК, истощит терпение людей, и им уже будет всё равно, когда случится нечто реально стоящее?
В5: Много лет назад вы стыдили народные массы за то, что они чрезмерно превозносят D-Wave и её заявления по поводу огромного квантового ускорения решения задач оптимизации через квантовый отжиг. Теперь вы стыдите народные массы за то, что они недостаточно сильно восторгаются КП. Почему бы вам не определиться?
Потому что моя цель – не вести «уровень восторженности» в каком-то определённом направлении, а в том, чтобы он был правильным! Разве нельзя сказать, оглядываясь назад, что я в целом был прав по поводу D-Wave, даже когда моя критика этой темы сделала меня непопулярным в некоторых кругах? Вот и по поводу КП я тоже стараюсь оказаться правым.
В6: Если расчёты, связанные с КП, учитывают только выборки из вероятностного распределения, как проверить, что расчёты верны?
Подчеркну, что эта проблема характерна для экспериментов с выборками, похожих на тот, что мы проводим сейчас. Если бы алгоритм Шора разложил на множители число из 2000 цифр, мы бы легко проверили это, просто перемножив полученные множители и проверив их на принадлежность к простым числам. Или, если бы КК использовался для симуляции сложной биомолекулы, мы бы могли проверить его работу в эксперименте.
В7: Погодите-ка. Если классические компьютеры могут проверить результаты эксперимента по КП только в режиме симуляции эксперимента (пусть и медленной), то как это может быть «квантовым превосходством»?
Да ладно вам. С чипом из 53 кубитов вполне логично ожидать ускорения в несколько миллионов раз в режиме, в котором вы всё ещё можете напрямую проверить результат работы, а также увидеть, что ускорение растёт экспоненциально при росте количества кубитов – точно так, как предсказывал асимптотический анализ.
В8: Есть ли математическое доказательство того, что не существует быстрого классического алгоритма, который бы перегнал эксперимент по КП с выборкой?
На сегодня нет. Но в этом нет вины исследователей КП! Специалисты по теоретической информатике неспособны даже доказать простейшие гипотезы, типа P≠NP или P≠PSPACE, поэтому не стоит и надеяться на то, что можно будет однозначно исключить наличие быстрой классической симуляции. Мы можем надеяться только на условную сложность. И мы действительно доказали какие-то из подобных результатов. Самая крупная теоретическая проблема в этой области – доказательство лучших результатов условной сложности.
В9: Имеет ли КП с выборкой само по себе какие-то полезные применения?
Впервые задумавшись об этой теме, люди обычно считали, что очевидный ответ на этот вопрос – «нет» (и я был одним из них). Но в последнее время ситуация поменялась – к примеру, благодаря моему протоколу подтверждённой случайности, который демонстрирует, как эксперимент с КП с выборкой можно очень быстро превратить в генератор битов, случайность которых можно доказать скептически настроенному стороннему наблюдателю (при некоторых вычислительных предположениях). А это может, потенциально, применяться к созданию PoS-криптовалют и других криптографических протоколов. Надеюсь, что в недалёком будущем будет открыто больше подобных применений.
В10: Если эксперименты с КП просто генерируют случайные биты, так ли это интересно? Разве это не тривиальная задача – превратить кубиты в случайные биты, просто измеряя их?
Суть в том, что эксперимент с КП не генерирует однородные случайные биты. Он делает выборку из некоей сложнго коррелирующего распределения вероятности по 50-битным или 60-битным строкам. В моём протоколе подтверждённой случайности отклонения от однородности играют центральную роль в том, как КП может убедить классического скептика в том, что биты в самом деле случайны, и не имеют тайной системы (как генератор псевдослучайных чисел).
В11: А разве десятилетия квантовомеханических экспериментов – к примеру тех, что нарушают неравенства Белла – уже не продемонстрировали КП?
Это просто путаница в терминах. Те эксперименты продемонстрировали другие виды «квантового превосходства». К примеру, в случае нарушения неравенств Белла это было «квантово-корреляционное превосходство». Там не было показано вычислительного превосходства, то есть чего-то, что невозможно симулировать на классическом компьютере (при том, что у классической симуляции не было бы ограничений по пространственной локальности или чего-то подобного). Сегодня люди обычно имеют в виду под КП квантовое вычислительное превосходство.
В12: Ну хорошо, но существует же бесчисленное количество примеров материалов и химических реакций, которые тяжело симулировать классически, а также особые квантовые симуляторы (к примеру у группы Лукина из Гарварда). Почему они не считаются примерами КП?
По некоторым определениям они могут считаться примерами КП! Ключевое отличие работы исследователей из Google в том, что их устройство полностью программируемое – его можно запрограммировать на произвольную последовательность 2-кубитных вентилей с ближайшим соседом, просто отправляя нужные сигналы с квантового компьютера.
Иначе говоря, КП-скептики уже не могут хмыкать, что, дескать если и существуют квантовые системы, которые сложно симулировать классически, то только потому, что природу тяжело симулировать, и мы не можем произвольным образом изменить то, какое случайное химическое соединение мы найдём в природе, поэтому эти системы нельзя считать «компьютерами, симулирующими самих себя». По любому разумному определению, сверхпроводящие устройства, которые сегодня создают в Google, IBM и других компаниях, являются настоящими компьютерами.
В13: Изобрели ли вы концепцию квантового превосходства?
Нет. Я сыграл некую роль в его определении, из-за чего Сабина Хоссенфелдер и другие приписали мне слишком большую роль в этой идее. Термин «квантовое превосходства» придумал Джон Прескилл в 2012 году, хотя в некоторым смысле ключевая концепция датируется началом самих квантовых вычислений в начале 1980-х. В 1994 году использование алгоритма Шора для разложения на множители больших чисел стала по-настоящему экспериментом в области КП – хотя эту задачу и сегодня слишком сложно решить.
Суть идеи, заключавшейся в том, чтобы вместо этого продемонстрировать КП при помощи задачи выборки, насколько мне известно, впервые предложили Барбара Терал и Дэвид Дивинченцо в дальновидной работе 2002 года. «Современные» попытки организации экспериментов начались в 2011 году, когда мы с Алексом Архиповым опубликовали нашу работу по BosonSampling, а Бремнер, Йоза и Шеперд опубликовали свою работу по коммутируемым гамильтонианам. Эти работы показали не только, что «простые», не универсальные квантовые системы могут решать кажущиеся сложными задачи с выборкой, но и что эффективный классический алгоритм для этих задач приведёт к коллапсу полиномиальной иерархии. Мы с Архиповым также сделали первые шаги к доказательству того, что даже приблизительные версии задач с квантовой выборкой могут быть сложными классически.
Насколько мне известно, идея «случайной выборки контуров» – то есть, генерации сложной проблемы выборок через выбор случайных последовательностей вентилей из 2 кубитов в сверхпроводящей архитектуре – появилась в емейл-переписке, которую я начал в декабре 2015 года, и в которой также участвовали Джон Мартинис, Хартмут Нивен, Серджио Бойксо, Эшли Монтанаро, Майкл Бремнер, Ричард Йоза, Арам Хэрроу, Грег Куперберг и др. Переписка называлась «сложная проблема выборки с 40 кубитами», и моё письмо начиналось словами «извините за спам». Я обсудил некоторые преимущества и недостатки трёх вариантов демонстрации КП с выборкой: (1) случайные контуры, (2) коммутируемые гамильтонианы, (3) BosonSampling. После того, как Куперберг встал на защиту первого варианта, среди участников быстро сформировался консенсус, что первый вариант действительно был лучшим с инженерной точки зрения – и что, если существующего теоретического анализа для (1) недостаточно, то мы сможем что-нибудь придумать.
После этого группа из Google провела огромное количество анализов выборок случайных контуров, как теоретических, так и численных, а мы с Лицзе Чэнем, а также Буланд с коллегами представляли доказательства различного вида для классической сложности задачи.
В14: Если КП достигнуто, что это будет означать для скептиков?
Мне бы не хотелось быть на их месте! Они могут отойти на позицию, по которой КП возможно (а кто говорил, что оно невозможно? Уж точно не они!), и что реальной проблемой всегда была квантовая коррекция ошибок. И многие из них действительно поддерживали именно эту позицию. Но другие, включая моего друга Гила Калая, прямо здесь, в блоге, под запись, утверждали, что КП невозможно достичь по фундаментальным причинам. И я уже не позволю им выкрутиться.
Достижение КП означает, что у группы Google уже есть оборудование, необходимое для демонстрации моего протокола генерации подтверждённых случайных битов. И это действительно одна из первых вещей, которые мы планируем сделать.
Следующей очевидной вехой будет использование программируемого КК с 50-100 кубитами для полезных квантовых симуляций (допустим, системы конденсированного состояния), работающих быстрее любых известных классических методов. Второй очевидной вехой будет демонстрация использования квантовой коррекции ошибок, чтобы закодированный кубит жил дольше лежащих в его основе физических кубитов. Нет сомнений в том, что Google, IBM и другие игроки будут наперегонки стремиться к обеим этим вехам.
После публикации статьи Стив Гирвин напомнил мне, что группа из Йеля уже достигла квантовой коррекции ошибок, хотя и в бозонной системе, а не в системе сверхпрвоодящих кубитов. Так что, возможно, следующую веху лучше сформулировать так: достижение квантового вычислительного превосходства и полезной квантовой коррекции ошибок в одной системе.