The XOR swap trick also features in the compilation/synthesis of quantum algorithms, where the XOR instruction (in the form of a CNOT gate) is fundamental in many architectures, and where native swapping need not be available.
One extension that I ran into, and which I think forms a nice problem is the following:
Just like the XOR swap trick can be used to swap to variables (and let's just say that they're bools), it can be extended to implement any permutation of the variables: suppose that the permutation is written as a composition of n transpositions (i.e., swaps of pairs), and that is the minimal number of transpositions that let's you do that. Each transposition can be implemented by 3 XORs, by the XOR swap trick for pairs, and so the full permutation can be implemented by 3n XORs. Now here's the question: Is it possible to come up with a way of doing it with less than 3n, or can we find a permutation that has a shortcut through XOR-land (not allowing any other kinds of instructions)? In other words, is XOR-swapping XOR-optimal?
I'm not going to spoil it, but only last year a paper was published in the quantum information literature that contains an answer [0]. I ended up making a little game where you get to play around with XOR-optimizing not only permutations, but general linear reversible circuits. [1]
I don't remember if it's ever explicitly stated, but I certainly took that to be the implication. Maybe it's actually funnier if they're doing it pro bono, now I am suddenly unsure.
Just to not feed the witch hunt further, note that human 30 second solve times can be entirely possible for the easiest puzzles, with enough experience, practice, and a bit of risk-taking; see e.g. https://adventofcode.com/2021/leaderboard/day/1 part 1. But the 4 second solution times we saw last year are not, no matter how you look at it.
But yes, you would have people openly share repositories for automatically ingesting the puzzle text, solving the puzzles, and submitting the results the moment the puzzles opened, leading to inhuman solution times. So, despite the rules stating that you can't do that, the result is that whenever the puzzles were easy enough for an LLM to solve them with high probability – and most of them are – the leaderboards would be overrun with such solutions.
In 2023, the LLMs would still struggle enough that the overall leaderboard (taking all 25 ⋅ 2 puzzles into account) would still be dominated by ordinary people (many of them recording their solutions), in 2024 that was no longer the case. Personally I would go from being able to top 100 regularly, to almost never being able to. I'm going to miss the thrill, and think it's a bit saddening that we can't have nice things, but also ultimately think that getting rid of it is the best option.
I don't understand why this is "hard". Doesn't a donut have this coveted property? I can't think of a way to drill a hole in a donut that would allow a donut through.
Hm, yeah, tested it down to about 500 px width, and the low-resolution devices in Chromium but that was too optimistic then. The modals should of course be closeable, and both game boards simultaneously visible. Played around with the modals a bit, so maybe it works better now?
One extension that I ran into, and which I think forms a nice problem is the following:
Just like the XOR swap trick can be used to swap to variables (and let's just say that they're bools), it can be extended to implement any permutation of the variables: suppose that the permutation is written as a composition of n transpositions (i.e., swaps of pairs), and that is the minimal number of transpositions that let's you do that. Each transposition can be implemented by 3 XORs, by the XOR swap trick for pairs, and so the full permutation can be implemented by 3n XORs. Now here's the question: Is it possible to come up with a way of doing it with less than 3n, or can we find a permutation that has a shortcut through XOR-land (not allowing any other kinds of instructions)? In other words, is XOR-swapping XOR-optimal?
I'm not going to spoil it, but only last year a paper was published in the quantum information literature that contains an answer [0]. I ended up making a little game where you get to play around with XOR-optimizing not only permutations, but general linear reversible circuits. [1]
[0] https://link.springer.com/article/10.1007/s11128-025-04831-5
[1] https://swapple.fuglede.dk
reply