Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

Question

Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable algorithms to solve such large cubes can be created with the methods listed here:

• link 1

• link 2

Such can be executed in $O(n^2)$ time, considering that they rely on short sequences of moves that only displace a couple of cubes, and do not have to compute individual rotations. But scrambling is another story. Given that a randomly executed move takes time $\Omega(n)$ and the diameter of the graph of the group of Rubik's cubes is $\Theta(n^2/\log n)$, a naive scramble would take $\Omega(n^3/ \log n)$, which is not at all feasible. Given that, is there an algorithm for scrambling large Rubik's cubes which:

1. Takes $O(n^{2+\epsilon})$ time
2. Produces every possible reachable configuration with positive probability, and only produces such configurations
3. Is not extremely skewed

Answer 1

Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly. A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd. Divide the cubies into orbits, then generate a random permutation for each orbit with the restriction that the total permutation across all orbits must be even. Then generate orientations for all edge and corner cubies, with a mod-2 parity restriction on each edge orbit and a mod-3 parity restriction on the corners.

I believe that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes uniformly distributed across the group.

This takes $O(N^2)$ time.