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

Полный граф на 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 Tiguan, а встретили сразу два
Дайте грязи: конкуренты вседорожному хэтчу Kia Rio X-Line
Renault Sandero Stepway, Lada Vesta SW Cross и другие приподнятые бюджетники
Как через Instagram продают машины за миллионы
Соцсети, молодеющие покупатели и другие причуды современного рынка суперкаров
Семиместность не порок
Как из пятиместной Mazda CX-5 получился семиместный кроссовер CX-9
Братва помнит
Чем украшают могилы криминальных авторитетов
Интим предлагать
Секс стал способом решения квартирного вопроса
«Я тупо решила, что теперь ем одну гречку»
Одинокая мать год сидела на крупе, чтобы накопить на квартиру
Раз, два, взяли!
Жилье в Крыму пока еще можно купить за копейки