# Quantum Algorithm for God's Number

God's number is the worst case of God's algorithm which is

a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves, the idea being that an omniscient being would know an optimal step from any given configuration.

Calculating God's number to be 20 took "35 CPU-years of idle (classical) computer time."

What kind of speed up could be achieved with a quantum approach?

• "God's number" for combinatorial puzzles is related to the diameter of the Cayley-like graph, that is, the largest smallest path in the graph. I don't think the generalized problem to the $n\times n \times n$ puzzles is in $\mathsf{NP}$. I haven't studied this paper - arxiv.org/abs/quant-ph/0303131 - but I think it claims a Grover-speedup over classical. – Mark S Aug 7 '18 at 12:20
• – user820789 Aug 7 '18 at 15:48
• You could ask a question like this for anything which is hard to compute. This doesn't seem to be very constructive. Why would you think that this specific problem might be of interest w.r.t. quantum algorithms? – Norbert Schuch Aug 9 '18 at 18:36
• @Norbert Schuch I cube & do quantum computing. It's a really interesting problem to me (& I would think to anyone else interested in quantum combinatorial optimization). – user820789 Aug 9 '18 at 21:23
• See also mathoverflow.net/questions/77836/… from a sister site. – Mark S Aug 18 '18 at 0:53

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.

• 1st of all, thank you for the excellent answer. I am very interested to find out more about spectral gaps & diabatic processes. Do you know anything about subcubic graphs? Also, do you know anythings about surreal numbers (specifially gaps)? Also, do you have any thoughts on the 2x2 case? Or the n x n case (for $3<n$)? – user820789 Aug 11 '18 at 2:50
• @meowzz, you're welcome. I'm sorry I don't know anything about surreal numbers or subcubic graphs. The Cayley graph above is not cubic and has a valence of $18$ I think ($6$ faces and a quarter, half, or three-quarter move per face). About the $n\times n$ case, the same thinking applies... measure how long $\tau_n$ an adiabatic algorithm takes to evolve into a solved state, use a relation between $\tau_n$ and $\lambda_2$ to bound the spectral gap, and bound the diameter $\delta$ with relation between $\lambda_2$ and $\delta$... – Mark S Aug 11 '18 at 11:30
• When reading the answer it is not yet fully clear "What kind of speed up could be achieved with a quantum approach?". – JanVdA Aug 20 '18 at 8:56
• @JanVdA Thanks for your comment. I never claimed to know all the details to the answer to the bolded question. I merely tried to give some feedback on approaches that might be worth exploring more, and to also lightly counter another comment in the question. Also, someone was very welcoming to a similar question from me. – Mark S Aug 20 '18 at 12:06