В поисках количественной оценки квантовости

Что делает квантовый компьютер мощнее классического? Это удивительно тонкий вопрос, над которым физики бьются уже несколько десятилетий, спустя десятилетия после начала квантовой эпохи. Комментарий Сохранить статью Прочитать позже

Введение

Прошло более 40 лет с тех пор, как физик Ричард Фейнман указал, что создание вычислительных устройств, основанных на квантовых принципах, может раскрыть возможности, значительно превосходящие возможности «классических» компьютеров. В своей программной речи 1981 года, которую часто считают основоположником квантовых вычислений, Фейнман завершил её знаменитой шуткой:

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

Прошло почти 30 лет с тех пор, как математик Питер Шор предложил первое потенциально революционное применение квантовых компьютеров. Безопасность цифрового мира во многом основана на предположении, что разложение больших чисел на множители — сложная и трудоёмкая задача. Шор показал, как использовать кубиты — квантовые объекты, которые могут существовать в виде смесей 0 и 1, — чтобы сделать это в мгновение ока, по крайней мере, относительно известных классических методов.

Исследователи вполне уверены (хотя и не полностью уверены), что квантовый алгоритм Шора превосходит все классические алгоритмы, поскольку, несмотря на огромные стимулы, никому не удавалось взломать современное шифрование с помощью классической машины. Но для задач менее гламурных, чем факторизация, сложно сказать наверняка, превосходят ли квантовые методы. Поиск новых новаторских приложений превратился в своего рода бессистемную игру в догадки.

«Это глупый подход», — сказала Кристал Ноэль, физик из Университета Дьюка.

В течение последних 20 лет свободная конфедерация физиков и математиков, интересующихся физикой, стремилась более чётко определить мощь квантового мира. Их цель? Найти способ количественной оценки квантовости. Они мечтают о числе, которое можно присвоить последовательности кубитов, полученной в результате квантового вычисления. Если это число мало, то это вычисление легко смоделировать на ноутбуке. Если оно велико, то кубиты представляют собой ответ на действительно сложную задачу, выходящую за рамки любого классического устройства.

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

«Именно здесь начинается квантовость в сверхстрогом смысле», — сказал Билл Фефферман, исследователь квантовой физики из Чикагского университета.

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

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

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

Запутанность

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

«О запутанности заговорили очень быстро, — сказал Ричард Йожа, математик из Кембриджского университета. — И все просто решили, что на этом всё и заканчивается».

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

Запутанность, явление, при котором две квантовые частицы образуют общее состояние, воплощает в себе то, что было сложным в квантовой механике — и, следовательно, то, в чем квантовые компьютеры могли бы преуспеть. Когда частицы не запутаны, вы можете отслеживать их по отдельности. Но когда частицы становятся запутанными, изменение или манипулирование одной частицей в системе требует учета ее связей с другими запутанными частицами. Эта задача растет экспоненциально по мере добавления новых частиц. Чтобы полностью определить состояние n запутанных кубитов, вам нужно что-то вроде 2n классических битов; чтобы вычислить эффект настройки одного кубита, вам нужно выполнить около 2n классических операций. Для трех кубитов это всего восемь шагов. Но для 10 кубитов это 1024 — математическое определение быстро возрастающих вещей.

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

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

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

Сегодня запутанность остаётся наиболее изученным квантовым ресурсом. «Если спросить 99 из 100 физиков, [что делает квантовые схемы такими мощными], первое, что придёт им в голову, — это запутанность», — сказал Фефферман.

Продолжаются активные исследования связи запутанности со сложностью. Например, Фефферман и его коллеги в прошлом году показали, что для одного конкретного класса квантовых цепей запутанность полностью определяет сложность их классического моделирования. «Как только вы достигаете определённого уровня запутанности, — сказал Фефферман, — вы фактически можете доказать сложность. Не существует [классического] алгоритма, который бы работал».

Но доказательство Феффермана справедливо только для одного типа цепей. И ещё 20 лет назад исследователи понимали, что одной лишь запутанности недостаточно, чтобы охватить всё богатство квантового океана.

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

Оказалось, что поиски квантовости только начинались.

 Немного магии

Йожа знал, что запутанность — не последнее слово в квантовости, поскольку за четыре года до его работы физик Дэниел Готтесман доказал обратное. На конференции 1998 года в Тасмании Готтесман объяснил, что в определённом типе квантовой схемы, казалось бы, квинтэссенция квантовой величины становится пустяком для моделирования классическим компьютером.

В методе Готтесмана (который он обсуждал с математиком Эмануэлем Книллом) операция запутывания практически ничего не стоила. Можно было запутать сколько угодно кубитов, и классический компьютер всё равно справлялся.

«Это был один из первых сюрпризов — теорема Готтесмана-Книла — в 90-х годах», — сказал Корзеква.

Возможность классического моделирования запутанности казалась чудом, но была одна загвоздка. Алгоритм Готтесмана-Нилла не мог справиться со всеми квантовыми цепями, а только с теми, которые были связаны с так называемыми вентилями Клиффорда. Но если добавить «T-вентиль» — на первый взгляд безобидное устройство, вращающее кубит определённым образом, — программа просто захлебнётся.

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

В 2004 году Сергей Бравый, работавший тогда в Институте теоретической физики им. Ландау в России, и Алексей Китаев из Калифорнийского технологического института разработали две схемы для выполнения любых квантовых вычислений: можно было включить T-вентили в саму схему. Или можно было взять «магическое состояние» кубитов, подготовленное с помощью T-вентилей другой схемой, и передать его в схему Клиффорда. В любом случае, магия была необходима для достижения полной квантовости.

Десять лет спустя Брави и Дэвид Госсет, исследователь из Университета Ватерлоо в Канаде, разработали способ измерения количества магии в наборе кубитов. А в 2016 году они разработали классический алгоритм для моделирования схем с низким уровнем магии. Их программа работала экспоненциально дольше с каждым дополнительным вентилем T, хотя экспоненциальный рост не был таким взрывным, как в других случаях. Наконец, они продемонстрировали эффективность своего метода, проведя классическое моделирование довольно магической схемы с сотнями вентилей Клиффорда и почти 50 вентилями T.

Сегодня многие исследователи используют квантовые компьютеры в режиме Клиффорда (или близком к нему), именно потому, что они могут использовать классический компьютер для проверки корректности работы неисправных устройств. Схема Клиффорда «настолько важна для квантовых вычислений, что её трудно переоценить», — сказал Госсет.

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

В 2021 году исследователи выявили определённые фазы квантовой материи, которые гарантированно обладают магией, подобно тому, как многие фазы материи обладают определёнными паттернами запутанности. «Для получения полного ландшафта фаз материи нужны более тонкие измерения вычислительной сложности, например, магии», — сказал Тимоти Хсие, физик из Института теоретической физики «Периметр», работавший над этим результатом. А Алиошия Хамма из Неаполитанского университета вместе со своими коллегами недавно исследовал, возможно ли — теоретически — реконструировать страницы дневника, поглощённого чёрной дырой, наблюдая исключительно за её излучением. Ответ был «да», сказал Хамма, «если чёрная дыра не слишком магическая».

Для многих физиков, включая Хамму, физические составляющие, необходимые для создания системы с экстремально квантовым характером, кажутся очевидными. Вероятно, необходимо сочетание запутанности и магии. Ни одна из них по отдельности недостаточна. Если состояние имеет нулевую оценку по любой из метрик, вы можете смоделировать его на ноутбуке, воспользовавшись помощью либо Йожи (если запутанность равна нулю), либо Брави и Госсета (если магия равна нулю).

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

Фермионная магия

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

В 2001 году специалист по информатике Лесли Валиант открыл способ моделирования третьего семейства квантовых задач. Подобно тому, как метод Йожи был ориентирован на схемы без запутывающих вентилей, а алгоритм Брави-Госсета позволял строить схемы без слишком большого количества T-вентилей, алгоритм Валианта был ограничен схемами, в которых отсутствовал «перестановочный вентиль» — операция, при которой два кубита меняются местами.

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

«Это было довольно странно», — сказал Йожа. «Как простая замена двух кубитов может дать такую мощь?»

Всего за несколько месяцев физики-теоретики Барбара Терхал и Дэвид ДиВинченцо раскрыли источник этой силы. Они показали, что схемы Valiant без перестановочных вентилей, известные как схемы со спичечными вентилями, тайно моделируют известный класс физических задач. Подобно тому, как компьютеры моделируют растущие галактики или ядерные реакции (не будучи ни галактикой, ни ядерной реакцией), схемы со спичечными вентилями моделируют группу фермионов — семейство элементарных частиц, содержащих электроны.

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

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

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

Всё изменилось прошлым летом. Три группы исследователей независимо друг от друга привлекли к решению этой проблемы работы Брави, Госсета и их коллег — удачное пересечение исследований, которое, по крайней мере в одном случае, было обнаружено, когда за чашкой кофе всплыли фермионы (как это часто случается, когда физики собираются вместе).

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

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

«У нас не было интуиции. Нам пришлось начинать с нуля», — сказал Стрельчук.

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

Результатом стал своего рода словарь для переноса классических алгоритмов моделирования из мира Клиффорда в мир матчгейта. «Практически всё, что у них есть для схем [Клиффорда], теперь можно перевести», — сказала Беатрис Диас, физик из Мюнхенского технического университета, — «так что нам не придётся изобретать все эти алгоритмы заново».

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

Оливер Рирдон-Смит, работавший с Коржеквой и Михалом Ошманцем из Польской академии наук в Варшаве, подсчитал, что их программа способна моделировать схему с 10 дорогостоящими перестановочными вентилями в 3 миллиона раз быстрее, чем предыдущие методы. Их алгоритм позволяет классическим компьютерам немного глубже проникнуть в квантовое море, одновременно расширяя нашу способность подтверждать производительность квантовых компьютеров и область, в которой не могут существовать ни одно революционное квантовое приложение.

«Моделирование квантовых компьютеров полезно многим, — сказал Рирдон-Смит. — Мы хотим сделать это как можно быстрее и дешевле».

Что касается того, как назвать ресурс «интерактивности», создаваемый обменными шлюзами, то у него до сих пор нет официального названия; некоторые называют его просто магией, а другие бросаются импровизированными терминами вроде «нефермионная штука». Стрельчук предпочитает «фермионную магию».

Дальнейшие острова на горизонте

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

«В конечном итоге [изучение классического моделирования] помогает нам понять, где можно найти квантовое преимущество», — сказал Госсет.

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

«Не думаю, что этот вопрос имеет смысл, — сказал Йожа. — Нет такой вещи, в которую можно вложить больше, чтобы получить больше силы».

Скорее, три квантовых ресурса, по-видимому, являются артефактами математических языков, используемых для того, чтобы втиснуть сложность квантовости в более простые рамки. Запутанность становится ресурсом, когда вы практикуете квантовую механику так, как это описал Шредингер, используя его одноимённое уравнение для предсказания изменения волновой функции частицы в будущем. Это хрестоматийная версия квантовой механики, но не единственная.

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

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

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

Десятилетия назад казалось, что ответ на вопрос о том, что делает систему квантовой, очевиден. Сегодня исследователи знают это лучше. После 20 лет исследований первых классических островов многие подозревают, что их путешествие может никогда не закончиться. Даже продолжая совершенствовать своё понимание того, где квантовая энергия отсутствует, они понимают, что, возможно, никогда не смогут точно сказать, где она находится.

Источник: www.quantamagazine.org