Квантовые компьютеры обещают решать определенные задачи с преимуществом, которое возрастает по мере усложнения задач. Однако они также очень подвержены ошибкам или шуму. Задача, по словам Лидара, состоит в том, чтобы "получить преимущество в реальном мире, где современные квантовые компьютеры все еще "шумные"". Это подверженное помехам состояние современных квантовых вычислений называется "NISQ" (Шумная квантовая эра промежуточного масштаба), термин адаптирован из используемой архитектуры RISC для описания классических вычислительных устройств. Таким образом, любая нынешняя демонстрация преимущества квантовой скорости требует снижения уровня шума.

Чем больше неизвестных переменных в задаче, тем сложнее обычно ее решить компьютеру. Ученые могут оценить производительность компьютера, сыграв с ним в какую-нибудь игру, чтобы увидеть, насколько быстро алгоритм сможет угадать скрытую информацию. Например, представьте себе версию телевизионной игры Jeopardy, в которой участники по очереди отгадывают секретное слово известной длины, по одному целому слову за раз. Ведущий показывает только одну правильную букву для каждого угаданного слова, прежде чем случайным образом изменить секретное слово.

В своем исследовании исследователи заменили слова битовыми строками. Классическому компьютеру в среднем потребовалось бы примерно 33 миллиона предположений, чтобы правильно идентифицировать 26-битную строку. Напротив, идеально функционирующий квантовый компьютер, представляющий предположения в квантовой суперпозиции, мог бы определить правильный ответ всего за одно предположение. Такая эффективность достигается за счет использования квантового алгоритма, разработанного более 25 лет назад учеными-компьютерщиками Итаном Бернштейном и Умешем Вазирани. Однако шум может значительно ограничить это экспоненциальное квантовое преимущество.

Lidar и Pokharel добились своего квантового ускорения, адаптировав метод подавления шума, называемый динамической развязкой. Они потратили год на эксперименты, причем Покхарел работал докторантом в Lidar в USC. Первоначально казалось, что применение динамической развязки приводит к снижению производительности. Однако после многочисленных доработок квантовый алгоритм заработал так, как было задумано. Время на решение задач тогда увеличивалось медленнее, чем при использовании любого классического компьютера, причем квантовое преимущество становилось все более очевидным по мере усложнения задач.

Лидар отмечает, что "в настоящее время классические компьютеры все еще могут решить проблему быстрее в абсолютном выражении". Другими словами, заявленное преимущество измеряется с точки зрения масштабирования времени, необходимого для поиска решения, а не абсолютного времени. Это означает, что для достаточно длинных битовых строк квантовое решение в конечном итоге будет быстрее.

Исследование убедительно демонстрирует, что при надлежащем контроле ошибок квантовые компьютеры могут выполнять полные алгоритмы с лучшим масштабированием времени, необходимого для поиска решения, чем обычные компьютеры, даже в эпоху NISQ.