Ученые доказали превосходство квантовых компьютеров над классическими

Исследователи Сергей Бравый из IBM, Дэвид Госсет из университета Ватерлоо и Роберт Кениг из Мюнхенского технического университета опубликовали доказательства эффективности квантовых схем.

Они продемонстрировали, что обычные компьютеры не смогут решать задачи, которые требуют фиксированной глубины вычислений за фиксированное время независимо от количества вводных. Обычному компьютеру по мере увеличения исходных данных потребуется и увеличение глубины, тогда как для его квантового «оппонента» этот параметр может оставаться неизменным.

Так смогут ли квантовые компьютеры когда-нибудь превзойти вычислительные мощности обычных? До недавнего времени этот вопрос оставался открытым.

Манящая «глубина»

Современные квантовые компьютеры в работе используют кубиты. Они отдаленно напоминают биты, но представляют все возможные значения вероятностей, не ограничиваясь состоянием 0 или 1. Но кубиты и время когерентности в работе квантовых компьютеров ограничены. Из-за этого область применения вычислений, которые способны выполнять квантовые машины, сужается. 

Когерентность – это согласованность протекания волновых, колебательных движений, процессов, совпадающих по фазе или сохраняющих разность фаз постоянной во времени.

Короткое время когерентности до того, как система станет хаотичной и бесполезной для вычислений, ограничивает количество производимых операций. В квантовых вычислениях это называется «глубина», а современные системы считаются «неглубокими».

Задача Бернштейна – Вазирани

Команда ученых поставила перед квантовым компьютером вычислительную проблему: задачу Бернштейна-Вазирани. Ее решение считается недоступным для традиционных устройств.

В черном ящике реализована функция f:

f : {0, 1}

n → {0, 1}

f(x) = a • x

Необходимо найти число a.

Не будем вдаваться в математические подробности, но исследователи показывают, что даже «мелкий» квантовый компьютер может легко превзойти классический компьютер при решении этой проблемы.

«Мы пытались понять, что можно сделать с "мелкой" квантовой схемой и искали подходящую модель для вычисления, которую можно реализовать на краткосрочном квантовом устройстве. В нашем докладе говорится, что существуют определенные вычислительные задачи, которые вы можете решить на квантовом компьютере с постоянной глубиной. Например, вы увеличиваете количество входных битов, а глубина квантового алгоритма, который решает проблему, остается постоянной», – рассказал Сергей Бравый. Классический компьютер не справился бы с этой задачей при одинаковых условиях теста.

Не останавливаться на достигнутом

Авторы доклада уверены, что зацикливаться на текущем состоянии квантовых вычислений нельзя: «Мы стараемся быть предельно осторожными и честными, когда говорим, что наш опыт – это то, что сегодня могут делать квантовые компьютеры по сравнению с классическими». Но достигнутый результат доказывает, что исследовать квантовые алгоритмы стоит». Ученые ожидают, что реальные преимущества квантовых вычислений можно будет применить на практике в ближайшие 5-10 лет.