7.6. Будущее квантовых вычислений. Квантовое превосходство или преимущество: IBM vs Google vs КНР

И как заявил

Google, что они.

Исследователи из Гугла заявили, что
они достигли немного большего,

чем год назад.

Ими достигнуто знаменитое
квантовое превосходство.

Что именно они сделали, чтобы
продемонстрировать

это квантовое преимущество, квантовое
превосходство?

Они не выполняли алгоритмы

Гровера или Шора, или иные
из уже изученных нами.

Они использовали квантовый компьютер

для запуска схем. Именно это и делает
квантовый компьютер,

основанный на модели квантовых вентилей,

он запускает

вентили

на кубитах, а затем измеряет
результаты.

Так что они подумали: «Давайте-ка используем

квантовый компьютер для выполнения
случайных схем,

и потом проверим, сопоставимо ли то,
что мы получаем,

с тем, что мы в теории ожидаем получить».

И существует много теоретических
предположений

относительно результатов,
которые можно получить

при запуске случайных схем.

Проблема или

преимущество перед классическими
вычислениями

здесь заключается в том, что мы не знаем,
насколько

эффективно квантовые компьютеры

эмулируются с помощью классических.

Имея случайную схему, мы не знаем,

насколько эффективно запустить эту схему
на классическом компьютере.

Это то, что

мы делаем и, фактически, есть несколько
разных экспериментов,

доказанных математически.

Например, работа Аронсона и Чена,

доказывающая,

что задача

моделирования

квантовых схем на классическом оборудовании

невозможна, если только

не исчезает полиномиальная
иерархия, что очень

похоже на открытие равенства Р и NP,

а это – очень маловероятно,

и это не одно и то же, но имеет отношение
к данной идее.

Мы не ожидаем, что это утверждение верно.

Извините, есть

вопрос от Ричарда Политки: «Я думал,
что "превосходство" используется для

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

в соответствии с теорией и практикой задач,

а "преимущество" означает
значительно быстрее».

Да, вы правы, в литературе

«преимущество» иногда употребляется
только

как более слабая версия «превосходства»,

но проблема в том, что термин «превосходства»
так идеологически заряжен, что некоторые

выступают за то,

чтобы вообще

отказаться от «превосходства» и использовать
«преимущество» или что-то вроде него.

А некоторые утверждают,
как вы и сказали, что

«превосходство» намного сильнее, чем

«преимущество» и передаёт иной смысл.

Но в некоторых

контекстах термин «преимущество» используется как

синоним «превосходства», а в других,
как вы и говорите,

как обозначение чего-то послабее.

В общем, с этой терминологией
есть определённые проблемы.

Но вы правы.

Итак, как я говорил, Гугл
запустил эти схемы,

И было доказано, что мы не рассчитываем,

что сможем найти классический алгоритм,
который бы эффективно

исполнялся в задаче случайных схемы,

и убедиться, что они действительно
выбраны из заданного

распределения, которое у нас было бы
на идеально

работающем квантовом компьютере.

Так что

при проектировании эксперимента нужно быть
осторожным, потому что

в некоторых ситуациях, хотя в общем

мы не знаем, как моделировать

квантовые схемы

с помощью классического компьютера,

в некоторых ситуациях у нас есть

эффективные алгоритмы для моделирования

квантовых схем даже с большим
количеством кубитов.

Например, одна из ситуаций, в которой
это можно сделать,

разумеется, когда у вас

множество кубитов,

но запутаны между собой только
блоки кубитов.

Представьте, что у вас есть

5 000 кубитов,

но кубиты запутаны

только между собой, только пары

кубитов запутаны, а этот блок не запутан
с двумя другими кубитами и

не запутан с другим кубитом, так что вы
можете просто разделить блоки,

которые не запутаны.

Можно реализовать каждую из этих схем
отдельно,

и затем

получить

идеальную симуляцию схемы путем запуска этих
маленьких схем и сложения результатов.

Так что нужно запутывание.
Нужно запутывание

между всеми кубитами

в схеме.

И поэтому

в случае схем, запущенных

Гуглом, они использовали контрольные
операции Z, сначала

в горизонтальном направлении, затем
в вертикальном.

Таким образом, через несколько слоев

они запутали все кубиты между собой.

Все они были запутаны во всей схеме.

Здесь также можно увидеть вентили Адамара,
некоторые

вентили вращения на T-вентилях, но

важно отметить, что

запутывание

быстро распространяется по всей схеме,
потому что без этого

можно легко смоделировать каждую часть схемы
отдельно, а затем сложить результаты.

Так что запутывание необходимо.

Но запутывание – не единственный ингредиент,
который вам нужен, чтобы получить

то, что трудно смоделировать
на обычных машинах.

Потому что получен выдающийся результат,

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

формализм, о котором я рассказывал.

Это одно из моих любимых достижений в квантовых

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

как

много значит представление информации, когда
вы пытаетесь смоделировать квантовые схемы.

Итак, теорема Готтесмана – Нилла
утверждает, что

если в схеме есть только вентили

из набора: вентиль Адамара, Вентиль НЕ,
вентиль CNOT и S-вентиль,

и сочетания этих вентилей, например,
если скомбинировать эти вентили,

можно получить

вентиль Z, вентиль Y и другие вентили,

но если есть только эти вентили,

то можно смоделировать

схему с помощью классического компьютера
весьма эффективно.

И трюк здесь в том, чтобы
представить состояния

не с помощью векторов состояния,
которым нужно

экспоненциальное количество амплитуд,

а с помощью представления стабилизационного
формализма.

Каждое состояние может быть

задано, каждое из состояний, которое вы
достигаете применением этих вентилей,

может быть уникально определено

полиномиальным числом

стабилизаторов, операций этих

тензорных произведений Паули,

и затем вы работаете с этим
представлением.

И удивительно, что даже если
состояние очень запутанное,

через минуту я покажу вам пример,

то можно смоделировать схему
классическим образом.

Так что с этим нужно быть осторожным,
нужно включить, например,

Т-вентиль сюда.

Обратите внимание также, что

здесь вы заменяете S-вентиль на Т-вентиль,
и у вас получается

универсальное вычисление.

А универсальное вычисление, квантовое
универсальное вычисление,

как мы считаем,

мы не сможем смоделировать по классике.

Так что простая замена S-вентиля
на Т-вентиль

переносит вас из мира эмуляций на
классических машинах в мир,

где больше невозможно сделать эмуляцию,

или, мы так думаем, что мы не можем сделать
эмуляцию на обычных компьютерах.

Итак, при условии, что вы построили
эти схемы данным способом,

получаются вот такие

теоретические результаты, показывающие,
что выбор из

полученного распределения, распределения
результатов, строк,

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

соответствует определенному теоретическому
распределению,

относящемуся к так называемому
распределению Портера–Томаса.

Сделать выборку из этого

распределения с помощью классического
алгоритма очень сложно.

Действительно, можно доказать,

что есть

измерение, называемое перекрестной
энтропией,

которая

либо

при

идеальной эмуляции

квантовых схем

должна дать «1»,

либо в равномерном распределении,

вместо реального распределения строк,
полученных из случайных схем,

должно дать вам «0».

То есть это способ

измерения, независимо от того,

моделируете ли вы

схемы

квантовым способом или делаете
что-то весьма далёкое

от этого, что ожидаете от симуляции схемы.

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

и если она близка к «единице»,

то у вас всё хорошо, а если близка к «нулю»,

то вы не делаете ничего квантового,
вы не моделируете схему.

И можно доказать, что даже небольшое
преимущество

над получением значения перекрестной
энтропии «0»

является признаком того, что вы делаете
что-то в квантовом пространстве.

И что классический алгоритм вам
не подойдет.

И именно

это

сотрудники, исследователи из Гугл сделали.

Вы видите здесь, что перекрестная энтропия

снижается с количеством кубитов

и с количеством циклов, которое равно
количеству слоёв

различных вентилей, однокубитных
и двухкубитных вентилей,

но они доказали, что даже

в случае

33 кубитов, которые они использовали,

они получили перекрестную энтропию,
близкую по их оценке к «нулю»,

но на несколько сигм выше «нуля».

А это – признак квантового превосходства.

Мы не ожидаем такого результата

от квантового компьютера, и действительно,

по их оценкам, классическому компьютеру
понадобилось бы

несколько десятков тысяч лет,
чтобы сделать то,

что они сделали на квантовых компьютерах
за 300 секунд.

Статью достаточно легко читать.

Я разместил ссылку также

на другую статью,

объясняющую идею перекрестной энтропии,

распределения Портера–Томаса и т.п.,

и мне кажется, что если вам это интересно,

вы можете их прочитать и понять многое
из того, что происходит в наши дни.

Но я хотел бы также упомянуть

о вызове, который IBM бросил

квантовому превосходству,
достигнутому в Гугл.

Они заявили, что цифра в 10 000

лет,

указанная Гугл в статье, некорректна.

Можно смоделировать

схемы, которые они выполняли,
классическим способом

с помощью значительно более
быстрого алгоритма.

И они

вычислили прогноз времени, которое

понадобилось бы для выполнения
этим алгоритмом той же задачи,

что и у Гугла,

на их компьютере.

И показали, что, например,

с 53 кубитами и глубиной

в 35 или 30 с чем-то слоёв,

можно смоделировать её решение

не за 10 000 лет, а примерно за 6 дней.

Это намного больше,

чем 300 секунд или 3 минуты или сколько там
понадобилось Гуглу.

Но это значительно меньше, чем 10 000 лет.
Вокруг этого шло много споров.

И я хочу заметить, что, конечно,
тем не менее,

преимущество, если даже не превосходство,

квантового компьютера – очевидно.

300 секунд или

5 минут или сколько там было, против
шести дней.

Также обратите внимание, что

исследователи из IBM

спрогнозировали, что им понадобится

для ещё одного кубита,
и вы видите, что

рост здесь экспоненциальный.
Я имею в виду, что

для 53 кубитов

нужно примерно в два раза меньше, чем для

50–54. И то же самое верно и для
другого количества слоев.

Так что очевидно, что если вам нужно
добавить кубит,

необходимое время умножается на два.

Так что рост экспоненциальный.

Так что даже с алгоритмом,
предложенным IBM,

если вместо

53 кубитов вам понадобится 73,

то необходимое время увеличивается
на два 2 в двадцатой степени,

то есть более чем в 1 миллион раз.
Так что ещё раз,

если исследователи из Гугл или другие могут
воспроизвести ту же задачу,

но с большим количеством кубитов,
то даже с этим алгоритмом

это невозможно сделать классическим
способом.

Итак,

с таким прогнозом от IBM,
какой алгоритм они

предлагают использовать?

Ну, идея заключается в том, что

если вы попытаетесь смоделировать схему

с помощью вектора состояния, вам понадобится
от 2 до 53 амплитуд,

и вы не сможете сделать этого в RAM,

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

Но

это возможно

на жестком диске.

Это возможно на большом дисковом
пространстве.

То есть, вы можете использовать
этот вектор состояния,

получить доступ к вектору состояния,

но с намного большей памятью.

Итак, IBM предложили брать огромное
дисковое пространство и

работать непосредственно
с вектором состояния,

потому что алгоритм, которым
пользуется Гугл

для оценки в эти 10 000 лет,

называется эмуляцией схемы в
полиномиальном пространстве.

Итак, вам не нужны

все амплитуды одновременно,

но нужно сделать намного больше операций,

потому что вы, по сути, рассматриваете
возможность наличия вентилей,

которые вызывают бифуркацию
в дереве вычислений.

Например, если у вас вентиль Адамара,
то есть суперпозиция.

А если схема вроде этой, то

количество ветвей, по которым
вам надо пройти,

начинает расти по экспоненте.

То есть, идея в том, что для того, чтобы

использовать вектор состояния, вам нужны
амплитуды всех этих вероятностей.

Если вы не можете работать со всеми этими
разными вероятностями,

вы можете идти по каждой из этих

веток, по одной за другой. Затем

возвращаться,

отсматривая собственные шаги, и затем
идти по следующей ветке.

И вы можете делать это в полиномиальном
пространстве,

так что вам не нужны все амплитуды
одновременно,

но это занимает намного больше времени.

Но IBM решили: «Хорошо, если у нас
много дискового пространства,

мы всё равно можем работать

с целым состоянием».

В общем, тут возникли разногласия.

Я хочу сейчас увеличить темп, так как
у нас заканчивается время.

Некоторые спрашивают меня
о новых заявлениях

о квантовом превосходстве, или,

в данном случае, используется слово
«преимущество», но

в смысле «превосходства», достигнутого
несколькими учеными в разных

университетах и исследовательских
институтах в Китае.

В данном случае

они используют другой подход.

Они используют не программу, не универсальный
квантовый компьютер, как это сделали

в Гугл, а так называемую фотонную

реализацию бозонного сэмплинга.

И что же такое бозонный сэмплинг? Ну,

в этой задаче бозонного сэмплинга,
предложенной в 2011 году

Аронсоном и Архиповым

как способ доказательства квантового
превосходства,

есть сеть линейных оптических устройств,

таких как расщепители пучка,
зеркала и тому подобных,

и вы подаете некоторое количество фотонов

на вход

сети, линейной

оптической сети, а затем

измеряете, у вас есть детекторы,
детекторы фотонов

на противоположном конце сети.

И вы

обнаруживаете, детекторы обнаруживают
фотоны в каких-то местах.

Конечно,

это является квантовой эволюцией

различных суперпозиций вероятностей
для фотонов,

так что ваши измерения вероятностные.

И было доказано, что

выборка из этого распределения

на практике сложна, трудна для
классических компьютеров,

потому что связана с так называемым

вычислением постоянной в матрице.

Конечно,

работа линейного

оптического устройства

может быть описана унитарной матрицей.

И далее,

чтобы увидеть различные вероятности, которые
можно получить для детекторов

в зависимости от фотонов на входе,

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

И эти разные пути

связаны

с рядами

и столбцами унитарной матрицы

и влекут за собой вычисление
так называемой постоянной,

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

Её оценка, или эффективное её вычисление

приведет к исчезновению полиномиальной
иерархии.

Итак, именно это и сделали эти
исследователи, выборку

этих распределений с помощью

реализации случайной сети этих

фотонных устройств,

и получили

результаты, близкие к

теоретическому распределению.

Проблема здесь в том, что они не использовали
непосредственно этот бозонный сэмплинг,

но использовали другую

версию, с другим типом входа, который
называется сжатым состоянием,

и так называемым гауссовым отбором.

И теперь, после публикации статьи,
была поднята проблема того, что

для этой гауссовой версии, гауссового
бозонного сэмплинга

теоретические результаты отличаются от тех,

которые получены для простого
бозонного сэмплинга.

Так что есть некая трудность в том,

возможно ли эмулировать или провести отбор
из этого распределения

с помощью классического алгоритма.

В этой области всё ещё происходят
новые открытия.