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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

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

Какие ужасные вещи назвали главными последствиями засух

N+1
Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы

Отрывок из книги «Я так не хотела» адвоката Кэрри Голдберг об интернет-троллях

Forbes
Каннибалы 5600 лет назад съели в Атапуэрке 11 человек Каннибалы 5600 лет назад съели в Атапуэрке 11 человек

Ученые проанализировали многочисленные человеческие кости из пещеры Эль-Мирадор

N+1
Вселенная Эдгара По Вселенная Эдгара По

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

Наука и жизнь
«Был честен с собой и со своим ремеслом»: каким был путь в искусстве Карла Брюллова «Был честен с собой и со своим ремеслом»: каким был путь в искусстве Карла Брюллова

Каким был путь в искусстве Карла Брюллова и как его показывают в музеях

Forbes
Эффектный конский хвост: 10 крутых идей для самой удобной прически Эффектный конский хвост: 10 крутых идей для самой удобной прически

Если обычный конский хвост — это слишком скучно, то попробуй наши варианты

Cosmopolitan
Что написать в сообщении после первого свидания? 8 советов от девушек Что написать в сообщении после первого свидания? 8 советов от девушек

Как закрепить хорошее впечатление после приятной встречи

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

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

Популярная механика
Химики проследили за озоном в жилом доме Химики проследили за озоном в жилом доме

Большой вклад в химию озона в доме вносят кожные жиры людей

N+1
Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple

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

VC.RU
Почему твой бывший совершенно точно «не торт» с точки зрения астрологии Почему твой бывший совершенно точно «не торт» с точки зрения астрологии

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

Cosmopolitan
Свободные взгляды Свободные взгляды

Режиссеры фильма «Дом Кардена» приглашают в путешествие по вселенной дизайнера

Vogue
Cosmo TV: 9 звездных пар, где мужчина сильно младше Cosmo TV: 9 звездных пар, где мужчина сильно младше

Несколько примеров звездных пар, в чьих отношениях мужчина младше своей женщины.

Cosmopolitan
Водка у таксистов, или Что роднило СССР и Великобританию Водка у таксистов, или Что роднило СССР и Великобританию

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

СНОБ
Зимние встречи на Алтае Зимние встречи на Алтае

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

Наука и жизнь
Магический реализм Магический реализм

Флоренс Уэлч, солистка Florence + the Machine, околдовала мир своим голосом

Glamour
Антидепрессант остановил разрушение хрящей при остеоартрите Антидепрессант остановил разрушение хрящей при остеоартрите

Пароксетин может стать препаратом для лечения остеоартрита

N+1
Гнезда ос помогли выявить старейший наскальный рисунок кенгуру Гнезда ос помогли выявить старейший наскальный рисунок кенгуру

В Австралии около 17300 лет назад впервые нарисовали кенгуру

N+1
Как скрыть номер в Телеграм: инструкция для смартфонов и ПК Как скрыть номер в Телеграм: инструкция для смартфонов и ПК

Разбираемся, как скрыть от контактов в Телеграм номер телефона

CHIP
«Нищебродов прошу не писать»: могут ли деньги сделать вас настоящим мужчиной «Нищебродов прошу не писать»: могут ли деньги сделать вас настоящим мужчиной

Григорий Туманов — о том, как связаны маскулинность и деньги

Forbes
«Кажется, я чувствую себя хуже, чем когда-либо в жизни»: репортаж Forbes из очереди к спецприемнику в Сахарово «Кажется, я чувствую себя хуже, чем когда-либо в жизни»: репортаж Forbes из очереди к спецприемнику в Сахарово

Фоторепортаж Forbes из очереди к спецприемнику в деревне Сахарово

Forbes
Приз за подписку: как устроены и чем оборачиваются розыгрыши в Instagram Приз за подписку: как устроены и чем оборачиваются розыгрыши в Instagram

Как устроены гивы в инстаграме и почему вокруг них так много скандалов?

РБК
8 звезд, у которых неидеальные стопы. Но они вообще не комплексуют! 8 звезд, у которых неидеальные стопы. Но они вообще не комплексуют!

Если ты переживаешь из-за своей внешности, бери пример с голливудских богинь

Cosmopolitan
Как поступить в сложной ситуации? Подскажут метафорические карты Как поступить в сложной ситуации? Подскажут метафорические карты

Метафорические карты помогут определить свою позицию накануне важного события

Psychologies
Роман Должанский: По России с любовью. Сад камней. Нерехта Роман Должанский: По России с любовью. Сад камней. Нерехта

Очерк Романа Должанского о старинном городе Нерехта

СНОБ
Тюркские юрты, саамский футбол, хоомей и тихий Дон: куда поехать, чтобы познакомиться с культурой народов России Тюркские юрты, саамский футбол, хоомей и тихий Дон: куда поехать, чтобы познакомиться с культурой народов России

Пять российских этнопарков, раскрывающих разные стороны России

Forbes
Распределенные вычисления на компьютерах добровольцев помогли найти новый пульсар-«черную вдову» Распределенные вычисления на компьютерах добровольцев помогли найти новый пульсар-«черную вдову»

Он разрушает своего маломассивного компаньона

N+1
Стрижка не удалась? Как выйти из салона довольной волосами — 5 советов мастера Стрижка не удалась? Как выйти из салона довольной волосами — 5 советов мастера

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

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

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

Cosmopolitan
Герпетологи уличили три вида змей в потрошении лягушек и жаб Герпетологи уличили три вида змей в потрошении лягушек и жаб

Герпетологи описали необычное охотничье поведение змей из рода Oligodon

N+1
Открыть в приложении