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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Ионный кубит заставили работать по циклу Стирлинга Ионный кубит заставили работать по циклу Стирлинга

Намеренная дефазировка увеличила КПД квантового двигателя на два процента

N+1
По кусочку По кусочку

Есть ли какое-то объяснение привычки кусочничества?

Худеем правильно
От Марса до квантовой физики: 11 книг для любителей научной фантастики От Марса до квантовой физики: 11 книг для любителей научной фантастики

Что ждет человечество в будущем? Фантасты размышляют в своих книгах

Maxim
Любовь: вихрь эмоций или кропотливая работа? Любовь: вихрь эмоций или кропотливая работа?

Психолог: как отличить мечту о близости от реального чувства любви?

Psychologies
Время динозавров Время динозавров

Новая история древних ящеров

kiozk originals
Как писать американскую прозу: фрагмент эссе американского писателя и многолетнего автора Esquire Филипа Рота Как писать американскую прозу: фрагмент эссе американского писателя и многолетнего автора Esquire Филипа Рота

Фрагмент знаменитого эссе «Как писать американскую прозу» Филипа Рота

Esquire
Белковая диета – способ похудеть и удержать вес Белковая диета – способ похудеть и удержать вес

Белковая диета на две недели позволяет похудеть и долго удерживать вес

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

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

N+1
Девушка на Кубе Девушка на Кубе

Катя Бобкова позирует в горячей, солнечной и морской фотосессии

Maxim
Не хочу работать: 7 основных причин, почему не хочется трудиться, и способы борьбы с апатией Не хочу работать: 7 основных причин, почему не хочется трудиться, и способы борьбы с апатией

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

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

Жестокая правда о механизмах психологической защиты

Maxim
Материнский капитал Материнский капитал

Статус матери одного из самых богатых людей в мире Мэй Маск не устраивает

Robb Report
Честная практика Честная практика

Двенадцать откровенных вопросов актрисе Варваре Шмыковой

Cosmopolitan
«Погребальный звон по карьере Вуди Аллена»: на HBO вышло расследование о семье режиссера «Погребальный звон по карьере Вуди Аллена»: на HBO вышло расследование о семье режиссера

В чем суть конфликта в семье Вуди Аллена и как мир воспринял новое расследование

Forbes
Как увеличить глубокий сон: подробный рассказ о важной стадии ночного отдыха Как увеличить глубокий сон: подробный рассказ о важной стадии ночного отдыха

Определение глубокого сна и его значение для полноценного отдыха

Playboy
Как решить финансовые проблемы: руководство для тех, кто не хочет погрязнуть в долгах Как решить финансовые проблемы: руководство для тех, кто не хочет погрязнуть в долгах

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

Playboy
Как восстановить режим сна Как восстановить режим сна

Превратись из ворчливого полуночника в раннюю пташку!

Maxim
Цифровое бессмертие Цифровое бессмертие

Sensorium Galaxy – VR-платформа, которая способна преобразить нашу жизнь

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

Удалось однозначно определить энергию связи Ξ-гиперона с ядром

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

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

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

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

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

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

Maxim
«Не нравится феминизм — учите матчасть»: Яна Чурикова — о равноправии, «людях из телека» и своем новом шоу «Не нравится феминизм — учите матчасть»: Яна Чурикова — о равноправии, «людях из телека» и своем новом шоу

Яна Чурикова — о том, как быть феминисткой в профессии, где оценивают внешность

Forbes
Борщевик Сосновского: растение-терминатор или культура будущего Борщевик Сосновского: растение-терминатор или культура будущего

Борщевик — сорняк, с которым невозможно справиться

Наука
Физики подтвердили полиморфизм льда и открыли лед-XIX Физики подтвердили полиморфизм льда и открыли лед-XIX

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

N+1
Что посмотреть и попробовать в Туве. Гид «РБК Стиль» Что посмотреть и попробовать в Туве. Гид «РБК Стиль»

Гид по самой загадочной республике России, где есть ларьки и нет супермаркетов

РБК
Как девушкам с типом фигуры «груша» визуально «облегчить» низ — 6 лайфхаков Как девушкам с типом фигуры «груша» визуально «облегчить» низ — 6 лайфхаков

Гак гармонизировать пропорции фигуры «груша» с помощью одежды

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

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

Forbes
«Хорошо сохранилась»: что делает Дженнифер Энистон, чтобы круто выглядеть в 52 «Хорошо сохранилась»: что делает Дженнифер Энистон, чтобы круто выглядеть в 52

Любимые бьюти-приемы Дженнифер Энистон, помогающие ей выглядеть молодой

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

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

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