Удивительное новое решение знаменитой «головоломки 36 офицеров» Леонарда Эйлера предлагает нам новый способ кодирования квантовой информации.
В 1779 году швейцарский математик Леонард Эйлер придумал задачу: если в каждом из шести разных армейских полков находится по шесть офицеров различных званий, можно ли построить эти 36 офицеров в квадрат 6 на 6 так, чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лищь один раз?
Головоломка легко решается, когда есть пять званий и пять полков, или семь званий и семь полков. Но после безуспешных поисков решения для случая с 36 офицерами Эйлер пришел к выводу, что «такое расположение невозможно, хотя мы и не можем дать строгого доказательства этого». Более века спустя французский математик Гастон Тарри доказал, что действительно невозможно расположить 36 офицеров Эйлера в квадрате 6 на 6 без повторений. В 1960 году математики использовали компьютеры, чтобы доказать, что решения существуют для любого количества полков и рангов больше двух, за исключением случая шести.
Такие загадки очаровывают людей уже более 2000 лет. Культуры по всему миру создавали «магические квадраты» — таблицы чисел, которые складываются в одну и ту же сумму в каждой строке и столбце, и «латинские квадраты», заполненные символами, каждый из которых появляется лишь один раз в строке и столбце. Эти квадраты использовались в искусстве и городском планировании, а также просто для развлечения. В одном популярном латинском квадрате — судоку — есть подквадраты, в которых также отсутствуют повторяющиеся символы. Задача Эйлера о 36 офицерах требует «ортогонального латинского квадрата», в котором два набора свойств, таких как звания и полки, одновременно удовлетворяют правилам латинского квадрата.
Хотя Эйлер считал, что такого квадрата 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З останется уникальным.
Ссылка на оригинал статьи: https://www.quantamagazine.org/eulers-243-year-old-impossible-puzzle-gets-a-quantum-solution-20220110/
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
