Пошук кількісної оцінки | Журнал Quanta

Минуло більше 40 років відтоді, як фізик Річард Фейнман зазначив, що створення обчислювальних пристроїв на основі квантових принципів може розкрити потужності, набагато більші, ніж у «класичних» комп’ютерів. У програмній промові 1981 р Якому часто приписують започаткування галузі квантових обчислень, Фейнман закінчив відомою тепер дотепою:

«Природа не класична, до біса, і якщо ви хочете створити симуляцію природи, вам краще зробити її квантово-механічної».

Минуло майже 30 років з тих пір, як математик Пітер Шор запропонував перше потенційно трансформаційне використання квантових комп’ютерів. Значна частина безпеки цифрового світу базується на припущенні, що розкладання великих чисел на множники є складним і тривалим завданням. Шор показав, як використовувати кубіти — квантові об’єкти, які можуть існувати в суміші 0 і 1 — щоб зробити це миттєво, принаймні відносно відомих класичних методів.

Дослідники цілком упевнені (хоча й не зовсім впевнені), що квантовий алгоритм Шора перевершує всі класичні алгоритми, тому що — незважаючи на величезні стимули — ніхто не зміг зламати сучасне шифрування за допомогою класичної машини. Але для завдань, менш привабливих, ніж факторинг, це важко сказати напевно чи є квантові методи кращими. Пошук нових блокбастерів став чимось на кшталт випадкової гри в здогадки.

«Це дурний спосіб зробити це», - сказав Кристал Ноель, фізик Університету Дьюка.

Протягом останніх 20 років конфедерація фізиків, схильних до математики, і математиків, схильних до математики, намагалася більш чітко визначити силу квантової сфери. Їх мета? Щоб знайти спосіб кількісного визначення квантової величини. Вони мріють про число, яке вони можуть призначити розташуванню кубітів, утвореному якимось квантовим обчисленням. Якщо цифра низька, тоді було б легко змоделювати цей розрахунок на ноутбуці. Якщо він високий, кубіти являють собою відповідь на справді складну проблему, недосяжну для будь-якого класичного пристрою.

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

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

Їхній пошук був плідним — можливо, надто плідним. Замість того щоб знайти одну метрику, дослідники натрапили на три, кожна з яких є окремим способом розділення квантової та класичної сфер. Тим часом фізики почали задаватися питанням, чи найменш конкретна кількість із трьох виявляється за межами квантових комп’ютерів. Попередні дослідження показали, що це так, і що це може запропонувати новий спосіб зрозуміти фази квантової матерії та руйнівну природу чорних дір.

З цих причин і фізики, і комп’ютерники намагалися нанести на карту точну топографію цього квантового царства, що складається з трьох частин. Цього літа тріо дослідницьких груп оголосили, що вони сформулювали найкращу карту найменш знайомих із трьох провінцій, додавши важливі деталі до розуміння того, де закінчується класичне і починається справді квантове.

«Це дуже важливо зрозуміти, де знаходиться цей горизонт». Каміль Корзеква Ягеллонського університету в Польщі, один із дослідників нових робіт. «Що насправді є квантовим щодо кванта?»

Заплутаність

У 1990-х роках фізичний компонент, який зробив квантові комп’ютери потужними, здавався очевидним. Це мала бути заплутаність, «моторошний» квантовий зв’язок між віддаленими частинками, який сам Ервін Шредінгер визначив як «характерну рису квантової механіки».

«Про заплутаність згадали дуже швидко», — сказав Річард Йожа, математик Кембриджського університету. «І всі просто припустили, що це все».

Якийсь час здавалося, що пошук цієї важливої ​​квантової спеції закінчився, навіть не розпочавшись.

Заплутаність, явище, в якому дві квантові частинки утворюють спільний стан, включало в себе те, що важко робити з квантовою механікою — і, отже, те, у чому квантові комп’ютери можуть перевершити. Якщо частинки не заплутані, ви можете відстежувати їх окремо. Але коли частинки стають заплутаними, модифікація або маніпулювання однією частинкою в системі передбачає облік її зв’язків з іншими заплутаними частинками. Це завдання зростає експоненціально, коли ви додаєте більше частинок. Для повного уточнення стану n переплутаних кубітів, вам потрібно щось на зразок 2ⁿ класичні біти; щоб обчислити ефект налаштування одного кубіта, вам потрібно виконати приблизно 2ⁿ класичні операції. Для трьох кубітів це лише вісім кроків. Але для 10 кубітів це 1,024 — математичне визначення речей, які швидко зростають.

У 2002, Йожа допоміг розробити простий процес використання класичного комп’ютера для моделювання квантової «схеми», яка є певною серією операцій, що виконуються над кубітами. Якби ви дали класичній програмі деяке початкове розташування кубітів, вона передбачила б їхнє остаточне розташування після того, як вони пройшли через квантову схему. Йожа довів, що якщо його алгоритм симулює схему, яка не заплутує кубіти, він може обробляти все більшу кількість кубітів, не потребуючи експоненціально довшого часу для роботи.

Іншими словами, він показав, що квантову схему без заплутаності легко змоделювати на класичному комп’ютері. У обчислювальному сенсі схема за своєю суттю не була квантовою. Сукупність усіх таких ланцюгів, що не заплутуються (або, що еквівалентно, усіх упорядковань кубітів, які можуть вийти з цих ланцюгів, що не заплутуються), утворила щось на зразок класично моделюваного острова у величезному квантовому морі.

У цьому морі були стани, що виникають в результаті справді квантових ланцюгів, ті, для класичного моделювання яких можуть знадобитися мільярди років. З цієї причини дослідники почали розглядати заплутаність не просто як квантову властивість, а як квантовий ресурс: це те, що потрібно, щоб досягти незвіданих глибин, де знаходяться потужні квантові алгоритми, такі як Шор.

Сьогодні заплутаність все ще залишається найбільш вивченим квантовим ресурсом. «Якщо ви запитаєте 99 із 100 фізиків [що робить квантові схеми потужними], перше, що спадає на думку, це заплутаність», — сказав Фефферман.

Активні дослідження зв’язку заплутаності зі складністю тривають. Фефферман і його співробітники, наприклад, показали минулого року що для одного конкретного класу квантових схем заплутаність повністю визначає, наскільки складно схему класично моделювати. «Як тільки ви дійдете до певної міри заплутаності, — сказав Фефферман, — ви можете фактично довести твердість. Немає [класичного] алгоритму, який би спрацював».

Але доказ Феффермана справедливий лише для одного виду схем. І навіть 20 років тому дослідники вже визнавали, що лише заплутаність не в змозі охопити багатство квантового океану.

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

Пошуки квантової величини, як виявилося, тільки починалися.

 Трохи магії

Йожа знав, що заплутаність — це не останнє слово щодо квантовості, тому що за чотири роки до своєї роботи фізик Даніель Готтесман показав інше. На конференції 1998 року в Тасманії Готтесман пояснені що в конкретному типі квантової схеми, здавалося б, квінтесенційна квантова величина стала дрібницею для моделювання класичного комп’ютера.

У методі Готтесмана (який він обговорював з математиком Емануелем Кніллом) операція заплутування практично нічого не коштувала. Ви можете заплутати скільки завгодно кубітів, і класичний комп’ютер усе ще зможе встигати.

«Це був один із перших сюрпризів, теорема Готтесмана-Нілла, у 90-х роках», — сказав Корзеква.

Можливість класичної імітації заплутаності здавалася трохи дивом, але була підступна річ. Алгоритм Готтесмана-Нілла не міг впоратися з усіма квантовими схемами, лише з тими, які прилипали до так званих воріт Кліффорда. Але якщо ви додасте «T gate», на перший погляд нешкідливий гаджет, який обертає кубіт певним чином, їхня програма захлинеться.

Схоже, що ці T-ворота виробляють якийсь квантовий ресурс — щось, по суті, квантове, що неможливо змоделювати на класичному комп’ютері. Невдовзі пара фізиків дадуть квантовій сутності, створеній забороненим обертанням Т-образних воріт, привабливу назву: магія.

У 2004 році Сергій Бравий, тодішній співробітник Інституту теоретичної фізики Ландау в Росії, та Олексій Китаєв з Каліфорнійського технологічного інституту розробили дві схеми для виконання будь-яких квантових розрахунків: Ви можете включити T-затвори в саму схему. Або ви можете взяти "чарівний стан” кубітів, які були підготовлені з T-затворами іншою ланцюгом, і подають його в схему Кліффорда. У будь-якому випадку, магія була важливою для досягнення повної кількісності.

Через десятиліття Бравий і Девід Госсет, дослідник з Університету Ватерлоо в Канаді, розробив, як виміряти кількість магії в наборі кубітів. А в 2016 р. вони розвивалися класичний алгоритм для моделювання ланцюгів з низьким рівнем магії. Їхній програмі знадобилося експоненціально довше для кожного додаткового T-ворота, хоча експоненціальне зростання не таке вибухове, як в інших випадках. Нарешті вони підвищили ефективність свого методу, класично змоделювавши дещо магічну схему із сотнями воріт Кліффорда та майже 50 воріт Т.

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

У гру увійшов новий квантовий ресурс — магія. Але на відміну від заплутаності, яка виникла як знайоме фізичне явище, фізики не були впевнені, чи магія має велике значення поза квантовими комп’ютерами. Останні результати показують, що це може бути.

У 2021 році дослідники визначили певні фази квантової матерії які гарантовано мають магію, так само як і багато фаз матерії конкретні моделі заплутаності. «Потрібні точніші вимірювання обчислювальної складності, як магія, щоб мати повний ландшафт фаз матерії», — сказав Тімоті Хсі, фізик Інституту теоретичної фізики «Периметр», який працював над результатом. І Аліосія Хамма Неаполітанського університету разом зі своїми колегами, нещодавно вивчений чи можливо — теоретично — реконструювати сторінки щоденника, поглиненого чорною дірою, спостерігаючи лише за випромінюванням, яке вона випромінює. Відповідь була так, сказав Хамма, «якщо чорна діра не має надто багато магії».

Для багатьох фізиків, включаючи Хамму, фізичні інгредієнти, необхідні для того, щоб зробити систему надзвичайно квантовою, здаються зрозумілими. Ймовірно, необхідна певна комбінація заплутування та магії. Жодного одного недостатньо. Якщо стан має нульову оцінку за будь-яким показником, ви можете змоделювати це на своєму ноутбуці за допомогою Йози (якщо заплутаність нульова) або Браві та Госсета (якщо магія нульова).

І все ж квантові пошуки тривають, тому що комп’ютерні вчені давно знають, що навіть магія та заплутаність разом не можуть справді гарантувати кількісність.

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

Інша квантова метрика почала формуватися майже чверть століття тому. Але донедавна вона була найменш розвиненою з трьох.

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

Поки ви не обмінюєтеся кубітами, ви можете заплутати їх і наповнити їх скільки завгодно магії, і ви все одно опинитеся на ще одному відмінному класичному острові. Але як тільки ви починаєте перемішувати кубіти, ви можете творити чудеса, які не під силу будь-якому класичному комп’ютеру.

Це було «досить дивно», сказав Йожа. «Як просто заміна двох кубітів може дати вам всю цю силу?»

За кілька місяців фізики-теоретики Барбара Терхал і Девід ДіВінченцо відкрили джерело цієї сили. Вони показали, що схеми Valiant без своп-вортів, відомі як схеми «matchgate», таємно симулювали добре відомий клас фізичних проблем. Подібно до того, як комп’ютери симулюють зростання галактик або ядерні реакції (не будучи насправді галактикою чи ядерною реакцією), ланцюги матчів імітують групу ферміонів, сімейство елементарних частинок, що містить електрони.

Коли вентилі обміну не використовуються, змодельовані ферміони не взаємодіють, або «вільні». Вони ніколи не стикаються один з одним. Проблеми, пов’язані з вільними електронами, фізикам відносно легко вирішити, іноді навіть за допомогою олівця та паперу. Але коли використовуються вентилі обміну, змодельовані ферміони взаємодіють, збиваючись разом і виконуючи інші складні речі. Ці проблеми надзвичайно важкі, якщо не нерозв’язні.

Оскільки ланцюги відповідного зв’язку моделюють поведінку вільних, невзаємодіючих ферміонів, їх легко моделювати класичним способом.

Але після першого відкриття ланцюги matchgate залишилися майже не дослідженими. Вони не були такими актуальними для основних квантових обчислень, і їх було набагато складніше проаналізувати.

Це змінилося минулого літа. Три групи дослідників незалежно один від одного взяли участь у роботі Браві, Ґоссета та їхніх співробітників, щоб розв’язати проблему — випадковий перетин досліджень, який, принаймні в одному випадку, було виявлено, коли ферміони прийшли за кавою (як це часто відбувається, коли фізики отримують разом).

Команди координували звільнити of їх результати у липні.

Усі три групи по суті переробили математичні інструменти, які піонери магії розробили для дослідження схем Кліффорда, і застосували їх до сфери схем сірникових воріт. Сергій Стрельчук та Джошуа Кадбі з Кембриджа зосередився на математичному вимірюванні квантового ресурсу, якого не вистачало в схемах matchgate. Концептуально цей ресурс відповідає «інтерактивності» — або тому, наскільки змодельовані ферміони можуть відчувати один одного. Інтерактивність класично легко моделювати, а більше інтерактивності ускладнює моделювання. Але наскільки додаткова порція інтерактивності ускладнила симуляції? А чи були якісь ярлики?

«У нас не було інтуїції. Довелося починати з нуля», – сказав Стрельчук.

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

Результатом став своєрідний словник для перенесення класичних алгоритмів моделювання зі світу Кліффорда у світ matchgate. «В основному все, що вони мають для схем [Кліффорда], тепер можна перекласти», — сказав Беатріс Діас, фізик з Технічного університету в Мюнхені, «тому нам не потрібно винаходити всі ці алгоритми».

Тепер швидші алгоритми можуть класично моделювати схеми з декількома вентилями обміну. Як і у випадку з заплутаністю та магією, алгоритми займають експоненціально більше часу з додаванням кожного забороненого воріт. Але алгоритми є значним кроком вперед.

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

«Симуляція квантових комп’ютерів є корисною для багатьох людей», — сказав Рірдон-Сміт. «Ми хочемо зробити це якомога швидше та дешевше».

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

Подальші острови на горизонті

Зараз дослідники стають зручнішими для кількісного визначення квантової величини за допомогою трьох показників, кожен з яких відповідає одному з трьох класичних методів моделювання. Якщо колекція кубітів значною мірою розплутана, має мало магії або імітує групу майже вільних ферміонів, тоді дослідники знають, що вони можуть відтворити її вихід на класичному ноутбуці. Будь-яка квантова схема з низьким балом за однією з цих трьох квантових метрик лежить на мілководдях неподалік від берегів класичного острова і точно не буде наступним алгоритмом Шора.

«Зрештою, [вивчення класичного моделювання] дійсно допомагає нам зрозуміти, де можна знайти квантову перевагу», — сказав Госсет.

Але чим більше дослідники знайомляться з цими трьома різними способами вимірювання того, наскільки квантовою може бути група кубітів, тим більш помилковою здається початкова мрія знайти єдине число, яке охоплює всі аспекти квантовості. У строго обчислювальному сенсі будь-яка дана схема повинна мати один найкоротший час, необхідний для її моделювання за допомогою найшвидшого з усіх можливих алгоритмів. Проте заплутаність, магія та ферміонна магія досить відрізняються одна від одної, тому перспектива об’єднати їх під однією великою квантовою метрикою для обчислення цього абсолютного найкоротшого часу роботи здається віддаленою.

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

Швидше, три квантові ресурси, здається, є артефактами математичних мов, які використовуються для втиснення складності квантової величини в простіші рамки. Заплутаність з’являється як ресурс, коли ви практикуєте квантову механіку у спосіб, який описав Шредінгер, який використовує його однойменне рівняння, щоб передбачити, як зміниться хвильова функція частинки в майбутньому. Це версія підручника квантової механіки, але це не єдина версія.

Коли Ґоттесман розробив свій метод моделювання ланцюгів Кліффорда, він заснував його на старішому різновиді квантової механіки, розробленому Вернером Гейзенбергом. На математичній мові Гейзенберга стан частинок не змінюється. Натомість еволюціонують «оператори» — математичні об’єкти, за допомогою яких можна передбачити ймовірність певного спостереження. Обмеження погляду на вільні ферміони передбачає розгляд квантової механіки через ще одну математичну лінзу.

Кожна математична мова красномовно фіксує певні аспекти квантових станів, але ціною спотворення деяких інших квантових властивостей. Ці незграбно виражені властивості потім стають квантовим ресурсом у цій математичній структурі — магія, заплутаність, ферміонна магія. Подолання цього обмеження та виявлення однієї квантової особливості, яка керувала б ними всіма, припускає Йожа, потребує вивчення всіх можливих математичних мов для вираження квантової механіки та пошуку універсальних рис, які всі вони можуть мати спільні.

Це не дуже серйозна дослідницька пропозиція, але дослідники вивчають додаткові квантові мови, крім трьох основних, і відповідні квантові ресурси, які приходять разом з ними. Се, наприклад, цікавиться фазами квантової матерії, які створюють безглузді негативні ймовірності при стандартному аналізі. Цей негатив, як він виявив, може визначати певні фази матерії так само, як магія.

Кілька десятиліть тому здавалося, що відповідь на питання про те, що робить систему квантовою, очевидна. Сьогодні дослідники знають краще. Після 20 років дослідження перших кількох класичних островів багато хто підозрює, що їхня подорож може ніколи не завершитися. Незважаючи на те, що вони продовжують вдосконалювати своє розуміння того, де немає квантової енергії, вони знають, що ніколи не зможуть точно сказати, де вона є.

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів з фізики і ви будете введені, щоб виграти безкоштовно Quanta товар