Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution | Hacker News Reader

Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution

quantamagazine.org

231 pointsnsoonhui99 comments

The 1779 Euler puzzle: "Six army regiments each have six officers of six different ranks. Can the 36 officers be arranged in a 6-by-6 square so that no row or column repeats a rank or regiment?" Euler said it's impossible.

The 1960 proof by mathematicians and computers: "It's impossible."[0]

The 2022 solution(?): "In a paper posted online and submitted to Physical Review Letters, a group of quantum physicists in India and Poland demonstrates that it is possible to arrange 36 officers in a way that fulfills Euler’s criteria — so long as the officers can have a quantum mixture of ranks and regiments."[1]

My question: If we are permitting this (headline style) to be called a "quantum solution" (to a non quantum problem), should we expect and brace for a torrent of "quantum solutions" to previously impossible problems? Are these meaningful? Or just really cool and interesting?

[0] https://www.cambridge.org/core/journals/canadian-journal-of-...

[1] https://arxiv.org/abs/2104.05122

> If we are permitting this (headline style) to be called a "quantum solution" (to a non quantum problem), should we expect and brace for a torrent of "quantum solutions" to previously impossible problems? Are these meaningful?

The paper does something meaningful with its solution - it constructs an "impossible" error-correcting code that you can use if you have a quantum channel. That's not really practical to use yet, but one could imagine one day e.g. sending messages through space slightly more efficiently.

Thank you, I can see why this could actually become practical. I was prematurely wincing at what I thought was watered down use of the word solution but that's just pedantry on my part. Cheers.

But utterly fails to address the Euler puzzle as I Euler was not asking about quantum mixture of ranks and regiments.

That's okay. Euler wasn't trying to arrange these army officers for any sort of practical purpose, the whole point of the puzzle is an exercise in mathematics. So it's mathematically interesting that the puzzle cannot be solved in a conventional manner, but it's also interesting that it can be solved by applying quantum concepts. Interesting research like this is the whole point of Euler's puzzles.

But yeah I guess it's a disappointment to all those army generals who were hoping for a way to arrange their officers in a 6x6 square according to Euler's constraints. The use of quantum ranks may have deleterious effects on battlefield effectiveness.

> So it's mathematically interesting that the puzzle cannot be solved in a conventional manner, but it's also interesting that it can be solved by applying quantum concepts.

I guess the question was: Is the "quantum officers puzzle" the same puzzle as the one proposed by Euler or a variant?

If they're not the same, it's not a "quantum solution" but "a solution to a quantum variant". That can be interesting on its own (with proposals made in the discussions here), it's just that "Yeehaw, we solved something for the first time in 243 years With Quantum[tm]" seems to be the wrong take away (although it might mean the next round of public funding)

I mean this is a common sort of thing, where you take something that has no solution, relax the setting, and find it has a solution in that relaxed setting. You're not finding a solution to the original problem, but you are finding a solution to a generalization, and that's still interesting.

I think it is worth noting that Euler conjectured there was no solution to any square of order 4n+2, but in 1960 it was proved that only orders 2 and 6 have no solutions.

Given that it was just a conjecture, why is it worth noting? Getting back to the main topic, it wasn't only conjectured, but also proven.

It's noteworthy because it's an a conjecture by Euler and because it's an example of hasty generalization. Either Euler jumped to conclusions almost laughably quickly or something interesting happens once n >= 10.

Because the conjecture for the order 6 is just a particular case of his wider conjecture that he posited, it gives a bigger picture.

What does "square of order 4n+2" mean here?

The term "order 4n+2" means a number of the form n (a positive integer) times four, then add two.

So 6 fits (6 is 1 times 4, plus 2) and 10 fits (10 is 2 times 4, plus two) but 12 does not (twelve can not be made by multiplying a positive whole number by four, then adding two to that number).

Thus a 6x6 square is permissible, as is a 10x10 square. But not a 12x12 square.

A square of x by x

for x ∈ {2, 6, 10, 14, 18, 22 ... } = {2, every uneven n multiplied with 2}

4n+2 = 2*(2n+1)

A 4n+2 by 4n+2 square.

I think it is worth noting that not everyone gets 100% right. You're point would be most accurate if Euler was a Quantum computation expert.

I haven't read his biography, so can't know for sure.

Euler was so successful and prolific that the list of discoveries named after him is huge.

So big, in fact, that a great many things are named after the second person to discover them.

He's one of - if not the - greatest mathematicians in history.

I don't know, I felt cheated when I learned about imaginary numbers in high school (wait, you can take the square root of a negative number?). It felt like you had patiently learned the rules of math and then someone just made some shit up.

Probably when I started my slow deviation away from math (certainly a part of why I never majored in it).

It's too bad though. Over the years since I have come to trust mathematicians more and more.

A co-worker explained to me how the imaginary component of complex numbers represents the phase information when performing an FFT. I think he was even trying to explain to me how it is why an FFT is not reversible, why you lose the phase information from the original (but I was already lost).

(Odd too that the human ear cannot distinguish between two audio sources for which every thing is the same but for the phase. Related?)

I am assuming now, from a position of ignorance if that is not obvious, that imaginary numbers are quite clever after all, perhaps neither a hack nor "imaginary".

Imaginary numbers simply represent a different and more powerful system like how integers gain power when you introduce 0 and negative numbers. Rational numbers (fractions) can’t represent irrational numbers like pi or e etc.

It’s often useful because you can use complex numbers as an intermediary step in many calculations (such as solving cubic equations) while still ending up with a non imaginary number at the end.

The history is actually fairly interesting: https://www.youtube.com/watch?v=cUzklzVXJwo

School teaching tends to be authoritarian, so that's a reaction I felt too. "Less than no apples? Minus times minus is plus? What the hell is this and who ordered it?"

I wish it'd been explained like: counting numbers like 1, 2, 3 obey certain laws, e.g. adding in different ways gets the same result. If you relax just a few of the laws in the right way, you can find a broader class of things obeying the shared logic. In the case of complex numbers, we're dropping ordering, and finding that takes us from 1-d sliding and stretching (adding and multiplying) to 2-d, where the stretching becomes stretching and turning.

I think the biggest problem with authoritarian thinking about math is that math is not a discovered set of authoritarian principles, but rather a colossal project to make up weird relationships that satisfy the rules of the weird relationships that were already made up.

Approaching imaginary numbers as:

> "Eventually, mathematicians got sick of not being able to achieve a negative result through multiplication, so Rafael Bombelli finally made up imaginary numbers using the work of other Italians and even some Greeks. Unfortunately for him, most people thought his idea and rule set was stupid until about two hundred years later. We will now learn what sorts of nonsense he made up--those of you who are interested in electricity had better listen close--"

will inevitably lead to a different mindset about math than:

> "Today's lesson is that the square root of negative one is i. Write that down, because it WILL be on the test."

I feel like they could have explained "minus times minus is a plus" using the distributive law.

  -1 x -1 = -1 * (0 - 1)
          = (-1 * 0) - (-1 * 1)

Presumably at this point you were happy with "anything times zero is zero" and "anything times unity is itself", so:

          = 0 - (-1)

and now we can just use the additive laws of negative numbers, which hopefully were intuitive enough:

= 1

They're used in a generalised solution to cubic equations (analogous to the quadratic solution we all learn in high school), where they represent the side length of a square with negative area.

https://www.youtube.com/watch?v=cUzklzVXJwo

Excellent video.

Imaginary numbers seem like something that shouldn’t be taught in high school. Algebra, geometry, trigonometry, and calculus are all useful even if you don’t recall the specifics of the notation and calculation. Imaginary numbers are niche.

They feature fairly prominently in quantum mechanics.

In my humble opinion, imaginary numbers are a core part of algebra, calculus, trigonometry, and physics, and all sufficiently intelligent people should learn about them. The reason exponential curves and sine waves show up all over the place in reality is because they are the solution to some simple differential equations. Imaginary numbers show you how these are fundamentally very similar things. Similarly, imaginary numbers make it clean and simple to solve cubic equations. And the idea that introducing this concept of "imaginary number" makes multiple practical applications much simpler, therefore we added it to mathematics, is core to how mathematics itself evolves.

I’m willing to believe that. But I certainly never learned that. I only briefly got into differential equations by the end of high school. For our program imaginary numbers weren’t much more than learning some rules about how they work exponentially and an awkward introduction to vectors with complex numbers that really should have started with just real numbers.

Maybe just teacher quality though. I can’t forget the frustration of both the class and our calc teacher when she realized our trig teacher from the prior year never conveyed the relationship between various trigonometric identities and the Pythagorean theorem and instantly made it vastly more intuitive.

Imaginary numbers are unfortunately named. It's not a misnomer per se, but they are far from being just figments of imagination.

I mean, I'm no scientist but the article does present it in a way that implies it can be solved by changing the problem / cheating. I mean sure, it might work if the ranks are all ranks at the same time or are in all positions at the same time, to use an overly simplified popular science take of quantum.

To be fair to the paper authors, they embrace and joke about it in their own headline '36 entangled officers'. PopSci headlines are always clickbait/sensationalised.

> PopSci headlines are always clickbait/sensationalised.

For most people this level of dishonesty would get them fired or at least a stern request to leave. If I go to my boss and tell him sure I did my job if my job was something other than what you asked, he will tell me "pls go".

This should be called what it is, lies, and it should not be allowed on HN, and it should get all quantamagazine's social media accounts suspended.

I'm not sure if we are "permitting" anything, but I don't think it would be a bad thing if mathematicians and researchers in quantum computing explored the implications of this field with regards to previously stated problems.[0] Is there a particular justification you suggest a paper in math should have before exploring a problem besides that it's interesting?

[0] https://chaos.if.uj.edu.pl/ZOA/?which=people&lang=en&who=Ada...

It’s mostly just that the solution is to a totally different problem once you remove the constraint that any given square contain only a single value (as opposed to a quantum superposition of values). AFAICT this doesn’t answer any open questions about the original puzzle.

More like "Quantum version of Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Solution". This is like saying "30 year old proof of the minimum number of moves to solve a Rubik's Cube gets broken by putting multiple colors on each cubelet face"

More like "by painting the whole Rubik's cube with the same color". This new amazing algorithm to this previously thought impossible problem is now able to solve it in 0 moves! And no matter which move, it always gets a solution! The quantum hype train says chooo choooo

This would violate the color sum constraint though, that the integral over the cube area of each colour must be equal.

If there's only one color, then that constraint is trivially met.

Good way of thinking about it

>30 year old proof of the minimum number of moves

Isn't it maximum numbers of moves to solve?

Maximum number of moves to solve any configuration. Minimum number of moves to solve for a given configuration.

exactly what I meant - to solve any configuration.

its the smallest number that tells you how many moves are required to solve a rubiks cube, regardless of how that cube was scrambled. lower is better, so its a minimum.

My process.

1) Ugh, they cheated. How dumb.

2) No, wait, that's clever. I like it.

3) Oooh, it's that perennial solution of thinking with orthogonality.

4) Wait, what? The golden ratio's in there?! No. Way! That's so cool. And the solution it's some random garbage, but pretty regimented. Neat-o!

> Wait, what? The golden ratio's in there?! No. Way! That's so cool. And the solution it's some random garbage, but pretty regimented. Neat-o!

The golden ratio is the solution to x(x-1) = 1. And its reciprocal is the solution to x(x+1) = 1. This equation is probably the simplest equation with irrational solutions aside from x*x = 2 and hence appears all over the place in mathematics.

I had a very similar experience.

This has to be one of the cooler instances of the golden ratio.

Another is Conway's Soliders:

A variant of peg solitaire, it takes place on an infinite checkerboard. The board is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". As in peg solitaire, a move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible. (https://en.wikipedia.org/wiki/Conway%27s_Soldiers)

How many soldiers have to be put below the line before the game starts to enable at least one soldier to reach a given height over the line?

For height 1, you need 2 soldiers.

For height 2, you need 4.

For height 3, you need 8.

For height 4, you need ... 20.

For height 5, it's impossible, by the golden ratio.

> For height 5, it's impossible, by the golden ratio.

Strictly speaking, it's Conway's proof uses the golden ratio. But it could be that there's an alternate proof that doesn't use the golden ratio.

Yes, you are right! In fact, to people working in foundations of mathematics it is routine to compile away any explicit use of the golden ratio in Conway's proof and thus obtain a proof which only refers to the integers. However the resulting proof will be less perspicuous. I don't know of any transparent proof avoiding the golden ratio, though it definitely could exist.

In one of Numberphile's more in-depth videos (41 minutes), they have a full video proof of this, including the derivation of where the golden ratio comes from: https://www.youtube.com/watch?v=Or0uWM9bT5w&t=10s

To bring this problem into our kitchen, last summer my fiancee and I block-painted 100 colored and symboled canvases to manipulate around on a 10x10 grid of pegs on our wall[0]

The first solution to this 10x10 version was discovered in 1959, and Euler died believing it impossible... so our most likely expectation is that we won't find the solution in our lifetimes. Still, it's fun to solve progressively bigger sub-puzzles on the grid, and it's nice to always have a nut too tough to crack in your life.

I've set aside this paper to read tomorrow. Naturally, the quantum solutions are not valid on our kitchen wall!

[0] https://imgur.com/a/tPj0tZB

A solution would be exactly as the problem states, one officer, with one rank, on one square, so I don't think the 'Quantum Solution' is actually a solution

> A solution would be exactly as the problem states, one officer, with one rank, on one square, so I don't think the 'Quantum Solution' is actually a solution

That's equivalent to saying that the square root of -1 is not actually number i, because negative numbers don't have square roots. Although it is proven that a solution to the original problem as stated is impossible, putting concepts in a new light expands the possibilities of the original formulation into new interesting areas.

I was going to give the same example. Even simpler example would be dividing 5/2 = x. If all you know is whole numbers there is no solution, but if you introduce fractions you get a solution and a new tool which has many practical applications.

The original problem statement might not mention something, but that might be due to not knowing the solution and insight about fundamental relationship between the numbers that it represents. Unless you are filling a school test where you are expected a specific answer (even when it's wrong in more general case) the "children story" part of a math problem shouldn't be mistaken for what it actually represents. The more general solution might not be applicable in all cases due to real world limitations, but in some it may. You can't (don't want to) split one of 5 officers in half, but having half an apple or sack of grain is not a problem. If Euler knew the solution maybe he would have chosen something else than officers and ranks to describe the problem.

It's an interesting solution to a related problem, if you want to be pedantic.

I think it is not unimportant ti be padantic here, a lot of classical problems and games generalize naturally to a quantum version of that problem which then admits for different solutions. I think that is great. But also (sometimes I think intentionally) misleading the non expert.

Agreed.

I'm a mathematician by training. So when I said pedantic, I didn't mean 'bad'.

Is it typical for quantum computing to use such specialized terminology?

I have a good understanding (i.e. graduate level study) of general quantum physics as well as pure mathematics in general, and can generally read quantum physics papers without issue and somewhat understand pure mathematics abstracts at the least (though the extent of my understanding depends on the subdiscipline).

And yet, the abstract for this paper reads like complete technobabble to me. It's filled with individual words which I know like "entangled", "orthogonal", "tensor", etc. and yet after reading both the article and abstract I have no idea what the hell is going on here.

Reading the body of the article, I can start to understand but it looks like I'll need to do a lot of study into quantum computing to get up to speed on it.

Yeah, I went into the article thinking, "Ooh, this looks fun and not too hard to grok." Once they started talking about perpendicularity and entanglement, I discovered I was quite mistaken.

“Another surprise was the coefficients that appear in the entries of the quantum Latin square. These coefficients are numbers that tell you, essentially, how much weight to give different terms in a superposition. Curiously, the ratio of the coefficients that the algorithm landed on was Φ, or 1.618…, the famous golden ratio.”

This suggests to me that quantum max-flow would yield the same solution. You just need a bipartite graph superposition.

Not that I actually know enough to justify this intuition. The knowledge is seeping through the multiverse from versions of myself that bothered getting a phd.

I almost thought Euler was wrong*, but that's just different problem, yet still interesting.

*) that would just destroyed internal peace and general view on the universe.

But he was wrong. He conjectured there was no solution to any square of order 4n+2, but actually only orders 2 and 6 have no solutions.

A conjecture is not a proof, hence not something taken seriously. I'm sure he conjectured that there's no black swans (or similar) at some point, but that's not worth remembering.

Which one is that

Will we ever get to “why” 6 is a special size. Thats what is really interesting to me.

The golden ratio thing: i wonder if thats an artefact of the algorithm? In other words there is a solution involving pi or other arbitrary constants? But the algorithm had some fibonacci-ness to it

The latest advancements in building materials and structural engineering allows us to build a bridge over the Atlantic cutting the France to USA commuting time to a mere 30 minutes! (*) Despite the huge importance of the discovery motorists do not appear to be very satisfied with the solution.

* as long as we can fold space and worm holes exist

I see in my crystal ball a future where some of our existing science fields turn out to be alchemy equivalents. This kind of solutions where you just cleverly rearrange the data to satisfy a success criteria that just isn't satisfying at all for practical purposes would never fly for any real-life problems. It smells like "I make big discovery! Can I haz founding now?"

The article mentions a Sudoku variant of the idea, dubbed SudoQ, where instead of integers 1-9 you have (as I understand it) orthogonal quantum vectors. But it seems like no one implemented this as a game -- anyone know if this would be remotely comprehensible for humans to play?

>Quantum Latin squares were quickly adopted by a community of theoretical physicists and mathematicians interested in their unusual properties. Last year, the French mathematical physicists Ion Nechita and Jordi Pillet created a quantum version of Sudoku — SudoQ. Instead of using the integers 0 through 9, in SudoQ the rows, columns and subsquares each have nine perpendicular vectors.

> so long as the officers can have a quantum mixture of ranks and regiments.

With that relaxation, it’s trivial, isn’t it? Just put identical officers on each square that are a mix of 1/36th of each of the 36 (rank, regiment) combinations.

They must be restricting the amount of entanglement somehow to make this an interesting result. From glancing the paper, I didn’t see what they did. Can anybody explain?

For example, is it already hard to find a solution if you disallow only that one trivial solution?

You are thinking continuous relaxation which is a lot less thight as entanglement enforces additional rules.

>"Two coins can be maximally entangled, and so can three, but not four"

How can 3 coins be maximally entangled? Is there also a quantum solution to entanglement monogamy?

The multi-party maximal-entanglement definition used in the paper is "no matter how you cut it into two pieces, the two pieces are maximally entangled". Monogamy isn't an obstacle because the definition is always using two pieces.

A 3-qubit state with this property is the |000> + |111> state. But |0000> + |1111> doesn't work as a 4-qubit state because when you cut it into evenly sized pieces you should be able to distill 2 bell pairs instead of 1.

Isn't this cheating?

"Euler thought no such 6-by-6 square exists, recently the game has changed. In a paper posted online and submitted to Physical Review Letters, a group of quantum physicists in India and Poland demonstrates that it is possible to arrange 36 officers in a way that fulfills Euler’s criteria — so long as the officers can have a quantum mixture of ranks and regiments."

It is lying, so kind of, I mean it is not exactly cheating because it does not solve the puzzle as it is not solveable, contrary to the false headline, but it is cheating in that lying to claim that it is a solution. Maybe some manner of fraud?

I just finished watching a really nice talk _An Evening with Leonhard Euler_ [1] that discussed a small fraction of his work and the massive amount of papers he produced (hundreds of which were only published after his death)

[1] https://www.youtube.com/watch?v=h-DV26x6n_Q

I always suggest that, when faced with an impossible problem, you go and solve a slightly different one. This is a fascinating take on the "slightly different problem" thing.

I was with them, until the line about entanglement only with 'adjacent regiments' and 'adjacent ranks'. Does that mean if I 'recolor' the problem by changing the names of the ranks or regiments, the quantum solution falls apart? That seems unintuitive, and further aligns quantum effects more with 'what people think about a problem' than with reality and the universe.

they way the puzzle is described in the article i really dont get whats the problem of a 6x6. especially after looking at the chess board 5x5. assume every number represents a different chess figure:

    1 2 3 4 5 6    21
    2 3 1 5 6 4    21
    3 1 2 6 4 5    21
    4 5 6 1 2 3    21
    5 6 4 2 3 1    21
    6 4 5 3 1 2    21

   212121212121

You've missed the fact that there are two attributes, rank and regiment. So it's something like this for a 3x3:

1A - 2B - 3C

2C - 3A - 1B

3B - 1C - 2A

so, something like:

a6 - b2 - c4 - d3 - e2 - f1

f5 - a4 - b3 - c2 - d1 - e6

e4 - f3 - a2 - b1 - c6 - d5

d3 - e2 - f1 - a6 - b5 - c4

c2 - d1 - e6 - f5 - a4 - b3

b1 - c6 - d5 - e4 - f3 - a2

Close. Pretty sure you have to use all values for letter and number combination. For example, you don't have f2.

You have two 2s in the second column

ok thank you. after studying he article again it gets clear.

6 minutes solution here : https://replit.com/@vcch/VitalOrangeDatalogs

I'm obviously missing something dramatic here.. I guess I don't even understand the Puzzle itself..?

Re1Ra1 Re2Ra2 Re3Ra3 Re4Ra4 Re5Ra5 Re6Ra6

Re2Ra2 Re3Ra3 Re4Ra4 Re5Ra5 Re6Ra6 Re1Ra1

Re3Ra3 Re4Ra4 Re5Ra5 Re6Ra6 Re1Ra1 Re2Ra2

Re4Ra4 Re5Ra5 Re6Ra6 Re1Ra1 Re2Ra2 Re3Ra3

Re5Ra5 Re6Ra6 Re1Ra1 Re2Ra2 Re3Ra3 Re4Ra4

Re6Ra6 Re1Ra1 Re2Ra2 Re3Ra3 Re4Ra4 Re5Ra5

You repeat the same value multiple times (eg "Re1Ra1"), which also implies you are missing some. The square has to contain 36 different entries.

Thank you.

Funny that they mention this game in the appendix of the paper: https://en.wikipedia.org/wiki/36_Cube

Title should be: Euler’s 243-Year-Old Impossible Puzzle Gets a Quantum ‘Solution’

But the puzzle was not asking about quantum ranks, so no, that would also be a false.

Can anyone share an intuition why 6x6 is a unique special case?

It's quite surprise on how did they take this one.

I couldn't help but go from cynical to "giddy child playing with mathematics" as I read this paper.

I don't get such high-matter maths as 'quantum maths' at all.

This all sounds like some bullshit.

What was the solution?

> Critically, the quantum states that compose these officers have a special relationship called entanglement, which involves a correlation between different entities. If a red king is entangled with an orange queen, for instance, then even if the king and queen are both in superpositions of multiple regiments, observing that the king is red tells you immediately that the queen is orange.

Okay.

> The theory seemed to work, but to prove it, the authors had to construct a 6-by-6 array filled with quantum officers. ... > When the researchers repeated the algorithm over and over, the puzzle array cycled closer and closer to being a true solution. Eventually, the researchers reached a point where they could see the pattern and fill in the few remaining entries by hand.

So what is the goddamn solution???

There isn't one, cause that's all bullshit and they didn't solve anything. I can claim I solved all the proved unsolvable math problems that way (I just superpositioned everything quantumly so everything has a solution).

Grant money well wasted.

“So what is the goddamn solution???”

It’s on page four: https://arxiv.org/pdf/2104.05122.pdf

It might not mean much to you unless you take a deep excursion into rigorous math with Dirac notation and Hilbert spaces and God-knows-what. The quanta magazine article is there for you if you’re somewhat generally interested and don’t have years to invest in study.

Sorry this is off topic but your name makes your comment make so much sense.

It isn't a solution to the problem in the way Euler meant it.

It is a bit like saying no one can climb this mountain, and then someone gets there by helicopter.

The Kobayashi Maru [0] is a no-win scenario. Unless you reprogram the simulation. Kirk called it original thinking. I call it cheating.

[0] https://memory-alpha.fandom.com/wiki/Kobayashi_Maru_scenario

The funny thing about that is, with original star trek going through all kinds of crazy situations, thinking outside of the box and changing the simulation was probably the correct solution to an unwinnable problem multiple times, in some cases literally.

In this case it solves a slightly different problem, but for many situations that may be enough.

TLDR; Euler's puzzle does in fact not get any solution, and HN is okay with false headlines.

Reply on news.ycombinator.com