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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

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

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

N+1
В системе Альфа Центавра обнаружили слабый сигнал. Это может быть прямым наблюдением экзопланеты В системе Альфа Центавра обнаружили слабый сигнал. Это может быть прямым наблюдением экзопланеты

Ученые с осторожностью заявляют о возможном прорывном открытии в астрономии

National Geographic
Загробный мир британцев бронзового века оказался перевернут вверх ногами Загробный мир британцев бронзового века оказался перевернут вверх ногами

Британцы бронзового века представляли загробный мир как жизнь вниз головой

N+1
Американские орнитологи опровергли эффект стола для пикников в Патагонии Американские орнитологи опровергли эффект стола для пикников в Патагонии

Редкие залетные птицы — не показатель присутствия новых видов

N+1
Как и где быстро заработать денег: 13 легальных и проверенных способов Как и где быстро заработать денег: 13 легальных и проверенных способов

Подборка вариантов подработки, помогающей быстро и просто увеличить свой доход

Playboy
Одна вокруг света: встреча с бизонами и несанкционированная ночевка в Йеллоустоуне Одна вокруг света: встреча с бизонами и несанкционированная ночевка в Йеллоустоуне

106-я серия о кругосветном путешествии москвички и ее собаки Греты

Forbes
Как выглядят анчар, мандрагора и другие таинственные растения, которые ты встречал в книгах Как выглядят анчар, мандрагора и другие таинственные растения, которые ты встречал в книгах

И это не только цветочки!

Maxim
Не давить, дома не лечить: что сегодня нужно знать об акне Не давить, дома не лечить: что сегодня нужно знать об акне

Разбираемся в причинах возникновения акне и в вариантах решения этой проблемы

РБК
Нейтральная территория Нейтральная территория

Бренды, выпускающие гендерно-нейтральную косметику

Glamour
Принцип 80/20 Принцип 80/20

Как достичь большего с наименьшими усилиями

kiozk originals
Как расслабить шею: 5 способов справиться с напряжением Как расслабить шею: 5 способов справиться с напряжением

Как расслабить шею в домашних условиях

Cosmopolitan
Мастер спора международного класса Мастер спора международного класса

Главный спорщик XX века Амарилло Слим прославился невероятными пари

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

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

N+1
Искусственный интеллект Искусственный интеллект

Развитие Т-14 продолжается как в плане технологий, так и в плане боеприпасов

Популярная механика
Робот – лучший повар Робот – лучший повар

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

Популярная механика
Прекращайте уже мечтать о романтических поездках за границу Прекращайте уже мечтать о романтических поездках за границу

C милым рай не на шезлонгах в Дубае, а в ОВД городского округа Химки

GQ
40 лет — ни мужа, ни наследства: Пэрис Хилтон и ее необычная судьба 40 лет — ни мужа, ни наследства: Пэрис Хилтон и ее необычная судьба

Чем прославилась Пэрис Хилтон и почему до сих пор не устроила личную жизнь?

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

Достойный ответ «зеленой» политике Брюсселя

СНОБ
11 продуктов питания, которые ученые советуют избегать 11 продуктов питания, которые ученые советуют избегать

Какие именно “плохие” продукты вредят нашему здоровью?

Популярная механика
Прокатимся на автоприцепе по Берлину Прокатимся на автоприцепе по Берлину

Производитель специальной грузовой техники «Бонум» планирует выйти в Европу

Эксперт
«Моего оптимизма хватит на двоих»: история мамы, чья дочь победила рак «Моего оптимизма хватит на двоих»: история мамы, чья дочь победила рак

История мамы и ее дочери, которые сумели победить рак благодаря оптимизму

Psychologies
«Пропавшую» австралийскую пчелу нашли спустя 100 лет с момента последнего наблюдения «Пропавшую» австралийскую пчелу нашли спустя 100 лет с момента последнего наблюдения

Обнаружены редчайшие пчелы Pharohylaeus lactiferus

National Geographic
Зоологи допустили существование сумчатых волков в наши дни Зоологи допустили существование сумчатых волков в наши дни

Скорее всего, этот вид вымер не в 1936 года, а на рубеже 1990-2000 годов

N+1
Найдена замена кремнию: началась эра пoсткремниевой фотоники Найдена замена кремнию: началась эра пoсткремниевой фотоники

Дисульфид молибдена позволяет создать миниатюрные оптические устройства

Популярная механика
Смертельные укусы Смертельные укусы

Ежегодно змеи убивают более 100 тысяч человек

National Geographic
В гармонии с собой В гармонии с собой

Психическая саморегуляция: 10 техник для улучшения самочувствия и настроения

Лиза
Три мысли о зрелом возрасте Три мысли о зрелом возрасте

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

Psychologies
«Мне больно, когда выбирают другого»: есть ли польза от ревности? «Мне больно, когда выбирают другого»: есть ли польза от ревности?

Психолог: почему мы ревнуем и что с этим делать?

Psychologies
В Дании представили ветровую турбину с рекордной длиной лопасти В Дании представили ветровую турбину с рекордной длиной лопасти

Это самый мощный агрегат в ветроэнергетической отрасли

National Geographic
Январь 2021 года оказался одним из самых теплых в истории наблюдений Январь 2021 года оказался одним из самых теплых в истории наблюдений

Январь 2021 года занял седьмое место среди всех январей за 142 года

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