Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2204.06800 · Journal of Physics Conference Series

9 × 4 = 6 × 6: Understanding the Quantum Solution to Euler’s Problem of 36 Officers

Karol Życzkowski, Wojciech Bruzda, Grzegorz Rajchel-Mieldzioć, Adam Burchardt, Suhail Ahmad Rather, Arul Lakshminarayan

Published Feb 1, 2023• 24 citations
arXivHTMLPDF

Abstract

Abstract The famous combinatorial problem of Euler concerns an arrangement of 36 officers from six different regiments in a 6×6 square array. Each regiment consists of six officers each belonging to one of six ranks. The problem, originating from Saint Petersburg, requires that each row and each column of the array contains only one officer of a given rank and given regiment. Euler observed that such a configuration does not exist. In recent work, we constructed a solution to a quantum version of this problem assuming that the officers correspond to superpositions of quantum states. In this paper, we explain the solution which is based on a partition of 36 officers into nine groups, each with four elements. The corresponding quantum states are locally equivalent to maximally entangled two-qubit states, hence each quantum officer is represented by a superposition of at most 4 classical states. The entire quantum combinatorial design involves 9 Bell bases in nine complementary 4–dimensional subspaces.

DOI
10.1088/1742-6596/2448/1/012003

Related papers

Quantum version of the Euler's problem: a geometric perspective

Karol Życzkowski

The classical combinatorial problem of $36$ officers has no solution, as there are no Graeco-Latin squares of order six. The situation changes if one works in a quantum setup and allows for superpositions of classical objects and admits entangled states. We analyze the recently found solution to the quantum version of the Euler's problem from a geometric point of view. The notion of a non-displaceable manifold embedded in a larger space is recalled. This property implies that any two copies of such a manifold, like two great circles on a sphere, do intersect. Existence of a quantum Graeco-Latin square of size six, equivalent to a maximally entangled state of four subsystems with d=6 levels each, implies that three copies of the manifold U(36)/U(1) of maximally entangled states of the $36\times 36$ system, embedded in the complex projective space ${C}P^{36\times 36 -1}$, do intersect simultaneously at a certain point.

arXiv:2212.03903•Dec 7, 2022•4 citations

Thirty-six Entangled Officers of Euler: Quantum Solution to a Classically Impossible Problem

Suhail Ahmad Rather, Adam Burchardt, Wojciech Bruzda +3 more

The negative solution to the famous problem of 36 officers of Euler implies that there are no two orthogonal Latin squares of order six. We show that the problem has a solution, provided the officers are entangled, and construct orthogonal quantum Latin squares of this size. As a consequence, we find an example of the long-elusive Absolutely Maximally Entangled state AME(4,6) of four subsystems with six levels each, equivalently a 2-unitary matrix of size 36, which maximizes the entangling power among all bipartite unitary gates of this dimension, or a perfect tensor with four indices, each running from one to six. This special state deserves the appellation golden AME state, as the golden ratio appears prominently in its elements. This result allows us to construct a pure nonadditive quhex quantum error detection code ((3,6,2))_{6}, which saturates the Singleton bound and allows one to encode a six-level state into a triplet of such states.

arXiv:2104.05122•Physical Review Letters•Feb 25, 2022•72 citations

Fractional and quantum Latin squares: real solutions of quantum 36 officers problem

Mykhailo Hontarenko, Karol Życzkowski

A Latin square can be extended by replacing its symbols with probabilities or quantum states. We relate these two extensions through explicit examples, from classical and fractional Latin squares to quantum Latin squares and a real solution of Euler's quantum 36 officers problem. A simultaneous cyclic-shift ansatz on a four-torus of tensor coefficients gives a real absolutely maximally entangled (AME) state of four six-level systems. A local orthogonal change of basis yields a representative with 96 nonzero amplitudes. Two single-party arrays obtained from the corresponding quantum orthogonal Latin square yield fractional Latin squares. Signs matter: comparison with the independent real construction of Bruzda and its sign variant distinguishes three local-unitary classes, two of which have identical probabilities. We extend this probability representation to existing seven- and nine-party AME states with six levels each. Their amplitude matrices reveal 48 complex Hadamard blocks of order $3^3$ and six of order $6^4$, respectively. These constructions separate what can be read from a probability picture from the coherent conditions responsible for maximal entanglement.

quant-pharXiv:2610.17170•Oct 13, 2026•0 citations

Absolutely maximally entangled state equivalence and the construction of infinite quantum solutions to the problem of 36 officers of Euler

Suhail Ahmad Rather, N. Ramadas, Vijay Kodiyalam +1 more

Ordering and classifying multipartite quantum states by their entanglement content remains an open problem. One class of highly entangled states, useful in quantum information protocols, the absolutely maximally entangled (AME) ones, are especially hard to compare as all their subsystems are maximally random. While it is well known that there is no AME state of four qubits, many analytical examples and numerically generated ensembles of four-qutrit AME states are known. However, we prove the surprising result that there is truly only one AME state of four qutrits up to local unitary equivalence. In contrast, for larger local dimensions, the number of local unitary classes of AME states is shown to be infinite. Of special interest is the case of local dimension 6, where it was established recently that a four-party AME state does exist, providing a quantum solution to the classically impossible Euler problem of 36 officers. Based on this, an infinity of quantum solutions are constructed, and we prove that these are not equivalent. The methods developed can be usefully generalized to multipartite states of any number of particles.

arXiv:2212.06737•Physical Review A•Sep 13, 2023•24 citations

Euler's thirty-six officers need not all be entangled: real AME(4,6), families and classification

Palash Pandya

Absolutely maximally entangled states of four six-level systems, AME$(4,6)$, are the quantum solutions of Euler's problem of the thirty-six officers. Until recently all reported solutions were complex, and it was conjectured that no real orthogonal 2-unitary matrix of order $36$ exists. We give real AME$(4,6)$ states with $60$ non-zero coefficients in $\{\pm1,\sqrt2\}/\sqrt{72}$. Of their thirty-six officers, $12$ are classical, as some must be whenever fewer than $72$ coefficients are non-zero. They lie in the $-1$ eigenspace of an order-$4$ local symmetry, and on their support the AME conditions become linear. We derive two closed-form families of AME$(4,6)$ states that meet at one of these states: a $10$-parameter family that is supported on $72$ basis states, and an $11$-parameter family on $60$ basis states. At each of its two ends the first family loses $12$ coefficients, and the AME states on the remaining $60$ basis states form an $11$-parameter family: the second family at one end, and an analogous family at the other. These two $60$-term families contain $4096$ real AME states up to diagonal local unitaries, $1024$ of which are limits of the first family. They fall into exactly $20$ classes under local unitaries and permutations of the parties, and we certify their separation with interval arithmetic.

quant-pharXiv:2610.16673•Oct 13, 2026•0 citations

Thirty-six officers, artisanally entangled

Gross, David, Paulina L. A. Goedicke

A perfect tensor of order $d$ is a state of four $d$-level systems that is maximally entangled under any bipartition. These objects have attracted considerable attention in quantum information and many-body theory. Perfect tensors generalize the combinatorial notion of orthogonal Latin squares (OLS). Deciding whether OLS of a given order exist has historically been a difficult problem. The case $d=6$ proved particularly thorny, and was popularized by Leonhard Euler in terms of a putative constellation of "36 officers". It took more than a century to show that Euler's puzzle has no solution. After yet another century, its quantum generalization was resolved in the affirmative: 36 entangled officers can be suitably arranged. However, the construction and verification of known instances relies on elaborate computer codes. In this paper, we present the first human-made order-$6$ perfect tensors. We decompose the Hilbert space $(\mathbb{C}^6)^{\otimes 2}$ of two quhexes into the direct sum $(\mathbb{C}^3)^{\otimes 2}\oplus(\mathbb{C}^3)^{\otimes 3}$ comprising superpositions of two-qutrit and three-qutrit states. Perfect tensors arise when certain Clifford unitaries are applied separately to the two sectors. Technically, our construction realizes solutions to the perfect functions ansatz recently proposed by Rather. Generalizing an observation of Bruzda and Życzkowski, we show that any solution of this kind gives rise to a two-unitary complex Hadamard matrix, of which we construct infinite families. Finally, we sketch a formulation of the theory of perfect tensors in terms of quasi-orthogonal decompositions of matrix algebras.

arXiv:2504.15401•Apr 21, 2025•9 citations
Abstract The famous combinatorial problem of Euler concerns an arrangement of 36 officers from six different regiments in a 6×6 square array. Each regiment consists of six officers each belonging to one of six ranks. The problem, originating from Saint Petersburg, requires that each row and each column of the array contains only one officer of a given rank and given regiment. Euler observed that such a configuration does not exist. In recent work, we constructed a solution to a quantum version of this problem assuming that the officers correspond to superpositions of quantum states. In this paper, we explain the solution which is based on a partition of 36 officers into nine groups, each with four elements. The corresponding quantum states are locally equivalent to maximally entangled two-qubit states, hence each quantum officer is represented by a superposition of at most 4 classical states. The entire quantum combinatorial design involves 9 Bell bases in nine complementary 4–dimensional subspaces.
The classical combinatorial problem of 363636 officers has no solution, as there are no Graeco-Latin squares of order six. The situation changes if one works in a quantum setup and allows for superpositions of classical objects and admits entangled states. We analyze the recently found solution to the quantum version of the Euler's problem from a geometric point of view. The notion of a non-displaceable manifold embedded in a larger space is recalled. This property implies that any two copies of such a manifold, like two great circles on a sphere, do intersect. Existence of a quantum Graeco-Latin square of size six, equivalent to a maximally entangled state of four subsystems with d=6 levels each, implies that three copies of the manifold U(36)/U(1) of maximally entangled states of the 36×3636\times 3636×36 system, embedded in the complex projective space CP36×36−1{C}P^{36\times 36 -1}CP36×36−1, do intersect simultaneously at a certain point.
The negative solution to the famous problem of 36 officers of Euler implies that there are no two orthogonal Latin squares of order six. We show that the problem has a solution, provided the officers are entangled, and construct orthogonal quantum Latin squares of this size. As a consequence, we find an example of the long-elusive Absolutely Maximally Entangled state AME(4,6) of four subsystems with six levels each, equivalently a 2-unitary matrix of size 36, which maximizes the entangling power among all bipartite unitary gates of this dimension, or a perfect tensor with four indices, each running from one to six. This special state deserves the appellation golden AME state, as the golden ratio appears prominently in its elements. This result allows us to construct a pure nonadditive quhex quantum error detection code ((3,6,2))_{6}, which saturates the Singleton bound and allows one to encode a six-level state into a triplet of such states.
A Latin square can be extended by replacing its symbols with probabilities or quantum states. We relate these two extensions through explicit examples, from classical and fractional Latin squares to quantum Latin squares and a real solution of Euler's quantum 36 officers problem. A simultaneous cyclic-shift ansatz on a four-torus of tensor coefficients gives a real absolutely maximally entangled (AME) state of four six-level systems. A local orthogonal change of basis yields a representative with 96 nonzero amplitudes. Two single-party arrays obtained from the corresponding quantum orthogonal Latin square yield fractional Latin squares. Signs matter: comparison with the independent real construction of Bruzda and its sign variant distinguishes three local-unitary classes, two of which have identical probabilities. We extend this probability representation to existing seven- and nine-party AME states with six levels each. Their amplitude matrices reveal 48 complex Hadamard blocks of order 333^333 and six of order 646^464, respectively. These constructions separate what can be read from a probability picture from the coherent conditions responsible for maximal entanglement.
Ordering and classifying multipartite quantum states by their entanglement content remains an open problem. One class of highly entangled states, useful in quantum information protocols, the absolutely maximally entangled (AME) ones, are especially hard to compare as all their subsystems are maximally random. While it is well known that there is no AME state of four qubits, many analytical examples and numerically generated ensembles of four-qutrit AME states are known. However, we prove the surprising result that there is truly only one AME state of four qutrits up to local unitary equivalence. In contrast, for larger local dimensions, the number of local unitary classes of AME states is shown to be infinite. Of special interest is the case of local dimension 6, where it was established recently that a four-party AME state does exist, providing a quantum solution to the classically impossible Euler problem of 36 officers. Based on this, an infinity of quantum solutions are constructed, and we prove that these are not equivalent. The methods developed can be usefully generalized to multipartite states of any number of particles.
Absolutely maximally entangled states of four six-level systems, AME(4,6)(4,6)(4,6), are the quantum solutions of Euler's problem of the thirty-six officers. Until recently all reported solutions were complex, and it was conjectured that no real orthogonal 2-unitary matrix of order 363636 exists. We give real AME(4,6)(4,6)(4,6) states with 606060 non-zero coefficients in {±1,2}/72\{\pm1,\sqrt2\}/\sqrt{72}{±1,2​}/72​. Of their thirty-six officers, 121212 are classical, as some must be whenever fewer than 727272 coefficients are non-zero. They lie in the −1-1−1 eigenspace of an order-444 local symmetry, and on their support the AME conditions become linear. We derive two closed-form families of AME(4,6)(4,6)(4,6) states that meet at one of these states: a 101010-parameter family that is supported on 727272 basis states, and an 111111-parameter family on 606060 basis states. At each of its two ends the first family loses 121212 coefficients, and the AME states on the remaining 606060 basis states form an 111111-parameter family: the second family at one end, and an analogous family at the other. These two 606060-term families contain 409640964096 real AME states up to diagonal local unitaries, 102410241024 of which are limits of the first family. They fall into exactly 202020 classes under local unitaries and permutations of the parties, and we certify their separation with interval arithmetic.
A perfect tensor of order ddd is a state of four ddd-level systems that is maximally entangled under any bipartition. These objects have attracted considerable attention in quantum information and many-body theory. Perfect tensors generalize the combinatorial notion of orthogonal Latin squares (OLS). Deciding whether OLS of a given order exist has historically been a difficult problem. The case d=6d=6d=6 proved particularly thorny, and was popularized by Leonhard Euler in terms of a putative constellation of "36 officers". It took more than a century to show that Euler's puzzle has no solution. After yet another century, its quantum generalization was resolved in the affirmative: 36 entangled officers can be suitably arranged. However, the construction and verification of known instances relies on elaborate computer codes. In this paper, we present the first human-made order-666 perfect tensors. We decompose the Hilbert space (C6)⊗2(\mathbb{C}^6)^{\otimes 2}(C6)⊗2 of two quhexes into the direct sum (C3)⊗2⊕(C3)⊗3(\mathbb{C}^3)^{\otimes 2}\oplus(\mathbb{C}^3)^{\otimes 3}(C3)⊗2⊕(C3)⊗3 comprising superpositions of two-qutrit and three-qutrit states. Perfect tensors arise when certain Clifford unitaries are applied separately to the two sectors. Technically, our construction realizes solutions to the perfect functions ansatz recently proposed by Rather. Generalizing an observation of Bruzda and Życzkowski, we show that any solution of this kind gives rise to a two-unitary complex Hadamard matrix, of which we construct infinite families. Finally, we sketch a formulation of the theory of perfect tensors in terms of quasi-orthogonal decompositions of matrix algebras.