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

Полный граф на 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:01 Сегодня
Американский пропагандистский плакат времен Второй мировой. Спортивное соперничество с японцами скоро перешло в военное

Оно не тонет

Как США стали сверхдержавой и впервые обвинили врагов в употреблении допинга
Напомнили о Третьей мировой
О чем говорили Путин и президент Словении на братской могиле русских солдат
 Лососевая путина на СахалинеРыба твоей мечты
Где наши законные морепродукты и почему они стоят так дорого
Челюстно-городская хирургия
Каким станет Новый Арбат после завершения масштабной реконструкции
Максим Ликсутов«Нельзя купить машину, если у вас нет парковочного места»
Максим Ликсутов о перспективах развития дорожно-транспортной системы Москвы
Протуберанцы атакуют
Внеземная жизнь, земная твердь и безграничные красоты космоса
Бальзамированное тело Владимира Ленина в траурном зале МавзолеяИ тело его живет
Какие тайны скрывает мавзолей Ленина
Американский пропагандистский плакат времен Второй мировой. Спортивное соперничество с японцами скоро перешло в военноеОно не тонет
Как США стали сверхдержавой и впервые обвинили врагов в употреблении допинга
Мозаичное панно, изображающее дружбу русского и украинского народов, на станции московского метро «Киевская»-кольцевая «Российская украинистика растет, формируется и зреет»
О чем спорят украинские и российские историки
Русская эмигрантка у витрин Брайтона«Захожу в лифт, а в нем негр»
Как отреагировала на перестройку русская эмиграция в Америке
Молодой Папа и старушка Европа
Гибсон, Малик, Кончаловский: что покажут на 73-м Венецианском кинофестивале
Рисунок любви
Почему девушки хотят замуж за очень взрослых мужчин
Разрешите вас съесть
Кинопремьеры недели: от «Охотников за привидениями» до «Неонового демона»
Взлом государственной важности
Кто внедрил вирус-шпион в сети российских госорганов и оборонных предприятий
Мем эпохи Возрождения
Как средневековая живопись стала оружием в руках интернет-троллей
«Новая традиция — оросить падик на Патриарших»
Откровения жителей центра о «быдле из Бирюлево» разозлили соцсети
Чак-Чак Норрис у Сильвестра в столовой
Как знаменитости превратились в названия ресторанов и кафе
Ноги от ушей
Лондонский Playboy Club отмечает полувековой юбилей
«Больше не хочу рисовать ягодицы»
Как и зачем ретуширует «ангелов» Victoria's Secret маэстро фотошопа
Селфи с медведем
Самые популярные фотографии Instagram за июль
Так любил, что почти убил
Фотоистория о женщинах, изуродованных «во имя чести»
Не надо втягивать живот
Лето-2016 проходит под знаком бодипозитива
Метры у метро
Московские новостройки, рядом с которыми скоро откроют станции подземки
Тиснули на славу
Как выглядит первое в мире здание, напечатанное на 3D-принтере
Вот это номер!
«Тайный арендатор» в многофункциональном комплексе «Ханой-Москва»
Жить стало веселее
Новая редакция «сталинского рая» на ВДНХ
Любовь по залету
Аэропорты мира, которые не захочется посещать добровольно
Rolling Acres Огайо, СШАЗакрыто навсегда
Как выглядят торговые центры-«призраки», потерявшие покупателей