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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

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

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

N+1
Ботокс: что нужно знать, прежде чем принимать решение Ботокс: что нужно знать, прежде чем принимать решение

Что лучше знать до инъекций ботокса и как он влияет на красоту и здоровье

РБК
Астрономы отыскали удивительно развитую перемычку у спиральной галактики в ранней Вселенной Астрономы отыскали удивительно развитую перемычку у спиральной галактики в ранней Вселенной

Астрономы обнаружили у галактики J0107a необычно развитую центральную перемычку

N+1
Как фильм «Дом Пьера Кардена» раскрывает дизайнера с новых и неожиданных сторон Как фильм «Дом Пьера Кардена» раскрывает дизайнера с новых и неожиданных сторон

Документальный фильм «Дом Пьера Кардена» о легендарном модном дизайнере

Esquire
Топ-5 орехов против старения Топ-5 орехов против старения

Могут ли орехи улучшить ваше самочувствие и продлить молодость?

ТехИнсайдер
Любовь живет четыре года Любовь живет четыре года

Анн-Софи Пайере раз в четыре года меняет жилье и с нуля создает новый интерьер

AD
Попутная нефтяная энергия Попутная нефтяная энергия

Чашкинская ГТЭС в Пермском крае будет перерабатывать попутный нефтяной газ

Наука
Пористый полимерный каркас позволил мышам эффективней нарастить мышечные клетки Пористый полимерный каркас позволил мышам эффективней нарастить мышечные клетки

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

N+1
Ретабло – древнейшее из искусств Ретабло – древнейшее из искусств

Ретабло – картины, которые жертвуют церквям в благодарность о помощи святых

Вокруг света
Жизнь после смерти: 5 историй тех, кто вышел из комы Жизнь после смерти: 5 историй тех, кто вышел из комы

Истории людей, которые пережили клиническую смерть

Cosmopolitan
«Малкольм и Мари» — неудачный фильм, который все равно нельзя пропустить «Малкольм и Мари» — неудачный фильм, который все равно нельзя пропустить

На Netflix вышла драма о сумме и разнице двух творческих единиц

РБК
Зеркальные нейтроны снизили предел массы нейтронных звезд Зеркальные нейтроны снизили предел массы нейтронных звезд

Свойства зеркального вещества ограничиваются из астрофизических наблюдений

N+1
Anti-age: 7 правил Anti-age: 7 правил

Чтобы замедлить старение кожи, не обязательно прибегать к салонным процедурам

Добрые советы
TikTok против убийств и расизма. Как алгоритмы соцсети помогают индейцам Канады бороться за жизнь и права TikTok против убийств и расизма. Как алгоритмы соцсети помогают индейцам Канады бороться за жизнь и права

Одни используют TikTok для самовыражения, другие — для борьбы за свои права

СНОБ
Любовь в зрелом возрасте: где и как ее искать? Любовь в зрелом возрасте: где и как ее искать?

Как еще раз построить отношения в зрелом возрасте

Домашний Очаг
«Еда должна быть безупречной». Рестораторы и шефы — о доставке и ее проблемах «Еда должна быть безупречной». Рестораторы и шефы — о доставке и ее проблемах

Рестораторы рассказывают о том, как они подходят к вопросам доставки блюд

РБК
Стала красивее,чем Хюррем: как изменилась Мерьем Узерли после пластики и диеты Стала красивее,чем Хюррем: как изменилась Мерьем Узерли после пластики и диеты

Мерьем Узерли расцвела, как прекрасный восточный цветок

Cosmopolitan
Слава угасла? Где сейчас YouTube-блогеры, которые были популярны 10 лет назад Слава угасла? Где сейчас YouTube-блогеры, которые были популярны 10 лет назад

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

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

Новая Зеландия разрешила ввезти в страну два вида насекомых из Евразии

N+1
Почему девушка не пишет первой: 8 возможных причин (рано паниковать) Почему девушка не пишет первой: 8 возможных причин (рано паниковать)

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

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

Рассказываем, как стать бизнесменом с нуля и не облажаться по полной программе.

Playboy
Наркотики и аборты без анестезии: как обращались с детьми-актерами в Голливуде Наркотики и аборты без анестезии: как обращались с детьми-актерами в Голливуде

Голливуд — фабрика грез с двойным дном

Cosmopolitan
«Новости со всех концов света»: Том Хэнкс соединяет штаты Америки и ведет ее в будущее словом «Новости со всех концов света»: Том Хэнкс соединяет штаты Америки и ведет ее в будущее словом

«Новости со всех концов света» — полюбившийся всем вестерн от Пола Гринграсса

Esquire
Антидепрессант остановил разрушение хрящей при остеоартрите Антидепрессант остановил разрушение хрящей при остеоартрите

Пароксетин может стать препаратом для лечения остеоартрита

N+1
Искатель жизни: чем уникальна новая марсианская миссия Искатель жизни: чем уникальна новая марсианская миссия

Амбициозные задачи марсохода Perseverance и вертолета Ingenuity

Forbes
Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги) Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги)

Фрагмент главы из книги Рока и Джона Позитано «Ужин с Ди Маджо»

Esquire
Новая Lada Niva Travel: первые впечатления за рулем Новая Lada Niva Travel: первые впечатления за рулем

Дебют обновленной Lada Niva

РБК
20 способов стать идеальным партнером 20 способов стать идеальным партнером

Как стать лучше в глазах любимого человека?

Psychologies
Праздник женских удовольствий: 24 часа только для себя Праздник женских удовольствий: 24 часа только для себя

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

Psychologies
Эффектный конский хвост: 10 крутых идей для самой удобной прически Эффектный конский хвост: 10 крутых идей для самой удобной прически

Если обычный конский хвост — это слишком скучно, то попробуй наши варианты

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