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

N+1Наука

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

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

Federico Centrone et al. / Nature communications, 2021

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

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

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

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

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

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

Астрономы отыскали кандидата в очень далекую карликовую планету на крайне широкой орбите Астрономы отыскали кандидата в очень далекую карликовую планету на крайне широкой орбите

Как обнаружили кандидата в экзотичный по свойствам транснептуновый объект

N+1
Валерия: «Удивляет все, что происходит на сцене» Валерия: «Удивляет все, что происходит на сцене»

Валерия все успевает и всегда остается молодой, красивой и безупречно элегантной

Лиза
«Гипотеза белых дыр» «Гипотеза белых дыр»

Почему снаружи белая дыра не отличается от черной

N+1
Роскошь Востока: турецкие сериалы для тех, кому понравился «Великолепный век» Роскошь Востока: турецкие сериалы для тех, кому понравился «Великолепный век»

Самые успешные сериальные проекты турецкого кинематографа

Cosmopolitan
Я вижу, о чем вы думаете Я вижу, о чем вы думаете

Как агенты ФБР читают людей

kiozk originals
Опыт против разума: чем купоны на еду лучше контроля над ценами Опыт против разума: чем купоны на еду лучше контроля над ценами

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

Forbes
Мастер историй Мастер историй

Увлекай, убеждай, вдохновляй

kiozk originals
19 существ, которые могут тебя съесть 19 существ, которые могут тебя съесть

Эти существа могут съесть человека

Maxim
«Чай с любовью» «Чай с любовью»

Регина Тодоренко и Влад Топалов — о любви, браке и 30 книгах по психологии

OK!
Школа рисования Школа рисования

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

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

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

Playboy
Отсечь и отпустить Отсечь и отпустить

Принципы жизни Бурятии

Вокруг света
5 ошибок сооснователя Playkey Егора Гурьева 5 ошибок сооснователя Playkey Егора Гурьева

Егор Гурьев, сооснователь Playkey, поделился ошибками своей команды

Inc.
Своя линия Своя линия

Учимся ухаживать за бровями, чтобы они лучше росли, были сильными и густыми

Лиза
Как начать работать на зарубежном маркетплейсе бренду из России? Инструкция для предпринимателей Как начать работать на зарубежном маркетплейсе бренду из России? Инструкция для предпринимателей

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

Inc.
Голливудский ГУЛАГ Голливудский ГУЛАГ

Михаил Трофименков о «Мавританце» — истории политического заключенного XXI века

Weekend
15 массовых заблуждений, с которыми пора наконец покончить раз и навсегда 15 массовых заблуждений, с которыми пора наконец покончить раз и навсегда

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

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

Как освободиться от сахара?

Cosmopolitan
Ездить на велосипеде зимой: 5 простых правил на личном опыте Ездить на велосипеде зимой: 5 простых правил на личном опыте

Велосипед – это круглогодичный вид транспорта!

Популярная механика
Poker face: как блеф может изменить твою жизнь Poker face: как блеф может изменить твою жизнь

Рейтинг самых лучших блефов в истории

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

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

Cosmopolitan
«Кошатники» и «собачники»: 6 принципиальных отличий «Кошатники» и «собачники»: 6 принципиальных отличий

Что выбор питомца говорит о нас самих?

Psychologies
Лоуренс Аравийский Лоуренс Аравийский

Война, ложь, имперская глупость и становление современного Ближнего Востока

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

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

Inc.
Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT

Биткоин-элита тратит миллионы долларов на покупку цифрового искусства

Inc.
Мафия Tesla: как бывшие подчиненные Илона Маска становятся его главными конкурентами Мафия Tesla: как бывшие подчиненные Илона Маска становятся его главными конкурентами

Люди, стоявшие у истоков Tesla, которые позднее бросили вызов Илону Маску

Forbes
Скорсезе раскритиковал стриминги и призвал вернуть ценность киноискусства Скорсезе раскритиковал стриминги и призвал вернуть ценность киноискусства

Мартин Скорсезе обратился к киноиндустрии с требованием сохранить искусство кино

РБК
«В чем сила, брат?» 7 фильмов Алексея Балабанова, которые нужно пересмотреть «В чем сила, брат?» 7 фильмов Алексея Балабанова, которые нужно пересмотреть

Алексей Балабанов - самый противоречивый российский режиссер

Cosmopolitan
Когда близнецы не похожи друг на друга Когда близнецы не похожи друг на друга

Почему одни близнецы похожи друг на друга, а другие нет?

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

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

Наука
Открыть в приложении