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

Исследователи Сергей Бравый из IBM, Дэвид Госсет из университета Ватерлоо и Роберт Кениг из Мюнхенского технического университета опубликовали доказательства эффективности квантовых схем.
Они продемонстрировали, что обычные компьютеры не смогут решать задачи, которые требуют фиксированной глубины вычислений за фиксированное время независимо от количества вводных. Обычному компьютеру по мере увеличения исходных данных потребуется и увеличение глубины, тогда как для его квантового «оппонента» этот параметр может оставаться неизменным.
Так смогут ли квантовые компьютеры когда-нибудь превзойти вычислительные мощности обычных? До недавнего времени этот вопрос оставался открытым.
Манящая «глубина»
Современные квантовые компьютеры в работе используют кубиты. Они отдаленно напоминают биты, но представляют все возможные значения вероятностей, не ограничиваясь состоянием 0 или 1. Но кубиты и время когерентности в работе квантовых компьютеров ограничены. Из-за этого область применения вычислений, которые способны выполнять квантовые машины, сужается.
Когерентность – это согласованность протекания волновых, колебательных движений, процессов, совпадающих по фазе или сохраняющих разность фаз постоянной во времени.
Короткое время когерентности до того, как система станет хаотичной и бесполезной для вычислений, ограничивает количество производимых операций. В квантовых вычислениях это называется «глубина», а современные системы считаются «неглубокими».
Задача Бернштейна – Вазирани
Команда ученых поставила перед квантовым компьютером вычислительную проблему: задачу Бернштейна-Вазирани. Ее решение считается недоступным для традиционных устройств.
В черном ящике реализована функция f:
f : {0, 1}
n → {0, 1}
f(x) = a • x
Необходимо найти число a.
Не будем вдаваться в математические подробности, но исследователи показывают, что даже «мелкий» квантовый компьютер может легко превзойти классический компьютер при решении этой проблемы.
«Мы пытались понять, что можно сделать с "мелкой" квантовой схемой и искали подходящую модель для вычисления, которую можно реализовать на краткосрочном квантовом устройстве. В нашем докладе говорится, что существуют определенные вычислительные задачи, которые вы можете решить на квантовом компьютере с постоянной глубиной. Например, вы увеличиваете количество входных битов, а глубина квантового алгоритма, который решает проблему, остается постоянной», – рассказал Сергей Бравый. Классический компьютер не справился бы с этой задачей при одинаковых условиях теста.
Не останавливаться на достигнутом
Авторы доклада уверены, что зацикливаться на текущем состоянии квантовых вычислений нельзя: «Мы стараемся быть предельно осторожными и честными, когда говорим, что наш опыт – это то, что сегодня могут делать квантовые компьютеры по сравнению с классическими». Но достигнутый результат доказывает, что исследовать квантовые алгоритмы стоит». Ученые ожидают, что реальные преимущества квантовых вычислений можно будет применить на практике в ближайшие 5-10 лет.
См. также
Российский разработчик создал неофициальную версию Clubhouse для Android
26.02.2021 1718 VKuser24342747 0
Масштабное обновление Trello: пять новых видов досок и интеграция с Google Docs
25.02.2021 2705 user1015646 0
Видеоигра на базе нейросетевого генератора текстов стала бизнес-консультантом
25.02.2021 1654 VKuser24342747 1
В ближайшие годы возрастет потребность в персонале центров обработки данных
24.02.2021 1897 SKravchenko 0
Rustоманы из Долины: Google, Microsoft, Huawei, Mozilla и AWS основали фонд поддержки языка программирования
16.02.2021 1588 user1015646 0
Украинская команда FireWay одержала победу в хакатоне NASA Space Apps Challenge 2020
05.02.2021 1947 SKravchenko 2
Microsoft участвует в разработке цифрового паспорта вакцинации от Covid-19
02.02.2021 1738 capitan 3
Что нового в Chrome 88: проверка надежности паролей и поддержка профилей
01.02.2021 2205 user1015646 0
280 символов для науки: Twitter откроет доступ ученым к архиву твитов
29.01.2021 1473 VKuser24342747 1