13 ms·
Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution
- amai 5y agoFunny that they mention this game in the appendix of the paper: https://en.wikipedia.org/wiki/36_Cube https://en.wikipedia.org/wiki/36_Cube
- madsr 5y agoI'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
- vcch92500 5y ago6 minutes solution here : https://replit.com/@vcch/VitalOrangeDatalogs https://replit.com/@vcch/VitalOrangeDatalogs
- kleer001 5y agoMy 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!
- randtrain34 5y agoThis has to be one of the cooler instances of the golden ratio.
- IngoBlechschmid 5y agoAnother 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 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.
- jerf 5y agoIn 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 https://www.youtube.com/watch?v=Or0uWM9bT5w&t=10s
- tomerv 5y ago> 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.
- IngoBlechschmid 5y agoYes, 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.
- emptybits 5y agoThe 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-mathematics/article/further-results-on-the-construction-of-mutually-orthogonal-latin-squares-and-the-falsity-of-eulers-conjecture/1152262BF046F8632638FE9C10610136 https://www.cambridge.org/core/journals/canadian-journal-of-... [1] https://arxiv.org/abs/2104.05122 https://arxiv.org/abs/2104.05122
- nappy 5y agoI'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=AdamBurchardt https://chaos.if.uj.edu.pl/ZOA/?which=people&lang=en&who=Ada...
- MobiusHorizons 5y agoIt’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.
- lmm 5y ago> 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.
- ehvatum 5y ago“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.
- neaumusic 5y agoA 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
- eru 5y agoIt's an interesting solution to a related problem, if you want to be pedantic.
- andi999 5y agoI 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.
- eru 5y agoAgreed. I'm a mathematician by training. So when I said pedantic, I didn't mean 'bad'.
- TuringTest 5y ago> 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.
- Karliss 5y agoI 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.
- causi 5y agoMore 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"
- maxwell86 5y agoMore 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
- xxs 5y ago>30 year old proof of the minimum number of moves Isn't it maximum numbers of moves to solve?
- xmprt 5y agoMaximum number of moves to solve any configuration. Minimum number of moves to solve for a given configuration.
- 5y ago
- mathfailure 5y agoI 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.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- motoxpro 5y agoSorry this is off topic but your name makes your comment make so much sense.
- ehvatum 5y ago“So what is the goddamn solution???” It’s on page four: https://arxiv.org/pdf/2104.05122.pdf 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.
- beardyw 5y agoIt 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.
- aphroz 5y ago>"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?
- Strilanc 5y agoThe 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.
- bladelessninja2 5y agoI 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.
- LudwigNagasena 5y agoBut 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.
- convery 5y agoA 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.
- dankwizard 5y agoWhich one is that
- ummonk 5y agoIs 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.
- Jeff_Brown 5y agoYeah, 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.
- quickthrower2 5y agoWill 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
- trabant00 5y agoThe 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?"
- sorokod 5y agoCan anyone share an intuition why 6x6 is a unique special case?
- rbanffy 5y agoI 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.
- W0lf 5y agoI 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 https://www.youtube.com/watch?v=h-DV26x6n_Q
- unholiness 5y agoTo 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 https://imgur.com/a/tPj0tZB
- gigatexal 5y agoIsn'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."
- zohch 5y agoIt 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?
- Someone 5y ago> 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?
- freemint 5y agoYou are thinking continuous relaxation which is a lot less thight as entanglement enforces additional rules.
- zczc 5y agoTitle should be: Euler’s 243-Year-Old Impossible Puzzle Gets a Quantum ‘Solution’
- zohch 5y agoBut the puzzle was not asking about quantum ranks, so no, that would also be a false.
- cbsmith 5y agoI couldn't help but go from cynical to "giddy child playing with mathematics" as I read this paper.
- xony 5y ago
- soliton4 5y agothey 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
- tridentboy 5y agoYou'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
- ohnoNotAgain321 5y agoso, 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 ?
- soliton4 5y agook thank you. after studying he article again it gets clear.
- zohch 5y agoTLDR; Euler's puzzle does in fact not get any solution, and HN is okay with false headlines.
- echopurity 5y ago
- brenelson 5y agoIt's quite surprise on how did they take this one.
- JoeAltmaier 5y agoI 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.
- SilasX 5y agoThe 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.