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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

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

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

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

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

Playboy
Речь пациента после инсульта отражает адаптивную стратегию мозга Речь пациента после инсульта отражает адаптивную стратегию мозга

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

TechInsider
Устрашающие факты об Элисе Купере Устрашающие факты об Элисе Купере

Элис Купер — самый жуткий рокер этой планеты

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

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

CHIP
Новая этика или новый тоталитаризм? Куда делась свобода слова в интернете Новая этика или новый тоталитаризм? Куда делась свобода слова в интернете

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

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

Рассказ о традиционном корейском алкогольном напитке

Playboy
Эффект Netflix: как сериалы делают модными шахматы и помогают продавать кроссовки Эффект Netflix: как сериалы делают модными шахматы и помогают продавать кроссовки

Современные сериалы могут поднять продажи чего угодно

Forbes
Они этого не скрывают! Российские звезды, которые признались в пластике Они этого не скрывают! Российские звезды, которые признались в пластике

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

Cosmopolitan
Когда ресницы нужно срочно снимать: SOS-сигналы, которые они тебе посылают Когда ресницы нужно срочно снимать: SOS-сигналы, которые они тебе посылают

Лэшмейкер рассказывает обо всем, что нужно знать перед наращиванием ресниц

Cosmopolitan
Спектр железа в космических лучах оказался непохож на спектры других тяжелых элементов Спектр железа в космических лучах оказался непохож на спектры других тяжелых элементов

Железо отнесли к одному классу космических лучей с более легкими частицами

N+1
Веселая вдова: лучшая роль Мишель Пфайффер — женщина, которая неудачно спланировала свою смерть Веселая вдова: лучшая роль Мишель Пфайффер — женщина, которая неудачно спланировала свою смерть

Почему фильм «Уйти не прощаясь» может принести «Оскар» Мишель Пфайффер

Forbes
Бадомедики Бадомедики

Что такое БАДы и что с ними делать?

Maxim
Зимние встречи на Алтае Зимние встречи на Алтае

На путешествие в Горный Алтай имеет смысл настроиться заранее

Наука и жизнь
В Стэнфорде назвали 4 причины «усталости от Zoom» и способы ее предотвратить В Стэнфорде назвали 4 причины «усталости от Zoom» и способы ее предотвратить

4 основные причины, по которым видеоконференции утомляют людей

Inc.
Роскошные платья, любовь и настоящие мужчины: 15 захватывающих ретросериалов Роскошные платья, любовь и настоящие мужчины: 15 захватывающих ретросериалов

Подборка ретросериалов, где время становится одним из действующих лиц

Cosmopolitan
9 лучших игр для двоих: свежие идеи для домашнего свидания 9 лучших игр для двоих: свежие идеи для домашнего свидания

Хватит залипать в сериалы!

Playboy
5 лучших хорроров, чтобы не скучать в пандемию: часть 1 5 лучших хорроров, чтобы не скучать в пандемию: часть 1

Лучшие книги для того, чтобы пощекотать себе нервы

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

Как в 50 выглядеть на 30

Добрые советы
Школа рисования Школа рисования

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

Лиза
Супы полезны для здоровья? Супы полезны для здоровья?

Теплая и жидкая еда ничуть не лучше и не хуже, чем твердая и холодная

Reminder
Сильный бренд, но слабый бизнес: Gibson за 127 лет производства гитар не раз сталкивалась с проблемами, но выжила Сильный бренд, но слабый бизнес: Gibson за 127 лет производства гитар не раз сталкивалась с проблемами, но выжила

История самого известного гитарного бренда Gibson

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

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

Cosmopolitan
«Делаю древнюю мудрость актуальной»: бывший монах из списка Forbes советует, как прокачать свою жизнь «Делаю древнюю мудрость актуальной»: бывший монах из списка Forbes советует, как прокачать свою жизнь

Качества, которые открывают двери к любым целям

Forbes
Композитор Игорь Яковенко — о музыкальных шифрах, притворстве и джазе Композитор Игорь Яковенко — о музыкальных шифрах, притворстве и джазе

Композитор Игорь Яковенко — о Бенджамине Бриттене и звуках, которые не замечаешь

РБК
Спанкинг: как правильно шлепать девушку, чтобы ей это понравилось Спанкинг: как правильно шлепать девушку, чтобы ей это понравилось

Спанкинг — не просто жарко, а обжигающе горячо

Playboy
Красота неземная: где лучше всего на нашей планете наблюдать звездное небо Красота неземная: где лучше всего на нашей планете наблюдать звездное небо

На Земле еще есть места, где можно восхититься красотой звезд

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

Дмитрий Брейтенбихер о том, как зарабатывать в эпоху интеллектуальной экономики

Esquire
Главный российский фильм года «Пугало» вышел в прокат Главный российский фильм года «Пугало» вышел в прокат

Мрачное, таинственное, мистическое кино из Якутии

СНОБ
И в шутку, и всерьез. Премьера по пьесе Ивана Вырыпаева на сцене «Современника» И в шутку, и всерьез. Премьера по пьесе Ивана Вырыпаева на сцене «Современника»

Спектакль «Иллюзии» — несколько историй любви длиною в жизнь

СНОБ
Открыть в приложении