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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Переплавка Луны омолодила ее на пару сотен миллионов лет Переплавка Луны омолодила ее на пару сотен миллионов лет

Планетологи заново оценили возраст Луны, теперь он составляет 4,43–4,53 млрд лет

N+1
Меню для комиссара Мегрэ Меню для комиссара Мегрэ

Рецепты из книги «Кухни знаменитых детективов» Алексея Биргера

СНОБ
Под замком Сфорца в Италии нашли тайные туннели: их описывал Леонардо да Винчи! Под замком Сфорца в Италии нашли тайные туннели: их описывал Леонардо да Винчи!

Как ученые смогли доказать, что под замком Сфорца существуют подземные туннели

ТехИнсайдер
Что наблюдать на небе в феврале: «весенние» галактики и Веста во Льве Что наблюдать на небе в феврале: «весенние» галактики и Веста во Льве

В феврале уже пора наблюдать «весенние» галактики

N+1
Как забыть мужчину, который загостил вас и исчез из вашей жизни Как забыть мужчину, который загостил вас и исчез из вашей жизни

Почему резкое исчезновение партнера может стать испытанием для психики?

Psychologies
Роман Балаян: «Не знаю, мое ли это призвание — режиссура, но мне она стала судьбой» Роман Балаян: «Не знаю, мое ли это призвание — режиссура, но мне она стала судьбой»

Режиссер Роман Балаян о съемках Алексея Германа и работе с Олегом Янковским

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

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

N+1
«Экономист под прикрытием. Почему возникают пробки, кофе стоит дорого и невозможно найти хорошую подержанную машину» «Экономист под прикрытием. Почему возникают пробки, кофе стоит дорого и невозможно найти хорошую подержанную машину»

Как водители влияют на окружающих?

N+1
Не только букеты в вазе: почему флористический декор стал интерьерным трендом и как украсить свой дом цветами Не только букеты в вазе: почему флористический декор стал интерьерным трендом и как украсить свой дом цветами

Как можно использовать цветы в украшении интерьера

Esquire
От Аньелли до Феррари: самые возрастные топ-менеджеры в истории автопрома От Аньелли до Феррари: самые возрастные топ-менеджеры в истории автопрома

Некоторые возглавляют свои компании до самой смерти

РБК
«Чахотка: другая история немецкого общества» «Чахотка: другая история немецкого общества»

Отрывок из книги Ульрике Мозер «Чахотка: другая история немецкого общества»

N+1
Сердце компании Сердце компании

Почему организационная культура значит больше, чем стратегия или финансы

kiozk originals
Предельный Туле Предельный Туле

Край мира: где его искать

Вокруг света
Молодежь против «жирных котов» с Уолл-стрит: как цифровое поколение меняет правила игры на рынке Молодежь против «жирных котов» с Уолл-стрит: как цифровое поколение меняет правила игры на рынке

Раздувание стоимости акций с помощью сетевых атак соблазняет многих

Forbes
Внедорожник быстрее Ferrari: тест-драйв GMC Typhoon Внедорожник быстрее Ferrari: тест-драйв GMC Typhoon

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

РБК
Задачи маршрутизации адаптировали к квантовым вычислениям Задачи маршрутизации адаптировали к квантовым вычислениям

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

N+1
Попутная нефтяная энергия Попутная нефтяная энергия

Чашкинская ГТЭС в Пермском крае будет перерабатывать попутный нефтяной газ

Наука
«Рыцари справедливости» – фильм-притча, который притворяется боевиком «Рыцари справедливости» – фильм-притча, который притворяется боевиком

«Рыцари справедливости» доказывают, что жизнь – это хаос

GQ
Ретабло – древнейшее из искусств Ретабло – древнейшее из искусств

Ретабло – картины, которые жертвуют церквям в благодарность о помощи святых

Вокруг света
Байден заставляет Израиль нервничать Байден заставляет Израиль нервничать

Как новая американская администрация пересмотрит взаимоотношения с Израилем

Эксперт
Платья-кольчуги, модная революция и «Барбарелла»: что нужно знать о дизайнере Пако Рабане Платья-кольчуги, модная революция и «Барбарелла»: что нужно знать о дизайнере Пако Рабане

Пако Рабан — основатель модного футуризма шестидесятых

Esquire
«Искусство статистики. Как находить ответы в данных» «Искусство статистики. Как находить ответы в данных»

Выводы из данных — процесс «индуктивного умозаключения»

N+1
Катя Смольникова Катя Смольникова

Инженер-физик колдует над мультикремами, которые не перекраивают ваше лицо

Собака.ru
Правила жизни Пэрис Хилтон Правила жизни Пэрис Хилтон

Правила жизни светской львицы Пэрис Хилтон

Esquire
Как позволить себе стать собой и изменить жизнь Как позволить себе стать собой и изменить жизнь

Как найти свое место в потоке жизни, как узнать, куда плыть?

Psychologies
Осип Мандельштам Осип Мандельштам

Правила жизни Осипа Мандельштама

Esquire
Вкусные ловушки Вкусные ловушки

Избыток жиров и сахара бывает и в продуктах, на которые сразу и не подумаешь

Лиза
Яйцеклетка — что нужно знать? Яйцеклетка — что нужно знать?

Яйцеклетка — самая крупная клетка твоего организма

Cosmopolitan
Золотой фонд цитат: как твиты Илона Маска влияют на рынок Золотой фонд цитат: как твиты Илона Маска влияют на рынок

Самые известные и неоднозначные высказывания Илона Маска в Twitter

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

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

Вокруг света
Открыть в приложении