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

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:

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
• Can you specify what a "randomly executed move" is, and why it takes $\Omega(n)$ time? Dec 8, 2020 at 9:30

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