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

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

Обсудить
Наука и техника

Пусть полетает

Какое ПО нужно беспилотнику и как на этом заработать
Очеловеченный фургон
Длительный тест стильно-пассажирского VW Multivan
ОСАГО надо?
Автомобильные аварии, превращенные в искусство
Самые крутые локомобили
Машины, которые ездят по рельсам
Самые выдающиеся французские машины
10 автомобилей из Франции, ставших культовыми
Москва за нами
Какие квартиры можно купить в пределах МКАД по цене до трех миллионов рублей
Зависли на хате
Украинцы придумали дом, который может обойтись без российского газа
Чудеса селекции
Что получится, если скрестить квартиру с дачей: опыт россиян
Сносное настроение
Демонтаж жилых домов в Москве: что нужно знать
Вышка светит
Как выглядит частный особняк, побивший мировой рекорд этажности