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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Дикие павианы не прошли зеркальный тест Дикие павианы не прошли зеркальный тест

Исследователи провели зеркальный тест на диких медвежьих павианах

N+1
Как говорить, чтобы тебя все слушали Как говорить, чтобы тебя все слушали

Как сделать так, чтобы тебя слушали в любой компании из 2, 17 и 639 человек

Maxim
Ученые переписали нейронауку: впервые обнаружены возможные основы человеческого интеллекта Ученые переписали нейронауку: впервые обнаружены возможные основы человеческого интеллекта

Ученые нашли, как нейроны в человеческом мозге хранят воспоминания

Inc.
Невероятная жизнь скрипача Оле Булла, которого называли «Элвисом XIX века» Невероятная жизнь скрипача Оле Булла, которого называли «Элвисом XIX века»

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

Maxim
Прививка от аллергии АСИТ — как она работает? Прививка от аллергии АСИТ — как она работает?

Вместо того чтобы смягчать симптомы аллергии, можно устранить причину

СНОБ
Почему мы заботимся о других в ущерб себе Почему мы заботимся о других в ущерб себе

Стоит ли забывать о собственных желаниях, ломать себя, чтобы угодить другому?

Psychologies
TESS нашел молодую экзопланетную систему в звездном потоке Рыбы-Эридан TESS нашел молодую экзопланетную систему в звездном потоке Рыбы-Эридан

Астрономы отыскали очень молодую экзопланетную систему

N+1
Для карьеры и не только: как научиться красиво говорить Для карьеры и не только: как научиться красиво говорить

Как научиться говорить красиво и правильно

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

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

VC.RU
Что не так с фильмом «Малкольм и Мари» от создателей «Эйфории» Что не так с фильмом «Малкольм и Мари» от создателей «Эйфории»

Режиссер Сэм Левинсон слишком увлекся саморефлексией

GQ
Nissan Qashqai заходит на третий круг Nissan Qashqai заходит на третий круг

Твоя будущая бывшая машина уже здесь

Maxim
Я мечтаю о дочке Я мечтаю о дочке

Певица Зара – о детстве, сыновьях и преимуществах зрелых родителей

Домашний Очаг
«Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи «Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи

Мария Максакова рассказала о своем скандальном браке с Денисом Вороненковым

Cosmopolitan
Как выглядят актеры дубляжа, чьими голосами по-русски говорят Шварценеггер, Скарлетт Йоханссон, Симпсоны и другие кинозвезды Как выглядят актеры дубляжа, чьими голосами по-русски говорят Шварценеггер, Скарлетт Йоханссон, Симпсоны и другие кинозвезды

Актеры дубляжа: ты узнавал их по голосу, а теперь будешь узнавать в лицо

Maxim
Правила жизни Бенисио Дель Торо Правила жизни Бенисио Дель Торо

Правила жизни актера Бенисио Дель Торо

Esquire
Сестра таланта Сестра таланта

В весенне-летних коллекциях о себе решили напомнить почти забытые нами мини-юбки

Vogue
Миллиардер Рубен Варданян инвестировал в сервис знакомств на основе ИИ iris Dating Миллиардер Рубен Варданян инвестировал в сервис знакомств на основе ИИ iris Dating

Бизнесмен Рубен Варданян стал акционером сервиса для знакомств iris Dating

Forbes
Уроки бизнеса в русской классике: как плохое ТЗ, русский комплекс неполноценности и скрепы привели к провалу Левши Уроки бизнеса в русской классике: как плохое ТЗ, русский комплекс неполноценности и скрепы привели к провалу Левши

Отрывок из книги «Бесполезная классика» Леонида Клейна

Inc.
14 дней спустя 14 дней спустя

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

N+1
Машины, которые не ломаются и много новинок. Главные автоновости недели Машины, которые не ломаются и много новинок. Главные автоновости недели

Состоялась премьера новых Nissan Qashqai и Mitsubishi Outlander

РБК
Мясное растениеводство Мясное растениеводство

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

Forbes
За что мы любим персонажей Андрея Мягкова За что мы любим персонажей Андрея Мягкова

Мягков у Рязанова играл советского человека таким, каким он был в своей массе

GQ
Сцепились языками Сцепились языками

Александр Добровинский объясняет, как в юности накопил большой словарный запас

Tatler
Правила жизни Айн Рэнд Правила жизни Айн Рэнд

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

Esquire
В главных ролях В главных ролях

Московская квартира с авангардными принтами для художницы по костюмам

AD
Удалили навсегда! Кто из звезд избавился от родинок, чтобы не рисковать Удалили навсегда! Кто из звезд избавился от родинок, чтобы не рисковать

Эти знаменитости убрали свои природные "метки" по медицинским показаниям

Cosmopolitan
Ученые смоделировали глобальную тектоническую историю Земли за миллиард лет Ученые смоделировали глобальную тектоническую историю Земли за миллиард лет

Глобальная реконструкция тектонических перемещений литосферных плит Земли

N+1
Астрономы впервые нашли гидрид хрома в атмосфере горячего юпитера Астрономы впервые нашли гидрид хрома в атмосфере горячего юпитера

Ученые изучили атмосферу горячего юпитера WASP-31b

N+1
Химики проследили за озоном в жилом доме Химики проследили за озоном в жилом доме

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

N+1
Биоинженерный суставной хрящ синтезировал для себя лекарство в ответ на нагрузку Биоинженерный суставной хрящ синтезировал для себя лекарство в ответ на нагрузку

Cоздан биоинженерный суставной хрящ на основе свиных клеток

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