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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Аммиак из пингвиньего гуано внес вклад в формирование облаков над Антарктидой Аммиак из пингвиньего гуано внес вклад в формирование облаков над Антарктидой

Из-за чего падает облачность в Антарктике?

N+1
Mazda CX-30: модель минус-сайз Mazda CX-30: модель минус-сайз

Самая обаятельная и привлекательная Mazda CX-30!

Maxim
Оригами-робота научили прижимать ноги и ходить по-крабьи Оригами-робота научили прижимать ноги и ходить по-крабьи

Инженер из Германии разработал четвероногого оригами-робота Fold Walker

N+1
Мне надо сейчас Мне надо сейчас

Известный фотограф Ольга Павлова – о том, как случайно найти свое призвание

Домашний Очаг
«Эффект кислого винограда»: как неудачи и страх провала мешают нам исполнять мечты «Эффект кислого винограда»: как неудачи и страх провала мешают нам исполнять мечты

Почему мы бессознательно обесцениваем то, что раньше вдохновляло?

Forbes
Управляя гневом Управляя гневом

Чему Кэри Маллиган научилась у своей новой героини?

OK!
Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT

Биткоин-элита тратит миллионы долларов на покупку цифрового искусства

Inc.
«Хрупкость человечества будет обсуждаться еще много лет»: большое интервью Дмитрия Озеркова «Хрупкость человечества будет обсуждаться еще много лет»: большое интервью Дмитрия Озеркова

Дмитрий Озерков — о «новой тактильности» и будущем Дома Радио

Школа Masters
Как тиктокер Костя Киевский попал под статью за хулиганство на протестах и набрал 800 000 подписчиков Как тиктокер Костя Киевский попал под статью за хулиганство на протестах и набрал 800 000 подписчиков

Что грозит Косте Киевскому после ареста и как складывалась карьера тиктокера?

Forbes
Как птичий помет превратил самую страшную пустыню в оазис Как птичий помет превратил самую страшную пустыню в оазис

Как самая сухая пустыня в мире может быть плодородной

Популярная механика
Магнитная. Тайны космических всплесков Магнитная. Тайны космических всплесков

Магнетары — нейтронные звезды, помогающие раскрыть загадки космоса

Наука и жизнь
Правила жизни Айн Рэнд Правила жизни Айн Рэнд

Писатель, скончалась в 1982 году в Нью-Йорке

Esquire
Поверх барьеров Поверх барьеров

9 мостов, представляющих культурное наследие человечества

Вокруг света
Персона Персона

О необычных запросах клиентов и репутации русских александритов

Robb Report
Новый робот борозды не испортит Новый робот борозды не испортит

В сельском хозяйстве хозяйничают роботы и все самые фантастические технологии!

Maxim
Праздник женских удовольствий: 24 часа только для себя Праздник женских удовольствий: 24 часа только для себя

Перезагрузиться и расслабиться душой и телом мы вполне можем за один день

Psychologies
Парад планет и полный хаос: найдена самая странная звездная система Парад планет и полный хаос: найдена самая странная звездная система

Астрономы обнаружили, что планеты совершают своего рода «танец»

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

MAXIM вспоминает героические моменты спорта

Maxim
Джентльмен в деталях: почему Кларк Гейбл безупречно выглядел — в костюме и не только Джентльмен в деталях: почему Кларк Гейбл безупречно выглядел — в костюме и не только

Кларк Гейбл одевался как образцовый джентльмен, а секрет его стиля был в деталях

Esquire
Отрывок из книги Дэвида Дарлинга и Агниджо Банерджи «Эта странная математика» Отрывок из книги Дэвида Дарлинга и Агниджо Банерджи «Эта странная математика»

Парадокс и его магия

СНОБ
Актер + актриса: почему распадаются красивые звездные пары Актер + актриса: почему распадаются красивые звездные пары

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

Cosmopolitan
Глобальный стендап: зачем нужна и чем хороша новая соцсеть ClubHouse Глобальный стендап: зачем нужна и чем хороша новая соцсеть ClubHouse

ClubHouse — новый культурный феномен или очередной IT-пшик?

Esquire
Говорить ли с детьми о политике? Говорить ли с детьми о политике?

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

Psychologies
Стать лучше! Стать лучше!

15 практик для построения продуктивных отношений на работе

kiozk originals
Влияет ли форма бюстгальтера на здоровье груди Влияет ли форма бюстгальтера на здоровье груди

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

Psychologies
Петров, Хабенский, Аксенова и другие: актеры из простых семей и их родители Петров, Хабенский, Аксенова и другие: актеры из простых семей и их родители

Талант — не всегда генетика, что доказывают российские артисты из простых семей

Cosmopolitan
Картины маслом: шесть самых неловких ситуаций в жизни мужчины глазами художника Картины маслом: шесть самых неловких ситуаций в жизни мужчины глазами художника

Живопись и жизнь: неловкие ситуации в картинах

Maxim
10 фильмов о любви, которые заменят поход к семейному психологу 10 фильмов о любви, которые заменят поход к семейному психологу

10 фильмов, которые стоит посмотреть вдвоем

Cosmopolitan
Прощайте, роботы: за что мы любим Daft Punk Прощайте, роботы: за что мы любим Daft Punk

Чем запомнится дуэт Daft Punk

Esquire
Зачем ученые подсчитывают фекалии рыб в мировом океане Зачем ученые подсчитывают фекалии рыб в мировом океане

Рыбные фекалии полны углерода, а океан полон фекалий

Популярная механика
Открыть в приложении