Скоро ли ученые добьются квантового превосходства и для чего оно нужно

Надежды на светлое квантовое будущее пока остаются надеждами: пригодный для решения практических задач универсальный квантовый компьютер еще не создан. Однако есть второй путь — создание специализированных квантовых вычислительных устройств, которые могут решать определенный тип задач, но делают это так, что никакой «обычный» компьютер будет не в силах за ними угнаться. Перспективы создания таких машин и их преимущества обсуждали в Москве на конференции «Сверхпроводниковые квантовые технологии», организованной НИТУ «МИСиС», МФТИ и Российским квантовым центром. Редакция N + 1поговорила о возможностях и будущем квантовых симуляторов с Павлом Буныком, главным конструктором архитектуры процессоров компании D-wave.

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

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

В частности, задача коммивояжера, которая представляет собой формализованный вариант задачи с грузовиками, решается на классическом компьютере простейшим перебором за n! шагов, где n— число вершин, которые нужно обойти. Например, чтобы найти оптимальный маршрут между 15 городами-миллионниками России, понадобится перебрать 15! — более 1,3 триллиона — вариантов. Квантовый алгоритм Гровера позволяет решить эту задачу уже за ?n! шагов, то есть дает практически квадратичный прирост по времени. Конечно, существуют и более быстрые классические алгоритмы (например, алгоритм Хелда-Карпа), однако их аналоги для квантовых компьютеров тоже работают быстрее. Поэтому сейчас квантовые компьютеры находятся впереди, хотя бы теоретически.

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

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

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

Грубо говоря, если вспомнить, что такое классы сложности, то алгоритм, который может проверить оптимальное решение, принадлежит к классу P, а алгоритм, который подсчитывает число оптимальных решений, лежит в классе #P. Считается, что задачи из класса #P являются исключительно сложными, но решать их за короткое время было бы очень интересно. Конечно, мы не гарантируем, что наш компьютер может быстро дать все решения. Мы говорим, что он старается найти как можно больше разнообразных, наиболее интересных ответов.

На ваших устройствах был успешно реализован алгоритм квантового отжига. Можете рассказать, как работает этот алгоритм?

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

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

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

Например, предположим, что я один из таких кубитов. Я смотрю на соседа слева, знаю, что нас запрограммировали так, чтобы мы находились в разногласии (то есть наши спины смотрели бы в противоположных направлениях), и пытаюсь под него подстроиться. Потом смотрю на соседа справа — вижу, что нас запрограммировали так, что мы с ним должны быть в согласии. Решаю, в какую сторону мне будет выгоднее повернуться, если бы я был классической частицей. Как должны взаимодействовать мои соседи, я уже не знаю. В результате кубиты постепенно перестраиваются, в какой-то момент энергия запрограммированной задачи становится примерно равной энергии квантово-механических взаимодействий, и в этот момент все кубиты одновременно решают, в каком направлении им выгоднее всего остаться. После этого решение все больше затвердевает, и конечный ответ получается чисто классический — каждый спин смотрит либо вверх, либо вниз. Эти состояния уже можно однозначно измерить, это итоговый результат «отжига». Конечно, с этим состоянием можно сделать что-то еще — например, проверить и повернуть некоторые спины, если в ходе отжига возникли ошибки.

Кубиты — логические элементы квантового компьютера; основное свойство кубита — способность находиться одновременно в суперпозиции (смеси) двух состояний, словно кот Шредингера. Реализовать кубиты на практике можно большим числом различных способов — конденсировать облака холодных атомов и следить за их спинами, управлять квантовыми точками в полупроводниках, оперировать запутанными фотонами и так далее. Квантовые компьютера компании D-wave работают со сверхпроводящими потоковыми кубитами на основе эффекта Джозефсона. Заключается этот эффект в том, что если соединить два сверхпроводника тонким слоем изолятора, то куперовские пары будут туннелировать через него, и в результате через соединение потечет сверхпроводящий ток. Такое соединение называют джозефсоновским переходом. Соединяя джозефсоновские переходы в кольцо, можно построить прибор, который находится в одном из двух квантовых состояний: одному состоянию отвечает движение электрического тока по часовой стрелке, другому состоянию — движение против. Собственно, именно из таких кубитов построены квантовые компьютеры D-wave.

В 2015 году компания Google сообщила, что компьютер D-waveпревзошел классический компьютер в сто миллионов раз на специально подобранной задаче квантового отжига. Можно ли считать этот результат доказательством квантового превосходства?

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

С другой стороны, если знать структуру задачи заранее, то превосходства добиться гораздо сложнее. Существуют классические алгоритмы, которые знают структуру задачи и могут ею пользоваться. Например, простой перебор в уже упоминавшейся задаче коммивояжера работает за время O(n!), а алгоритм Хелда-Карпа — за O(n2 ? 2n). Это сокращает разницу, может, до тысячи или ста раз в нашу пользу или вообще ее убирает. На этом уровне нам такой выигрыш уже не интересен.

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

То есть это была демонстрация того, что если кто-то кому-то принес в клювике конкретную задачу и на нее натравили компьютер D-wave, то он дает ответ в сто миллионов раз быстрее, чем «неподготовленный» классический компьютер. Google хотел показать, что эта вещь работает. И у него получилось, с учетом тех оговорок, что если знать, как «сломать» наш компьютер, то сломать его можно. Следующую версию «сломать» будет уже гораздо сложнее. Пока никто не придумал, как. Может быть, придумают потом.

А насколько велик спрос на квантовые симуляторы? Сколько компьютеров вы уже продали?

Пока что не очень много, штуки 3-4. И потом тем же покупателям продали апгрейды, тоже штуки 3-4. Google/NASA/USRA, Lockheed Martin/USC, Лос-Аламос, Окридж. Надеюсь, никого не забыл, потому что я делаю чипы, а не обслуживаю их.

Нужно еще понимать, что сейчас наши компьютеры — это, скорее, своеобразные тренировочные «игрушки», чем гарантированно полезный с практической точки зрения инструмент. Все наши покупатели используют их для того, чтобы выяснить, насколько они могут давать им что-то новое. Такое, что вот они придумали, запустили, а потом посмотрели на результат и сказали: «Ага! Как интересно». Если бы Google был бы нужен конкретный ответ на конкретный вопрос, то он бы воспользовался своими классическими вычислительными ресурсами, которые превосходят по вычислительной мощности многие другие известные вычислители. Но им интересно посмотреть, почему эта штука вдруг через десять миллисекунд отвечает на их вопрос, причем дает настолько хороший ответ, что они говорят «Ага!»

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

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

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

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

Какой будет следующая версия вашего компьютера?

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

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

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

У универсальных квантовых компьютеров есть одно достоинство, которое одновременно является большой проблемой. Такие компьютеры могут решить задачу, которая, насколько известно современной математике, классические компьютеры решить не могут. А именно — разложить большие числа на простые множители с помощью алгоритма Шора. На невозможности решения этой задачи основаны все более-менее современные средства шифрования. Если бы у нас был универсальный квантовый компьютер, на котором можно реализовать алгоритм Шора, то ваша связь с банком была бы гораздо менее надежной. Именно поэтому государственные службы разных стран очень много вкладывали денег именно в универсальный квантовый компьютер. Хотя бы для того, чтобы проверить, могут ли его сделать конкуренты.

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

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

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

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

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

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

Поэтому никто пока еще не может взломать существующие средства шифрования с помощью квантового компьютера. Конечно, маленькие числа, например 15 или 143, и сейчас раскладывают. По-моему, рекорд сейчас составляет 175. Без алгоритма Шора, на наших адиабатических компьютерах, мы раскладывали 5- и 6-значные числа. Однако чтобы разложить на множители числа, которые использовались для защиты банковской информации в 1990-х годах, то есть 256-битные ключи, нужен миллион кубитов. Более того, с тех пор классические компьютеры улучшились еще больше, и все пользуются не 256- и даже не 512-битными ключами, а 1024 или 2048-битными. Соответственно, для взлома этих ключей нужно еще больше кубитов. С точки зрения теоретика задача решена. Однако с точки зрения практики до этого еще далеко.

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

Какие практические задачи компьютеры D-wave уже решают?

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

Вторая статья немного более экзотическая. Она уже выложенана arXiv.org и посвящена моделированию экзотических топологических фаз материи. За теоретические исследования таких систем Майклу Костерлицу и Дэвиду Таулессу в 2016 году дали Нобелевскую премию по физике, а мы эти системы промоделировали. Это чисто квантово-механический эффект. И ничего, наш процессор вполне даже говорит — здесь происходит так, а здесь по-другому.

То есть опять же, это еще не дошло до уровня «чтобы улучшить производство аммиачного удобрения на 25 процентов, делай так». Но это на пути к нему. И для меня лично это гораздо приятнее, чем возможность взломать переписку и прочитать e-mail того или иного политика.

Можно ли использовать ваши компьютеры для создания искусственного интеллекта?

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

Более того, недавно в D-wave было создано новое подразделение, которое работает с нейронными сетями, адаптирует их для квантовых вычислений. Люди, которые этим занимаются, говорят, что от такой адаптации должен быть выигрыш. При маленьком количестве «чистых» (правильных) данных на большое количество «грязных» данных ребята из нового подразделения делают выводы, которые впечатляют экспертов в этой области. Опять же, работа ведется в надежде, что когда-нибудь все это присоединится к действительно большому процессору, и тогда это будет не просто «Хм, интересно», а «Ого!»

Беседовал Дмитрий Трунин

Источник: nplus1.ru

Комментарии: