Квантові комп'ютери обіцяють прорив у вирішенні складних завдань, але їх розвиток ще на ранній стадії. Нещодавно почали говорити про квантову перевагу як про визначний етап, який нещодавно Google перетнув. Але що це означає?
Експерименти з квантовим домінуванням намагаються суворо відповісти на запитання: чи квантові комп’ютери насправді принципово потужніші за класичні комп’ютери? Природним способом було б показати, що квантовий комп'ютер може розкласти велику кількість на фактори (розкладання на фактори, наприклад: 15 = 5 × 3, лише з більшими числами). Комп'ютерні вчені вважають, що це завдання є складним для традиційних комп'ютерів, і значна частина сучасного шифрування базується на цій складності. Однак розкладання на множники "легке" для квантових комп’ютерів і може бути вирішене за допомогою алгоритму Шора. За останніми оцінками, такий експеримент вимагає близько 20 мільйонів кубітів (квантових бітів) і дуже точних операцій [1].
На жаль (або на щастя), квантові комп’ютери далеко не такі розрахунки. Тому вже кілька років вчені шукають розрахунки, які були б дуже складними для класичних комп’ютерів, але могли б бути вирішені кількома десятками кубітів і відносно невеликою кількістю операцій на квантовому комп’ютері. Є кілька таких проблем, але найбільш перспективними є так звані випадкові квантові схеми [2-5].
Проблема полягає в наступному: По-перше, ми випадковим чином вибираємо квантову програму (схему) із заданою кількістю кубітів та елементарними операціями і надаємо їй нульовий вхід. Наше завдання - генерувати зразки з того самого розподілу, що і після вимірювання такого квантового кола. Квантові випадкові схеми є відносно простим завданням для квантових комп'ютерів, оскільки така програма може легко працювати на них. Можна чітко продемонструвати, що за розумних припущень ця проблема буде складною для класичних комп’ютерів [2-5]. Крім того, можна показати, що випадкові схеми все ще важкі для класичних комп’ютерів, навіть якщо врахувати, що квантова схема містить невеликі помилки.
Хороша новина полягає в тому, що класичні суперкомп’ютери знаходяться на межі моделювання існуючих квантових ланцюгів. Гірша новина полягає в тому, що така проблема не має практичного застосування, крім демонстрації потужності квантових комп'ютерів. У цьому відношенні термін домінування дещо вводить в оману - квантові комп’ютери переможуть класичні комп’ютери в ролі випадкових схем приблизно на п’ятдесят кубітів, але класичні комп’ютери все ще будуть домінувати у вирішенні переважної більшості практичних задач.
Багато вчених розглядають потенційну демонстрацію квантового панування як демонстрацію технічного прогресу. Такий експеримент вимагає отримання більше п’ятдесяти кубітів на невеликому чіпі, який буде достатньо ізольований від оточення, щоб кубіти були досить стабільними, але в той же час ми повинні контролювати їх індивідуально і точно. Ці вимоги відрізняють цифровий квантовий комп'ютер від існуючих квантових симуляторів і одночасно відкривають простір для подальших експериментів.