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

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

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