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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Астрономы увидели старт образования экзопланет в протопланетном диске Астрономы увидели старт образования экзопланет в протопланетном диске

Как образовываются твердые тела в диске протозвезды

N+1
Неизвестные X и Y Неизвестные X и Y

Как и, главное, зачем природа разделила обитателей земли на юношей и девушек

Вокруг света
Дрейф континентов 2.0: как будет выглядеть Земля через миллионы лет — рассказывает геолог Дрейф континентов 2.0: как будет выглядеть Земля через миллионы лет — рассказывает геолог

Покопаемся в геологическом прошлом и будущем нашей Земли

ТехИнсайдер
Как игра разработчиков из Нижнего Новгорода попала в Apple Arcade Как игра разработчиков из Нижнего Новгорода попала в Apple Arcade

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

РБК
Эмоциональный интеллект Эмоциональный интеллект

Новое представление о том, что значит быть «умным»

kiozk originals
Паразительная медицина Паразительная медицина

Откуда взялась идея лечиться кишечными червями

N+1
Разговор на кухне Разговор на кухне

О самых свежих трендах в организации кухонных пространств

SALON-Interior
Mustang против Camaro: шесть раундов за титул лучшего пони-кара в истории Mustang против Camaro: шесть раундов за титул лучшего пони-кара в истории

Это соперничество по крутости запросто сравнится с дерби «Спартак» – ЦСКА

Популярная механика
Японцы понаблюдали за объедающими друг другу крылья самками и самцами азиатского таракана Японцы понаблюдали за объедающими друг другу крылья самками и самцами азиатского таракана

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

N+1
Квантовую голограмму получили без сложения волн Квантовую голограмму получили без сложения волн

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

N+1
8 способов развить креативное мышление 8 способов развить креативное мышление

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

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

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

N+1
Новый робот борозды не испортит Новый робот борозды не испортит

В сельском хозяйстве хозяйничают роботы и все самые фантастические технологии!

Maxim
Линия нижнего белья от Рианны привлекла $115 млн на фоне новостей о закрытии ее модного дома Линия нижнего белья от Рианны привлекла $115 млн на фоне новостей о закрытии ее модного дома

Бренд Рианны привлек миллионные инвестиции

Forbes
Главный российский фильм года «Пугало» вышел в прокат Главный российский фильм года «Пугало» вышел в прокат

Мрачное, таинственное, мистическое кино из Якутии

СНОБ
Ловушка самоуспокоения: почему мы в нее попадаем и как оттуда выбраться Ловушка самоуспокоения: почему мы в нее попадаем и как оттуда выбраться

Тревожные мысли порой одолевают каждого

Psychologies
«Хочу перестать каждый день плакать»: Ольга Бузова о жизни после разрыва с Давой «Хочу перестать каждый день плакать»: Ольга Бузова о жизни после разрыва с Давой

Ольга Бузова призналась, что не считает себя сильной женщиной

Cosmopolitan
Мертвые амебы, негативщики и нытики: как выстраивать отношения с проблемными сотрудниками Мертвые амебы, негативщики и нытики: как выстраивать отношения с проблемными сотрудниками

Отрывок из книги «Сложные подчиненные» Максима Батырева

Forbes
Физики описали еще один способ получения энергии из черных дыр Физики описали еще один способ получения энергии из черных дыр

Физики: найден новый способ извлечь энергию из вращающейся черной дыры

N+1
Жан-Кристоф Гранже: День праха Жан-Кристоф Гранже: День праха

Первая глава романа Жана-Кристофа Гранже «День праха»

СНОБ
Сергей Зверев, Илья Лагутенко и принцы — 15 знаменитых мужчин, служивших в армии Сергей Зверев, Илья Лагутенко и принцы — 15 знаменитых мужчин, служивших в армии

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

Cosmopolitan
Пригнать машину из Европы: реальные цены и все варианты Пригнать машину из Европы: реальные цены и все варианты

Все, что официально не поставляется в Россию, но доступно для покупки

РБК
Леонардо ДиКаприо, Криштиану Роналду и другие секс-символы, обожающие своих мам Леонардо ДиКаприо, Криштиану Роналду и другие секс-символы, обожающие своих мам

Эти роковые покорители сердец всю жизнь остаются преданны одной женщине - маме

Cosmopolitan
Как программист с Украины и экс-партнер Маска стал новым долларовым миллиардером Как программист с Украины и экс-партнер Маска стал новым долларовым миллиардером

Макс Левчин — революционер на рынке потребительского кредитования

Forbes
Не пытайтесь мотивировать сотрудников страхом. Чему учит лидеров опыт собак Павлова Не пытайтесь мотивировать сотрудников страхом. Чему учит лидеров опыт собак Павлова

Как создать психологически безопасную среду для эффективной и успешной работы

Inc.
Послепродажное обслуживание. Зачем ехать к дилеру, если в гараже дешевле? Послепродажное обслуживание. Зачем ехать к дилеру, если в гараже дешевле?

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

4x4 Club
Полюби зарядку! 9 простых упражнений от Ляйсан Утяшевой Полюби зарядку! 9 простых упражнений от Ляйсан Утяшевой

Гимнастка Ляйсан Утяшева показывает упражнения для утренней зарядки

Cosmopolitan
8 суеверий, связанных с числами (а также почему мы выбрали 8) 8 суеверий, связанных с числами (а также почему мы выбрали 8)

Список чисел, которые вызывают очень сильные эмоции по всему миру

Maxim
Нити цивилизации Нити цивилизации

Текстиль учил людей считать, подталкивал технический и социальный прогресс

Forbes
Периодические многоножки оказались обладателями жизненного цикла длиной в восемь лет Периодические многоножки оказались обладателями жизненного цикла длиной в восемь лет

Исследователи: японские многоножки имеют восьмилетние жизненные циклы

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