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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Шимпанзе заразились зевотой от головы андроида Шимпанзе заразились зевотой от головы андроида

Шимпанзе способны заразиться зевотой от зевающей головы человекоподобного робота

N+1
В Китае все чаще меняют менеджеров на алгоритмы: те следят за работниками, дают им задачи и могут списать часть зарплаты В Китае все чаще меняют менеджеров на алгоритмы: те следят за работниками, дают им задачи и могут списать часть зарплаты

Автоматические системы штрафуют китайских работников за нарушения расписания

VC.RU
Ученые обнаружили древнего хищника с тремя глазами и зубастым ртом! Он жил 506 млн лет назад Ученые обнаружили древнего хищника с тремя глазами и зубастым ртом! Он жил 506 млн лет назад

В Берджесс нашли окаменелость необычного существа, жившего 506 млн лет назад

ТехИнсайдер
3D-печать удешевит создание ионных двигателей для кубсатов 3D-печать удешевит создание ионных двигателей для кубсатов

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

N+1
Как кофеин влияет на мозг и тело: неожиданные факты Как кофеин влияет на мозг и тело: неожиданные факты

Исследования выявили ряд интересных фактов, связанных с кофеином

Psychologies
История актрисы Наоми Гроссман, которая не боится быть смешной История актрисы Наоми Гроссман, которая не боится быть смешной

Наоми Гроссман — одна из самых смелых женщин современного кинематографа

Cosmopolitan
12 громких фактов о Джонни Кэше 12 громких фактов о Джонни Кэше

Исполнитель кантри, которого должен знать каждый россиянин, — Джонни Кэш

Maxim
Выжившие: как выглядели реальные герои фильмов про экстремальные путешествия Выжившие: как выглядели реальные герои фильмов про экстремальные путешествия

Прототипы героев фильмов о выживании и опасных путешествиях

Cosmopolitan
Как перестать учить английский и начать на нём говорить Как перестать учить английский и начать на нём говорить

Знание английского сегодня — ключ к миру

Inc.
«Да» значит «да», но можно передумать»: юрист Анна Ривина — о концепции согласия в отношениях «Да» значит «да», но можно передумать»: юрист Анна Ривина — о концепции согласия в отношениях

Как зафиксировать сексуальное согласие?

Forbes
Испанские страсти Испанские страсти

Певица Розалия готовит новый альбом, а в перерыве — выбирает наряды и пластинки

Vogue
Романтичные поступки, от которых не тошнит: 12 свежих идей для ценителей искренности Романтичные поступки, от которых не тошнит: 12 свежих идей для ценителей искренности

Идеи для тех, кто хочет сделать 14 февраля запоминающимся

Playboy
Перекачанные лица, или Overfilling: как выходят и чем грозят, знает косметолог Перекачанные лица, или Overfilling: как выходят и чем грозят, знает косметолог

Зачем так надуваться? Психологическая проблема или ошибка пластического хирурга?

Cosmopolitan
Химики создали искусственные сухожилия Химики создали искусственные сухожилия

Этот полимер, сравним по прочности, эластичности и долговечности с сухожилиями

N+1
Самые бесполезные вещи, за которые были заплачены баснословные деньги Самые бесполезные вещи, за которые были заплачены баснословные деньги

Список идиотских и безумно дорогих покупок

Maxim
Иногда они лопаются. Что делать во время биржевого краха Иногда они лопаются. Что делать во время биржевого краха

Когда на рынке начинается «цепная реакция», нет никаких «надежных» активов

СНОБ
7 очень странных исторических фактов о сексе 7 очень странных исторических фактов о сексе

Блесни эрудицией во время секса!

Maxim
Ночницы не почувствовали сладкого несмотря на наличие нужных рецепторов Ночницы не почувствовали сладкого несмотря на наличие нужных рецепторов

Почему ночницы утратили способность воспринимать сладкое

N+1
Женщины эмансипированы, а равенства нет: социолог — о гендерной повестке в России Женщины эмансипированы, а равенства нет: социолог — о гендерной повестке в России

Социолог Анна Темкина — о том, что мешает женщинам делать карьеру

Forbes
7 мистических находок археолога: куда пропала Клеопатра и что такое «воздушные змеи» пустыни 7 мистических находок археолога: куда пропала Клеопатра и что такое «воздушные змеи» пустыни

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

Популярная механика
20 самых мужских пород собак 20 самых мужских пород собак

Если решил завести собаку, то выбери достойную породу

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

Объясняем, почему сладкое может провоцировать зубную боль: основные причины

Playboy
«Были проблемы с деньгами»: близкий друг Андрея Мягкова о его последних годах «Были проблемы с деньгами»: близкий друг Андрея Мягкова о его последних годах

Георгий Штиль вспоминает давнего приятеля Андрея Мягкова

Cosmopolitan
За что мы любим персонажей Андрея Мягкова За что мы любим персонажей Андрея Мягкова

Мягков у Рязанова играл советского человека таким, каким он был в своей массе

GQ
В прокате «Родные» — удивительная народная комедия с Буруновым и Монеточкой. Рассказываем, почему ее стоит посмотреть В прокате «Родные» — удивительная народная комедия с Буруновым и Монеточкой. Рассказываем, почему ее стоит посмотреть

«Родные» — лихое и веселое роуд-муви, которое превращается в драму

Esquire
«Не нравится феминизм — учите матчасть»: Яна Чурикова — о равноправии, «людях из телека» и своем новом шоу «Не нравится феминизм — учите матчасть»: Яна Чурикова — о равноправии, «людях из телека» и своем новом шоу

Яна Чурикова — о том, как быть феминисткой в профессии, где оценивают внешность

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

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

Psychologies
Знаешь ли ты, как закончились сериалы нашего детства Знаешь ли ты, как закончились сериалы нашего детства

Что произошло в финале «Зачарованных» и «Санта-Барбары»?

Cosmopolitan
Пространство новых материалов Пространство новых материалов

Как один ученый придумал альтернативу таблице Менделеева

Популярная механика
История PortalPlayer — компании, которая разработала iPod для Apple и исчезла История PortalPlayer — компании, которая разработала iPod для Apple и исчезла

Ради Apple PortalPlayer отказалось от всех клиентов, но не удержалась на рынке

VC.RU
Открыть в приложении