Как стать автором
Обновить

Через 243 года «неразрешимая» головоломка Эйлера получила наконец решение с помощью странной физики кота Шредингера

Время на прочтение6 мин
Количество просмотров58K
Автор оригинала: Daniel Garisto, журнал Quantum Xchange

Удивительное новое решение знаменитой «головоломки 36 офицеров» Леонарда Эйлера предлагает нам новый способ кодирования квантовой информации.

Елена Шмахало для журнала Quanta.
Елена Шмахало для журнала Quanta.

В 1779 году швейцарский математик Леонард Эйлер придумал задачу: если в каждом из шести разных армейских полков есть по шесть офицеров различных званий, можно ли построить эти 36 офицеров в квадрат 6 на 6 так, чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лишь один раз?

Головоломка легко решается, когда есть пять званий и пять полков, или семь званий и семь полков. Но после безуспешных поисков решения для случая с 36 офицерами Эйлер пришел к выводу, что «такое расположение невозможно, хотя мы и не можем дать строгого доказательства этого». Более века спустя французский математик Гастон Тарри доказал, что действительно невозможно расположить 36 офицеров Эйлера в квадрате 6 на 6 без повторений. В 1960 году математики использовали компьютеры, чтобы доказать, что решения существуют для любого количества полков и рангов больше двух, за исключением случая шести.

Такие загадки очаровывают людей уже более 2000 лет. Культуры по всему миру создавали «магические квадраты» — таблицы чисел, которые складываются в одну и ту же сумму в каждой строке и столбце, и «латинские квадраты», заполненные символами, каждый из которых появляется лишь один раз в строке и столбце. Эти квадраты использовались в искусстве и городском планировании, а также просто для развлечения. В одном популярном латинском квадрате — судоку — есть подквадраты, в которых также отсутствуют повторяющиеся символы. Задача Эйлера о 36 офицерах требует «ортогонального латинского квадрата», в котором два набора свойств, таких как звания и полки, одновременно удовлетворяют правилам латинского квадрата.

Таблица пять на пять может быть заполнена шахматными фигурами пяти разных рангов и пяти разных цветов, так что ни одна строка или столбец не повторяет ранг или цвет. Сэмюэл Веласко / Quanta Magazine
Таблица пять на пять может быть заполнена шахматными фигурами пяти разных рангов и пяти разных цветов, так что ни одна строка или столбец не повторяет ранг или цвет. Сэмюэл Веласко / Quanta Magazine

Хотя Эйлер считал, что такого квадрата 6 на 6 не существует, недавно все поменялось. В статье, представленной к публикации в журнале Physical Review Letters , группа квантовых физиков из Индии и Польши продемонстрировала, что можно расположить 36 офицеров таким образом, чтобы они соответствовали критериям головоломки Эйлера, но при условии, что офицеры могут иметь квантовую смесь званий и полков. Результатом стала последняя работа в области разработки квантовых версий головоломок с магическим и латинским квадратом, которая представляет собой уже не просто развлечение или игру, но и предоставляет возможность практического применения ее для квантовой связи и квантовых вычислений.

«Я считаю, что их статья весьма красива», — сказала Джемма Де лас Куэвас , квантовый физик из Университета Инсбрука, которая не участвовала в работе. —  «Там много квантовой магии. И не только это, на протяжении всей статьи чувствуется их любовь к проблеме».

Новая эра квантовой головоломки началась в 2016 году, когда Джейми Викари из Кембриджского университета и его тогдашний студент Бен Мусто пришли к неожиданной идее, что записи в латинских квадратах можно сделать квантовыми.

В квантовой механике такие объекты, как электроны, могут находиться в «суперпозиции» нескольких возможных состояний: например, одновременно магнитно ориентированы как вверх, так и вниз. Квантовые объекты остаются в этой неопределенности до тех пор, пока они не будут измерены, и именно в этот момент они определяются в одном конкретном состоянии. Записи квантовых латинских квадратов также являются квантовыми состояниями, которые могут находиться в квантовых суперпозициях. Математически квантовое состояние представлено вектором, имеющим длину и направление подобно стрелке. Суперпозиция — это стрелка, образованная объединением нескольких векторов. По аналогии с требованием, чтобы символы вдоль каждой строки и столбца латинского квадрата не повторялись, квантовые состояния вдоль каждой строки или столбца квантового латинского квадрата должны соответствовать векторам, перпендикулярным друг другу.

Квантовые латинские квадраты были быстро приняты сообществом физиков-теоретиков и математиков, заинтересованных в их необычных свойствах. В прошлом году французские физики-математики Ион Нечита и Жорди Пийе создали квантовую версию судоку — SudoQ . Вместо использования целых чисел от 0 до 9 в SudoQ строки, столбцы и подквадраты имеют девять перпендикулярных векторов.

Эти достижения побудили Адама Бурхардта, научного сотрудника Ягеллонского университета в Польше, и его коллег заново пересмотреть старую загадку Эйлера о 36 офицерах. Они задались вопросом, а что, если офицеры Эйлера станут квантовыми?

В классическом варианте задачи каждая запись — это офицер с четко определенным званием и полком. Для простоты можно представить себе 36 офицеров как разноцветные шахматные фигуры, каждая из которых может быть королем, ферзем, ладьей, слоном, конем или пешкой, а полк представлен красным, оранжевым, желтым, зеленым, синим или фиолетовым цветом. Но в квантовой версии офицеры формируются из суперпозиций званий и полков. Например, офицер может быть суперпозицией красного короля и оранжевой королевы.

Критически важно, что квантовые состояния, в которых находятся эти офицеры, имеют особое отношения, называемое запутанностью, которое включает корреляцию между различными сущностями. Например, если красный король запутан с оранжевым ферзем, то даже если и король, и ферзь находятся в суперпозиции нескольких полков, наблюдение того, что рядом есть красный король, сразу означает, что в этом случае наша фигура - оранжевый ферзь (при запутывании состояние одного объекта информирует нас о состоянии другого). Именно из-за специфического характера запутывания все офицеры на каждой линии могут быть перпендикулярны.

Теория, казалось, работала, но для доказательства её авторам пришлось построить массив размером 6 на 6, заполненный квантовыми офицерами. Огромное количество возможных конфигураций и запутанных ситуаций означало, что им пришлось полагаться на помощь компьютера. Исследователи подключили классическое "почти" решение (расстановка из 36 классических офицеров с несколькими повторениями званий и полков в одном ряду или столбце) и применили алгоритм, который настроил расположение в сторону истинного квантового решения. Алгоритм немного похож на сборку кубика Рубика методом brute force, когда вы исправляете и затем фиксируете первую строку, затем первый столбец, второй столбец и так далее. Когда они повторяли алгоритм снова и снова, массив головоломки становился все ближе и ближе к истинному решению. В конце концов, исследователи достигли точки, когда они смогли увидеть шаблон и заполнить несколько оставшихся записей вручную.

В каком-то смысле Эйлер оказался неправ — хотя в XVIII веке он не мог представить появления квантовых офицеров.

«Они перевернули страницу с этой головоломкой, что уже очень приятно», — сказал Нечита. — «Это очень красивый результат, и мне нравится, как они его получают».

Одна удивительная особенность их решения, по словам соавтора Сухайла Разера, физика из Индийского технологического института в Мадрасе в Ченнаи, заключается в том, что офицерские звания перепутаны только с соседними званиями (короли с ферзями, ладьи со слонами, кони с пешками) и полки с соседними полками. Еще одним сюрпризом стали коэффициенты, появляющиеся в записях квантового латинского квадрата. Эти коэффициенты представляют собой числа, которые, по сути, говорят вам, какой вес придавать различным терминам в суперпозиции. Любопытно, что соотношение коэффициентов, на котором остановился алгоритм, было  1,618… — знаменитое золотое сечение.

Решение также известно как абсолютно максимально запутанное состояние (AMЗ), расположение квантовых объектов, которое считается важным для ряда приложений, включая квантовую коррекцию ошибок — способа избыточного хранения информации в квантовых компьютерах, чтобы она сохранялась даже при повреждении данных. В АМЗ корреляции между измерениями квантовых объектов настолько сильны, насколько это возможно: если у Алисы и Боба "запутались" монеты, и Алиса подбрасывает свою монету и выпадает орел, она точно знает, что у Боба решка, и наоборот. Две монеты могут быть максимально запутаны, как и три, но не четыре: если Кэрол и Дэйв присоединятся к подбрасыванию монеты, Алиса никогда не сможет быть уверена, что получит Боб.

Однако новое исследование доказывает, что если у вас есть набор из четырех запутанных игральных костей, а не монет, они могут быть максимально запутаны. Расположение шестигранных игральных костей эквивалентно квантовому латинскому квадрату 6 на 6. Из-за присутствия золотого сечения в их решении исследователи назвали его «золотым AMЗ».

Исследователи ранее разработали другие AMЗ, начав с классических кодов с исправлением ошибок и найдя аналогичные квантовые версии. Но новоявленный золотой AMЗ отличается от него и не имеет классического криптографического аналога. Бурхардт подозревает, что это может быть первый представитель нового класса квантовых кодов с исправлением ошибок. С другой стороны, может оказаться не менее интересно, если золотой AMЗ останется уникальным.

Ссылка на оригинал статьи


Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.

Теги:
Хабы:
Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку
Всего голосов 37: ↑16 и ↓21+3
Комментарии75

Публикации