репост про армейские полки, КХД и золотое сечение

сегодня эпиграф к репосту будет такой:

"Хочу рассказать вам про 9 Мая и моего дедушку.
Он был пехотинцем, войну закончил не в Германии, но где-то в Европе. Почему я не знаю никаких подробностей - потому что он никогда ничего не рассказывал про войну! Никогда и ничего." (цитата для Вас, неизвестный читатель - я перепечатала сюда анонс твита, поступившего мне на почту два часа назад - сам твиттер по-прежнему для меня не открывается, но анонсы продолжают поступать... эта цитата - сегодня 9 Мая 2022 года - именно сегодня, именно для меня актуальна как никогда... кстати, напомню себе и Вам... мой дедушка - тоже пехотинец - он не вернулся, в 43м погиб; его письма бабушке я храню, но рассказов о фронте в строчках, как правило нацарапанных химическим карандашом на коленке - рассказов мало, полагаю из-за военной цензуры)

репост сегодня такой:

243-летняя «нерешаемая» головоломка Эйлера получила квантовое решение

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

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

Подобные головоломки очаровывают людей уже более 2 тысяч лет. Культуры по всему миру создали «магические квадраты», массивы чисел, сумма которых в каждой строке и каждом столбце одинакова, и «латинские квадраты», заполненные символами, каждый из которых появляется один раз в строке и столбце. Эти квадраты использовались как в искусстве и градостроительстве, так и просто для удовольствия. Один популярный латинский квадрат, судоку, имеет подквадраты, в которых также отсутствуют повторяющиеся символы. Головоломка Эйлера «36 офицеров» представляет собой «ортогональный латинский квадрат», в котором два набора свойств, таких как звания и полки, одновременно должны удовлетворять правилам латинского квадрата.

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

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

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

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

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

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

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

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

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

Так что Эйлер, в некотором смысле, оказался неправ, хотя в 18-м веке он просто не мог знать о возможности квантовых офицеров.

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

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

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

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

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

(Василий Вдовиченко 3 месяца назад. По материалам: quantamagazine)

Другие статьи в литературном дневнике:

• 09.05.2022. репост про армейские полки, КХД и золотое сечение