Квантовий обчислювач випередив класичний у вирішенні нового завдання, а точніше в перевірці цього рішення. Фізики експериментально реалізували протокол перевірки вирішення завдання, яку не можна вирішити на класичному комп'ютері за поліноміальний час. Вони показали, що для перевірки квантовій машині потрібно в тисячу разів менше інформації. Робота опублікована в.
Квантовий комп'ютер сильніший і потужніший за класичний не в будь-якому завданні, про це ми докладніше розповідали в матеріалі «Коли чекати квантової переваги». Поки вченим вдалося продемонструвати квантову перевагу на завданнях генерації випадкового рядка і бозонного семплінгу. З прикладної точки зору ці завдання не представляють якоїсь цінності - вони показують можливості квантових обчислювачів і їх майбутнього в цілому. Демонстрація вирішення більш застосовних і реальних завдань впирається в маленьке число кубітів обчислювача.
Вибір завдань, які вчаться вирішувати на квантових обчислювачах, невипадковий. Квантовий комп'ютер повинен впоратися із завданнями, вирішення яких займає у класичного необмежений час. Вчені давно стикаються з такими завданнями і вже встигли розділити їх на класи складності залежно від того, як швидко збільшується час вирішення завдання при збільшенні кількості вхідних даних. Причому під часом вирішення завдання мається на увазі час, який буде потрібно самому швидкому алгоритму. Невизначеність, яка таїться в терміні «найшвидший алгоритм» (раптом він є, а вчені його ще не придумали і не знайшли) народжує відому задачу рівності класів P і NP. NP клас складності включає завдання, вирішення яких можна перевірити за поліноміальний час за наявності додаткових відомостей, а клас P - завдання, для яких залежність часу вирішення від розмірності завдання поліноміальна. Вважається, що квантові алгоритми зможуть поставити крапку в цьому питанні.
Одне з популярних завдань для квантових обчислювачів - завдання про здійсненність бульових формул (SAT). Вона не просто належить класу NP, але і будь-яку NP складну задачу можна звести до неї (такий підклас NP складності називають NP-повним). N-SAT завдання складається з набору умов, кожна з яких у свою чергу складається з N бульових змінних (можуть приймати значення 0 або 1). В умову може входити як змінна, так і її заперечення (НЕ). Задачу можна вирішити, якщо знайти такий набір змінних, що підсумкова формула буде вірна (дорівнює 1). Наприклад, 2-SAT завдання може виглядати так: (X1 АБО X3) І (НЕ X2 АБО X1). Виходить, що для вирішення завдання потрібно, щоб кожна дужка була рівна 1. Тоді для вирішення достатньо зафіксувати X1 = 1, а X2 і X3 можуть бути будь-якими. Зрозуміло, що збільшення кількості умов (дужок) ускладнює завдання, як і число елементів у дужці.
Команда фізиків під керівництвом Йорданіса Керенідіса (Iordanis Kerenidis) змогли показати експериментально, що квантовий обчислювач швидше справляється з перевіркою рішення NP-повного завдання, ніж класичний і розглянули всі можливі реальні обмеження, які виникають в експерименті. Вчені розглядали цікаве завдання 2-out-of-4 SAT: у кожній дужці з чотирьох змінних як мінімум дві повинні бути 1.
Для того щоб реалізувати перевірку рішення, необхідно дві людини - в квантовому світі це Мерлін і Артур. Мерлін знаходить якесь імовірно вірне рішення завдання і відправляє його Артуру, який перевіряє це рішення на вірність. Важливо відзначити, що Мерлін і Артур працюють в умовах обмеженої інформації, тобто Мерлін не може вислати все завдання цілком. І в класичному світі, якщо ж Артур буде перевіряти за однією випадковою умовою, то Мерлін може кожен раз змінювати значення змінних, що спотворить перевірку. У квантовому світі Мерлін кодує можливе вирішення завдання за допомогою когерентних станів і відправляє його Артуру. Артур готує свій набір послідовних станів з потрібною амплітудою і поділом за часом. Стани Артура і Мерліна інтерферують на світлоделювачі і залежно від фази стану Мерліна клікає або один, або інший детектор. Збільшення числа фотонів в одному імпульсі збільшує ймовірність задетектувати стан і робить схему більш ефективною.
У перевірці вірності рішення відіграють важливу роль дві ймовірності: перша показує як часто при дійсно правильному рішенні результат верифікації це підтверджує, а друга описує ситуацію, коли перевіряючий прийняв неправильне рішення за вірне. Першу (С) намагаються збільшити, а другу (S) зменшити. Авторам вдалося отримати C більше 0.9 при утриманні S менше 0.6.
Крім цього, для неправильного рішення має значення число умов, яке виявилося невиконаним. Вчені зафіксували це значення на рівні 15 відсотків, число змінних вони вибирали рівним десяти тисячам. Для розрахунку реальної експериментальної схеми, вони врахували неідеальність детекторів і вибрали значення видності в 0.91 (в ідеалі вона дорівнює 1). При всіх перерахованих параметрах, досліджували шукали оптимальне число фотонів в імпульсі для демонстрації переваги квантового обчислювача перед класичним. Виявилося, що розрив між ймовірністю C і S близький до одиниці в широкому діапазоні і для експерименту автори використовували величину в 1.31. Експеримент показав, що для перевірки квантовий обчислювач вимагає в тисячу разів менше біт, ніж класичний.
Завдання перевірки рішення на відміну від попередніх завдань для демонстрації можливостей квантовий обчислювачів, робить крок на шляху до реальних застосувань. Фізики пропонують використовувати потужні квантові обчислювачі для вирішення завдань, а перевірку вірності рішень проводити на менш потужних машинах. Іншим можливим застосуванням вони бачать квантовий інтернет.
«Залізом» в експерименті вчених служили фотони, як і в експерименті китайських фізиків, які показали перевагу квантового обчислювача у вирішенні завдання бозонного семплінгу. А найпершою демонстрацією квантової переваги була робота вчених з Google, в якій вони використовували обчислювач на надпровідниках.