Поразительное новое доказательство сложности квантовых вычислений лучше всего можно понять с помощью игривого мысленного эксперимента. Наберите ванну, а затем бросьте в воду кучу плавающих стержневых магнитов. Каждый магнит будет менять свою ориентацию вперед и назад, пытаясь выровняться со своими соседями. Он будет толкать и тянуть другие магниты, а в ответ будет толкаться и тянуться. А теперь попробуйте ответить на этот вопрос: каким будет окончательное устройство системы?
Эта и подобные ей задачи, оказывается, невероятно сложны. С чем-то большим, чем несколько сотен магнитов, компьютерное моделирование потребовало бы нелепого количества времени, чтобы выдать ответ.
Теперь сделайте эти магниты квантовыми — отдельные атомы подчиняются византийским правилам квантового мира. Как вы могли догадаться, проблема становится еще сложнее. «Взаимодействия становятся более сложными», — сказал Генри Юэн Колумбийского университета. «Существует более сложное ограничение на то, когда два соседних «квантовых магнита» счастливы».
Эти кажущиеся простыми системы обеспечили исключительное понимание пределов вычислений как в классической, так и в квантовой версиях. В случае классических или неквантовых систем знаменательная теорема из компьютерных наук ведет нас дальше. Названная теоремой PCP (от «вероятностно проверяемого доказательства»), она говорит, что не только конечное состояние магнитов (или аспекты, связанные с ним) невероятно сложно вычислить, но и многие шаги, ведущие к нему. Сложность ситуации еще более драматичная, иными словами, конечное состояние окружено зоной загадочности.
Другая версия теоремы PCP, еще не доказанная, специально касается квантового случая. Ученые-компьютерщики подозревают, что квантовая гипотеза PCP верна, и ее доказательство изменит наше понимание сложности квантовых проблем. Это считается, возможно, самой важной открытой проблемой в теории сложности квантовых вычислений. Но пока он остается недоступным.
Девять лет назад два исследователя определили промежуточную цель, которая поможет нам ее достичь. Они придумали более простая гипотеза, известная как гипотеза об «отсутствии низкоэнергетического тривиального состояния» (NLTS), которая должна быть верной, если верна квантовая гипотеза PCP. Доказательство не обязательно облегчило бы доказательство квантовой гипотезы PCP, но разрешило бы некоторые из ее самых интригующих вопросов.
Затем в прошлом месяце трое компьютерщиков доказал гипотезу NLTS. Результат имеет поразительные последствия для информатики и квантовой физики.
«Это очень интересно, — сказал Дорит Ааронов из Еврейского университета в Иерусалиме. «Это побудит людей изучить более сложную проблему квантовой гипотезы PCP».
Чтобы понять новый результат, начните с представления квантовой системы, такой как набор атомов. У каждого атома есть свойство, называемое спином, которое чем-то похоже на ориентацию магнита в том смысле, что он указывает вдоль оси. Но в отличие от выравнивания магнита, вращение атома может находиться в состоянии одновременного смешения разных направлений — явление, известное как суперпозиция. Кроме того, может оказаться невозможным описать спин одного атома без учета спинов других атомов из отдаленных областей. Когда это происходит, говорят, что эти взаимосвязанные атомы находятся в состоянии квантовой запутанности. Запутывание замечательно, но также хрупко и легко разрушается тепловыми взаимодействиями. Чем больше тепла в системе, тем сложнее ее запутать.
Теперь представьте себе охлаждение группы атомов до тех пор, пока они не приблизится к абсолютному нулю. По мере того как система охлаждается и модели запутывания становятся более стабильными, ее энергия уменьшается. Наименьшая возможная энергия, или «энергия земли», дает краткое описание сложного конечного состояния всей системы. Или, по крайней мере, было бы, если бы это можно было вычислить.
Начиная с конца 1990-х годов исследователи обнаружили, что для некоторых систем эта энергия земли никогда не может быть рассчитана в разумные сроки.
Однако физики считали, что уровень энергии, близкий к энергии земли (но не совсем такой), должно быть легче вычислить, поскольку система будет теплее и менее запутанной, а значит, проще.
Ученые-компьютерщики не согласились. Согласно классической теореме PCP, энергии, близкие к конечному состоянию, вычислить так же сложно, как и саму конечную энергию. И поэтому квантовая версия теоремы PCP, если она верна, говорит, что энергии-предшественники энергии земли так же сложно рассчитать, как и энергию земли. Поскольку классическая теорема PCP верна, многие исследователи считают, что квантовая версия тоже должна быть верна. «Конечно, квантовая версия должна быть правдой», — сказал Юэнь.
Физические следствия такой теоремы были бы глубокими. Это означало бы, что существуют квантовые системы, которые сохраняют запутанность при более высоких температурах, что полностью противоречит ожиданиям физиков. Но никто не мог доказать, что такие системы существуют.
В 2013 году Майкл Фридман и Мэтью Хастингс, работавшие в Microsoft Research’s Station Q в Санта-Барбаре, Калифорния, сузили круг проблемы. Они решили искать системы, самые низкие и почти самые низкие энергии которых трудно рассчитать по одному показателю: количеству схем, которые потребуются компьютеру для их моделирования. Эти квантовые системы, если бы они смогли их найти, должны были бы сохранять богатые паттерны запутанности при всех своих самых низких энергиях. Существование таких систем не докажет квантовую гипотезу PCP — могут быть и другие показатели твердости, которые следует учитывать, — но это будет считаться прогрессом.
Ученые-компьютерщики не знали о таких системах, но они знали, где их искать: в области исследований, называемой квантовой коррекцией ошибок, где исследователи создают рецепты запутывания, предназначенные для защиты атомов от возмущений. Каждый рецепт известен как код, и существует множество кодов как большего, так и меньшего масштаба.
В конце 2021 года компьютерщики сделал большой прорыв в создании квантовых кодов с исправлением ошибок по существу идеального характера. В последующие месяцы несколько других групп исследователей использовали эти результаты для создания различных версий.
Три автора новой статьи, которые сотрудничали в смежных проектах в течение последних двух лет, собрались вместе, чтобы доказать, что один из новых кодов обладает всеми свойствами, необходимыми для создания квантовой системы того типа, о котором выдвинули гипотезу Фридман и Гастингс. . Тем самым они доказали гипотезу NLTS.
Их результат показывает, что запутанность не обязательно настолько хрупка и чувствительна к температуре, как думали физики. И это поддерживает квантовую гипотезу PCP, предполагающую, что даже вдали от энергии земли энергию квантовой системы практически невозможно рассчитать.
«Это говорит нам о том, что то, что казалось маловероятным, является правдой», — сказал он. Исаак Ким из Калифорнийского университета в Дэвисе. — Хотя и в какой-то очень странной системе.
Исследователи считают, что для доказательства полной квантовой гипотезы PCP потребуются различные технические инструменты. Однако они видят причины для оптимизма, что нынешний результат сблизит их.
Их, пожалуй, больше всего интересует, могут ли недавно открытые квантовые системы NLTS — хотя и возможны в теории — быть созданы в природе, и как они будут выглядеть. Согласно текущему результату, для этого потребуются сложные модели дальнодействующей запутанности, которые никогда не создавались в лаборатории и которые можно было построить только с использованием астрономического числа атомов.
«Это высокотехнологичные объекты», — сказал Чинмай Нирхе, ученый-компьютерщик из Калифорнийского университета в Беркли и соавтор новой статьи вместе с Анураг Аншу Гарвардского университета и Николас Брейкманн Университетского колледжа Лондона.
«Если у вас есть возможность соединить действительно далекие кубиты, я думаю, вы сможете реализовать систему», — сказал Аншу. «Но есть еще одно путешествие, чтобы действительно перейти к низкоэнергетическому спектру». Брейкманн добавил: «Возможно, есть какая-то часть вселенной, которая является NLTS. Я не знаю."
