843
У 1782 році Леонард Ейлер сформулював задачу про 36 офіцерів: шість полків і шість військових рангів потрібно розмістити у квадраті 6×6 так, щоб у кожному рядку й стовпці кожен полк і кожен ранг зустрічалися рівно один раз. Класична математика пізніше довела, що такого розташування не існує.
Задача пов’язана з orthogonal Latin squares — таблицями символів, де кожен символ зустрічається по одному разу в кожному рядку та стовпці, а після накладання двох таблиць усі можливі пари символів мають виникнути рівно один раз.
У сучасній quantum combinatorics замість звичайних символів можна використовувати quantum states. Це дозволило побудувати квантове рішення задачі Ейлера.
Що показало дослідження
Дослідники Polytechnic University of Catalunya поставили точніше питання: чи можна отримати таке рішення лише завдяки quantum superposition, але без entanglement.
Практично це було б цікаво тому, що квантовий стан без заплутаності можна підготувати простішими circuits із меншою gate depth.
Robin Simoens і Simeon Ball спочатку довели, що в шуканій парі один quantum Latin square можна вважати класичним без втрати загальності.
Після цього задачу перевели в graph theory: потрібно було з’ясувати, чи має відповідний Latin square graph певне orthonormal representation.
Чому це важливо
Комп’ютерний алгоритм показав, що такого представлення не існує. Отже, взаємно orthogonal quantum Latin squares розміру 6×6 без entanglement побудувати неможливо.
Результат закриває останній відкритий випадок для product-orthogonal quantum Latin squares. Для інших розмірностей подібні пари були відомі, а шоста залишалася особливою.
Таким чином, квантова версія справді обходить класичну неможливість Ейлера, але лише за рахунок genuinely quantum resource — заплутаності між станами.
Автори продовжують шукати інші combinatorial structures, де одна лише superposition могла б перевершити класичну математику навіть без entanglement.
Джерело: Phys.org
