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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

В старой коллекции находок из Костёнок нашли три кроманьонских зуба В старой коллекции находок из Костёнок нашли три кроманьонских зуба

Ученые обнаружили три кроманьонских человеческих зуба в Костёнки-1

N+1
3 интересных научно-фантастических романа о людях, покинувших Землю 3 интересных научно-фантастических романа о людях, покинувших Землю

Книги, в которых Земля погибла

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

Ученые выяснили, что терапия артрита ингибиторами янус-киназы не провоцирует рак

N+1
Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги) Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги)

Фрагмент главы из книги Рока и Джона Позитано «Ужин с Ди Маджо»

Esquire
Иммунитет от хамства: как реагировать на грубость Иммунитет от хамства: как реагировать на грубость

Как защититься от хамства, не опускаясь до него?

Psychologies
Педофилия, инцест и еще 7 сексуальных табу, против которых борется современное общество Педофилия, инцест и еще 7 сексуальных табу, против которых борется современное общество

Узнай, чего боялись наши предки, и чего боятся до сих пор граждане разных стран

Maxim
Лоуренс Аравийский Лоуренс Аравийский

Война, ложь, имперская глупость и становление современного Ближнего Востока

kiozk originals
Выход из тупика: почему Голливуд все время снимает новые франшизы по старым блокбастерам Выход из тупика: почему Голливуд все время снимает новые франшизы по старым блокбастерам

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

Forbes
Осторожно! 10 популярных бьюти-процедур, которые могут обернуться кошмаром Осторожно! 10 популярных бьюти-процедур, которые могут обернуться кошмаром

Многие популярные процедуры все-таки лучше доверить профессионалам

Cosmopolitan
Не очевидно Не очевидно

Как выявлять тренды раньше других

kiozk originals
“Нам нравится щекотать друг другу мозг” “Нам нравится щекотать друг другу мозг”

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

Psychologies
Удивительная история LEGO: от деревянных уточек до робототехники Удивительная история LEGO: от деревянных уточек до робототехники

Сегодня мы расскажем эту удивительную историю – историю LEGO

Популярная механика
«Не хотим продавать бизнес»: братья из Вологды рассказали Тинькову о цели создать крупнейшую игровую компанию «Не хотим продавать бизнес»: братья из Вологды рассказали Тинькову о цели создать крупнейшую игровую компанию

Основатели Playrix решили сделать его самой дорогой игровой компанией в мире

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

Паттерны, которые не приносят удовольствия и разрушают отношения

Psychologies
Физики разработали самовосстанавливающиеся генераторы для носимой электроники Физики разработали самовосстанавливающиеся генераторы для носимой электроники

Ученые создали гибкий нательный генератор электричества

N+1
Спецотряд «Эльба»: первая атака немецких камикадзе Спецотряд «Эльба»: первая атака немецких камикадзе

Первая и последняя миссия немецкого спецотряда «Эльба»

Maxim
Экстремальные нагрузки вызвали появление аморфных фаз в высокоэнтропийном сплаве Экстремальные нагрузки вызвали появление аморфных фаз в высокоэнтропийном сплаве

Физики нашли аморфные зоны в кристаллической структуре металла под нагрузкой

N+1
Александра Ребенок: «Дома я перестаю быть воином» Александра Ребенок: «Дома я перестаю быть воином»

Интервью с актрисой Александрой Ребенок об активном материнстве и работе в кино

Cosmopolitan
Белковая диета: принципы, меню, научные факты Белковая диета: принципы, меню, научные факты

Как работает белковая диета

РБК
Палеонтолог вместо топ-модели: кто из детей fashion-красавиц не пошел на подиум Палеонтолог вместо топ-модели: кто из детей fashion-красавиц не пошел на подиум

Они могли бы сделать карьеру в мире высокой моды, но отказались

Cosmopolitan
Я не такая: каким женщинам не нужен феминизм Я не такая: каким женщинам не нужен феминизм

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

Psychologies
Правила жизни Юбера де Живанши Правила жизни Юбера де Живанши

Правила жизни модельера и основателя модного дома Givenchy Юбера де Живанши

Esquire
«Это не по-пацански»: 7 токсичных стереотипов, которые портят жизнь мужчинам «Это не по-пацански»: 7 токсичных стереотипов, которые портят жизнь мужчинам

Концепция «настоящего мужика» в нашем обществе претерпевает трансформацию

Playboy
Обычные фильмы от обычных режиссеров: Гордей Петрик о том, как в России, наконец, появилось жанровое кино Обычные фильмы от обычных режиссеров: Гордей Петрик о том, как в России, наконец, появилось жанровое кино

Нашему кино не хватает простых историй, рассказанных понятным киноязыком

СНОБ
Готовим за 30 минут: 5 рецептов быстрого и изысканного завтрака Готовим за 30 минут: 5 рецептов быстрого и изысканного завтрака

Пять рецептов необычных блюд, которые отлично подходят для завтрака

Cosmopolitan
25 спортивных подвигов 25 спортивных подвигов

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

Maxim
Изобрести велосипед на последней миле: как стартап из Краснодара вырос в 21 раз за счет ИИ и «ВкусВилла» Изобрести велосипед на последней миле: как стартап из Краснодара вырос в 21 раз за счет ИИ и «ВкусВилла»

Как стартап «Чекбокс» способен составить конкуренцию лидерам индустрии доставки

Forbes
Ма, ну сколько можно! Ма, ну сколько можно!

Мамочка, хватит уже критиковать подростка – дай ему возможность ошибаться

Лиза
Самый быстрорастущий дейтинг в мире: как Bumble пришел к IPO и почему непопулярен в России Самый быстрорастущий дейтинг в мире: как Bumble пришел к IPO и почему непопулярен в России

Сервис знакомств Bumble провел успешное IPO в Нью-Йорке

Forbes
10 мини-сериалов, на которые не жалко потратить хоть все выходные 10 мини-сериалов, на которые не жалко потратить хоть все выходные

Мини-сериал - идеальное блюдо выходного дня

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