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