Новая задача для квантового вычислителя с реальным возможным применением

N+1Наука

Квантовый вычислитель оказался сильнее классического в прикладной задаче

Оксана Борзенкова

Federico Centrone et al. / Nature communications, 2021

Квантовый вычислитель опередил классический в решении новой задачи, а точнее в проверке этого решения. Физики экспериментально реализовали протокол проверки решения задачи, которую нельзя решить на классическом компьютере за полиномиальное время. Они показали, что для проверки квантовой машине требуется в тысячу раз меньше информации. Работа опубликована в Nature Communications.

Квантовый компьютер сильнее и мощнее классического не в любой задаче, об этом мы подробнее рассказывали в материале «Когда ждать квантового превосходства». Пока ученым удалось продемонстрировать квантовое превосходство на задачах генерации случайной строки и бозонного сэмплинга. С прикладной точки зрения эти задачи не представляют какой-то ценности — они показывают возможности квантовых вычислителей и их будущего в целом. Демонстрация решения более применимых и реальных задач упирается в маленькое число кубитов вычислителя.

Выбор задач, которые учатся решать на квантовых вычислителях, неслучаен. Квантовый компьютер должен справиться с задачами, решение которых занимает у классического неограниченное время. Ученые давно сталкиваются с такими задачами и уже успели разделить их на классы сложности в зависимости от того, как быстро увеличивается время решения задачи при увеличении числа входных данных. Причем под временем решения задачи подразумевается время, которое потребуется самому быстрому алгоритму. Неопределенность, которая таится в термине «самый быстрый алгоритм» (вдруг он есть, а ученые его еще не придумали и не нашли) рождает известную задачу равенства классов P и NP. NP класс сложности включает задачи, решение которых можно проверить за полиномиальное время при наличии дополнительных сведений, а класс P — задачи, для которых зависимость времени решения от размерности задачи полиномиальная. Считается, что квантовые алгоритмы могут поставить точку в этом вопросе.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

1647-летний можжевельник из Финляндии назвали старейшим древесным растением тундры и Европы 1647-летний можжевельник из Финляндии назвали старейшим древесным растением тундры и Европы

Старейший можжевельник из Финляндии рос с 260 по 1906 год

N+1
Алло, гараж! Алло, гараж!

Смартфон и кнопочный телефон: как выбрать мобильник для своей мамы или бабушки?

Лиза
Почему ученые до сих пор не могут предсказывать землетрясения Почему ученые до сих пор не могут предсказывать землетрясения

Почему землетрясения не поддаются прогнозированию?

ТехИнсайдер
Выбирай себя любой Выбирай себя любой

Сегодня быть собой хорошо как никогда

Cosmopolitan
Прививка от аллергии АСИТ — как она работает? Прививка от аллергии АСИТ — как она работает?

Вместо того чтобы смягчать симптомы аллергии, можно устранить причину

СНОБ
Суперобучение Суперобучение

Система освоения любых навыков – от изучения языков до построения карьеры

kiozk originals
7 подсказок для тех, кого ранит чужая критика 7 подсказок для тех, кого ранит чужая критика

Случалось ли вам слышать от окружающих, что вы на что-то остро реагируете?

Psychologies
Был спрос, деньги и помощь Disney, но все равно обанкротились: как провалился перспективный бренд мороженого Ample Hills Был спрос, деньги и помощь Disney, но все равно обанкротились: как провалился перспективный бренд мороженого Ample Hills

Что будет, если вложить в рост бизнеса миллионы, но экономить на оборудовании

VC.RU
Оптогенетический инструмент управления экспрессией белков in vivo применили для терапии диабета Оптогенетический инструмент управления экспрессией белков in vivo применили для терапии диабета

Ученые создали инструмент, который можно использовать для терапии диабета

N+1
Биолог — об исчезающих видах, экоциде и предсказании эпидемий Биолог — об исчезающих видах, экоциде и предсказании эпидемий

Сколько существует видов жизни на Земле

РБК
Детектор невроза: что отличает хороший психологический тест и можно ли его обмануть Детектор невроза: что отличает хороший психологический тест и можно ли его обмануть

Что делает психологический тест надежным и какие аспекты нужно учитывать

Forbes
Физики измерили асимметрию антикварков внутри протона Физики измерили асимметрию антикварков внутри протона

Асимметрия в распределении верхних и нижних антикварков внутри протона

N+1
Сомнения батьки: ждет ли белорусов настоящий транзит власти Сомнения батьки: ждет ли белорусов настоящий транзит власти

Когда уйдет Александр Лукашенко

Forbes
Чего не хватает российским учёным, чтобы делать прорывные проекты, и почему они вынуждены уходить в коммерцию Чего не хватает российским учёным, чтобы делать прорывные проекты, и почему они вынуждены уходить в коммерцию

Почему в России трудно продавать наукоёмкий продукт

Inc.
Ешьте на здоровье! Ешьте на здоровье!

Простые способы, которые помогут избавиться от наеденных за зиму килограммов

Добрые советы
«Истинный сын американского Юга»: Мэттью Макконахи вспоминает советы мамы и детство в Техасе «Истинный сын американского Юга»: Мэттью Макконахи вспоминает советы мамы и детство в Техасе

Отрывок из дневников актера Мэттью Макконахи

Forbes
От записи рэпа в 2007-м до проектов с «Яндексом»​ и «Газпром нефтью»: как студия из Тольятти делает звуки для бизнеса От записи рэпа в 2007-м до проектов с «Яндексом»​ и «Газпром нефтью»: как студия из Тольятти делает звуки для бизнеса

Кто такие дизайнеры звука и сколько они зарабатывают

VC.RU
Правила жизни Мэтта Гроунинга Правила жизни Мэтта Гроунинга

Правила жизни создателя «Симпсонов» и «Футурамы» Мэтта Гроунинга

Esquire
Дакота Джонсон и Джейсон Сигел о настоящей дружбе, подлизах и мечтах Дакота Джонсон и Джейсон Сигел о настоящей дружбе, подлизах и мечтах

Интервью с Дакотой Джонсон и Джейсоном Сигелом

Cosmopolitan
«Часики тикают»: как отвечать на бестактные вопросы о личной жизни «Часики тикают»: как отвечать на бестактные вопросы о личной жизни

«Когда свадьба?», «Скоро обзаведетесь наследниками?», «Пойдете за вторым?»

Psychologies
Снова как девочки! 8 причесок, которые молодят звезд после 35 Снова как девочки! 8 причесок, которые молодят звезд после 35

Мы собрали самые удачные прически голливудских знаменитостей

Cosmopolitan
РПЦЗ и катакомбники: антисоветское православие РПЦЗ и катакомбники: антисоветское православие

В ХХ веке русское православие столкнулось с новым конфликтом

Weekend
Кто такой сигма-самец и что делать, если ты — он? Кто такой сигма-самец и что делать, если ты — он?

Одинокие волки: не менее сильные, чем альфа, но более независимые

Maxim
Мигрень: что нужно знать? Мигрень: что нужно знать?

Всё самое новое о профилактике и лечении мигрени

Домашний Очаг
Абьюз: как распознать моральное насилие и что делать Абьюз: как распознать моральное насилие и что делать

Как понять, что вы столкнулись с эмоциональным насилием в отношениях?

РБК
Варя, надежда, любовь Варя, надежда, любовь

Актриса Варвара Шмыкова говорит, что эмоции у нее всегда через край

Cosmopolitan
В атмосфере Венеры нет биомаркеров жизни: ошибка ученых В атмосфере Венеры нет биомаркеров жизни: ошибка ученых

Газ на Венере никак не связан с деятельностью живых микробов

Популярная механика
Как разговаривать с подростками о политике Как разговаривать с подростками о политике

Расскажи сыну про митинги, либерализм и демократию

Maxim
Три мысли о зрелом возрасте Три мысли о зрелом возрасте

Как принять свою новую идентичность и полюбить новую себя

Psychologies
Необычные блюда: треска в соусе мисо, шоколадный пирог и суп из потрохов Необычные блюда: треска в соусе мисо, шоколадный пирог и суп из потрохов

Алексей Зимин делится классными рецептами приготовления небанальных блюд

Cosmopolitan
Открыть в приложении