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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

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

Богатая микофлора носа повышает вероятность развития аллергии и  астмы

N+1
GTA V: минимальные системные требования для комфортной игры GTA V: минимальные системные требования для комфортной игры

Требования для GTA V, которые определил разработчик

CHIP
Японцы сделали роборуку с человеческими мышцами Японцы сделали роборуку с человеческими мышцами

Японские инженеры разработали биогибридную руку с человеческими мышцами

N+1
Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года

Символ советского туризма обернулся сотней пострадавших и погибших

Maxim
Как научиться довольствоваться тем, что есть, и перестать сравнивать свою жизнь с чужими Как научиться довольствоваться тем, что есть, и перестать сравнивать свою жизнь с чужими

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

ТехИнсайдер
«Я не могу без тебя»: о чем говорит это послание? «Я не могу без тебя»: о чем говорит это послание?

Психиатр — о том, что такое расстройство сепараторной тревоги

Psychologies
В Китае все чаще меняют менеджеров на алгоритмы: те следят за работниками, дают им задачи и могут списать часть зарплаты В Китае все чаще меняют менеджеров на алгоритмы: те следят за работниками, дают им задачи и могут списать часть зарплаты

Автоматические системы штрафуют китайских работников за нарушения расписания

VC.RU
Правила жизни Мэтта Гроунинга Правила жизни Мэтта Гроунинга

Правила жизни создателя «Симпсонов» и «Футурамы» Мэтта Гроунинга

Esquire
Геополитические конфликты из-за энергетической безопасности Геополитические конфликты из-за энергетической безопасности

Отрывок из книги Дэниела Ергина «Новая карта мира»

СНОБ
Каким получился фильм Ренаты Литвиновой «Северный ветер» Каким получился фильм Ренаты Литвиновой «Северный ветер»

Из чего сплетена история в фильме «Северный ветер»

РБК
«Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи «Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи

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

Cosmopolitan
Практика большого взрыва Практика большого взрыва

Мадс Миккельсен снова пытается применить на практике одну научную теорию

СНОБ
Длиннорогие ватуси Длиннорогие ватуси

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

Наука и жизнь
“Я вышла замуж по расчету” “Я вышла замуж по расчету”

Юлия Эльдеева слушала не веление сердца, а голос рассудка

Psychologies
Как игра разработчиков из Нижнего Новгорода попала в Apple Arcade Как игра разработчиков из Нижнего Новгорода попала в Apple Arcade

Как трем любителям игр из России удалось влюбить в себя мировой рынок

РБК
Почему наша целеустремленность обусловлена эволюцией? Отрывок из книги «Что такое жизнь?» нобелевского лауреата Пола Нерса Почему наша целеустремленность обусловлена эволюцией? Отрывок из книги «Что такое жизнь?» нобелевского лауреата Пола Нерса

Фрагмент главы из книги «Что такое жизнь? Понять биологию за пять простых шагов»

Esquire
Президент «Рив Гош» Эдгар Шабанов — о будущем компании Президент «Рив Гош» Эдгар Шабанов — о будущем компании

В каком направлении будет развиваться парфюмерно-косметическая сеть «Рив Гош»

РБК
Мадс Миккельсен: «История русских — это драма. Но вы умеете видеть свет даже в самой темной дыре» Мадс Миккельсен: «История русских — это драма. Но вы умеете видеть свет даже в самой темной дыре»

Мадс Миккельсен — о черной комедии из Скандинавии «Рыцари справедливости»

Esquire
Все о звездах сериала Все о звездах сериала

Что происходит в личной жизни актеров, сыгравших в популярном ситкоме?

Cosmopolitan
«Не только ради себя»: как Билл Гейтс продолжает борьбу с климатическими изменениями «Не только ради себя»: как Билл Гейтс продолжает борьбу с климатическими изменениями

У Билла Гейтса есть план по спасению планеты

Forbes
Как живут отцы, воспитывающие особенных детей Как живут отцы, воспитывающие особенных детей

Рассказываем о настоящих мужчинах, которые каждый день борются за своих детей

GQ
Синдром отличника Синдром отличника

Актер «Гоголь-центра» Михаил Тройник — о выборе, искусстве и точных науках

OK!
Опасные гидраты и где они обитают Опасные гидраты и где они обитают

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

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

Жизнь большой «литературной коммуналки» с ее скандалами и творческими вечерами

Караван историй
Какую профессию выбрать: руководство для тех, кто еще не определился с призванием Какую профессию выбрать: руководство для тех, кто еще не определился с призванием

Присмотрись к нашим рекомендациям, если ты до сих пор недоволен своей работой

Playboy
Физики измерили асимметрию антикварков внутри протона Физики измерили асимметрию антикварков внутри протона

Асимметрия в распределении верхних и нижних антикварков внутри протона

N+1
«Я смог бы сыграть всё» «Я смог бы сыграть всё»

Почему Антон Шагин не снимается в рекламе и не повторяется в ролях

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

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

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

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

Maxim
31 способ понять, что за человек перед вами 31 способ понять, что за человек перед вами

Несколько особенностей поведения, которые приоткроют тайну личности близкого

Psychologies
Открыть в приложении