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

Полный граф на 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.

Обсудить
Афганский груз
Американцев убивают в Афганистане уже 16 лет, и Трамп хочет продолжения
На кровавых каруселях
Перестрелять недовольных — переизбравшийся президент Кении оказался обидчивым
Гуд-бай, Америка: США перестанут выдавать визы россиянам
Все собеседования отменены до начала осени
Всюду Гитлер
Беспощадная война с нацистами в Германии набирает абсурдные обороты
Демократия подъехала
США влияют на политику других стран, не привлекая внимания
Ломать — не строить
Кто наживется на программе реновации в России
Михаил Воронин«Бизнесмены — это одинокие люди»
Михаил Воронин рассказал о малом бизнесе и секретах Российского Бизнес-Форума «Атланты 2017»
Тухлый номер
Россияне рискуют закупиться отравленными продуктами и умереть