We can think of the Rubik's cube Cayley graph $\Gamma=(V,E)$ with each (colored) edge $E$ being one of the Singmaster moves $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ and each vertex $V$ being one of the $43252003274489856000\approx 4.3e{19}$ different configurations of the $3\times 3\times 3$ cubes.
The diameter of a graph is the longest shortest path in the graph. Classical algorithm for determining the diameter is polynomial in $\vert V \vert$; see, e.g., this answer from a sister site.
As mentioned above, God's number is (related to) this diameter; to know the longest shortest path between to vertices for a Cayley graph on a group, it suffices to know how many steps away from the solved state one is. We know, thanks to Rokicki, Kociemba, Davidson, and Dethridge among others, that God's number is $20$. The algorithms they executed was polynomial in $\vert V\vert$, e.g. polynomial in $4.3e{19}$.
Heiligman's quantum algorithm for graph diameter, mentioned in the comments, achieves a Grover speedup over Djikstra's algorithms, with "a total quantum cost of $O(|V|^{9/4})$." However, I believe Heiligman encodes the graph much as a classical algorithm would; e.g. with $O(|V|)$ qubits. Clearly if $|V|=4.3e{19}$ then this would not help.
Instead, another way to encode a Rubik's cube, as hinted in the other questions, is of course to prepare a uniform superposition over all $4.3e{19}$ states. This only takes $\log 4.3e{19}$ qubits.
Quantum algorithms are good at talking about "eigenvalues" and "eigenvectors" and "eigenstates." Applying all Singmaster moves to a uniform superposition of all $4.3e{19}$ states does not change the state; i.e. the uniform superposition is an eigenstate of the Markov chain on the Cayley graph.
There are relations between the diameter of a graph and the eigenvalues/eigenvectors of the corresponding adjacency/Laplacian matrix, especially the spectral gap, the distance between the two largest eigenvalues ($\lambda_1-\lambda_2$). A quick Google search of "diameter eigenvalue" produces this; I recommend exploring similar Google searches.
Spectral gaps are exactly what limits the adiabatic algorithm. Thus, perhaps by knowing how fast an adiabatic algorithm needs to run to evolve from the uniform superpositon to the solved state for various subgroups/subspaces of the Rubik's cube group, one could estimate the spectral gap, and use this to bound God's number. But I'm quickly out of my league here and I doubt any sense of accuracy is achievable.
