Хотите видеть только хорошие новости?

Ученые провели самые масштабные квантовые вычисления

Полный граф на 8 вершинах. Иллюстрация David Benbennick

Американские и канадские ученые провели самое масштабное вычисление при помощи квантового компьютера на настоящий момент. Им удалось посчитать так называемые двухцветные числа Рамсея. Препринт статьи появился на сайте arXiv.org.

Теория Рамсея, названная в честь английского математика Франка Рамсея, - это раздел дискретной математики, занимающийся вопросами возникновения порядка в случайных системах. В частном случае, который изучался в работе, основная теорема звучит так - для любой пары чисел m и n найдется такое число R(m, n) (и называемое двухцветным числом Рамсея), что при любой раскраске полного графа с количеством вершин не меньше этого числа, в нем найдется либо полный подграф на m вершинах первого цвета, либо на n вершинах второго.

Примером на теорему Рамсея может служить следующая задача. Пусть решается вопрос о приглашении некоторого количества людей в гости. Мы знаем, что среди них нет n попарно знакомых, которые могли бы отделиться от общей вечеринки. Сколько надо пригласить людей, чтобы среди них было m попарно незнакомых?

Примечательно, что вычисление чисел Рамсея представляет сложнейшую задачу, поскольку проводится в лоб, громадным количеством переборов (например, до сих пор неизвестно R(5,5) - скорее всего оно лежит в пределах от 43 до 49). В рамках новой работы ученые использовали квантовый компьютер из 84 кубитов - квантовых аналогов бита, которые могут находиться сразу в суперпозиции нескольких состояний.

В результате им удалось посчитать числа R(3,3), R(4,2), R(5,2), R(6,2), R(7,2) и R(8,2). По словам исследователей, предыдущим рекордом по вычислению было разложение на простые множители числа 143. Для этого использовалось всего 4 кубита. В свою очередь первым реальным вычислением считается разложение на множители числа 15 десять лет назад. В том первом опыте участвовали семь кубитов.

В сентябре 2011 года группе физиков из Японии, Китая и США впервые удалось построить на практике квантовый компьютер по архитектуре фон Неймана - то есть с физическим разделением квантового процессора и квантовой памяти. Свои результаты они опубликовали в журнале Science.

Обсудить
00:02 Сегодня

Адский пепел

Что сотворило с человечеством мощнейшее в истории извержение вулкана
00:06 25 ноября 2016
Адольф Гитлер в окружении девушек

Блудливый рейх

Как проституция поднимала боевой дух нацистов
Заложники ситуации
Зачем США разворачивают бригаду в Восточной Европе
Достучаться до небес
Как в криминальной России разбираются с доносчиками
CH-53K King StallionСколько стоит вертолет
В поисках шеста для технологического барьера
Собирательный образ
Похожи ли фотороботы на реальных преступников
Дональд ТрампБомбы не получилось
Что может помешать Трампу обменять ядерное оружие на санкции
Спиральная галактика NGC 3521Их взрывы
Найден источник инопланетных сигналов
Адский пепел
Что сотворило с человечеством мощнейшее в истории извержение вулкана
Чужой внутри
Как раковые клетки обретают неуязвимость и медленно уничтожают человека
Белла Ахмадулина«Твоя сестра, такая дура, не научилась кофе готовить?!»
Борис Мессерер о Белле Ахмадулиной и Михаил Шишкин о свободе и демократии
Парадокс акына
В чем прав лауреат Сталинской премии Джамбул
Японский передовой
Как менялся празднующий 70-летний юбилей Такэси Китано
Концерт Noize MC в клубе Arena Moscow.«Соскучился ли я по травле в СМИ?»
Noize MC о новом альбоме, произволе полиции и безответственности родителей
Не только снег
Какие деликатесы готовят в российской глубинке
Обойдемся без «шенгена»
Как летать через Европу без визы
Падал прошлогодний снег
Как непогода изменила облик туристических достопримечательностей мира
Мила България
Чем заняться в Софии любознательному туристу
Тест: угадай автомобиль под камуфляжем
Получится ли у автопроизводителей провести настоящего знатока? Давайте проверять
5 провалов Детройта
Засекреченный блогер о главных премьерах первого моторшоу 2017 года
Бандитские тачки суровых времен
Самые известные машины 1990-х
Красивейшие машины Советского Союза
Самые красивые машины СССР, так и не увидевшие конвейера
«Теперь она бомж и живет в закутке под лестницей»
История преподавательницы, лишившейся трех квартир в Москве
«Мы начали решать свои проблемы, как в 90-х»
За потребительские кредиты смогут отбирать квартиры
Развели тут бордель
Экскурсия по самому большому публичному дому Южного полушария
Война дворцам
Каких домов лишились в 2016 году звезды Голливуда