# Can we use quantum phase estimation to count how often we can walk from one Rubik's cube position to another?

Consider a state $$\vert\psi\rangle$$ as below, which is in a superposition of a difference between a Rubik's cube in a solved state and a Rubik's cube in the "superflip" state. Here, with $$8$$ cells on each face (apart from the fixed center cell), $$6$$ faces, and $$3$$ qubits to record the color of each cell, $$\vert\psi\rangle$$ has $$8\times 6\times 3=144$$ qubits.

With:

$$\langle F_1,B_1,L_1,R_1,U_1,D_1,F_2,B_2,L_2,R_2,U_2,D_2,F_3,B_3,L_3,R_3,U_3,D_3\rangle\tag 1$$

being a generating set of $$\mathsf{SWAP}$$ circuits for the quarter-turn, half-turn, and three-quarter turn twists of each face, we can simulate $$H_{\text{Rubik's}}$$ as:

$$e^{-i\mathcal H_{\text{Rubik's}}}\approx(F^{1/4}_1B^{1/4}_1L^{1/4}_1R^{1/4}_1U^{1/4}_1D^{1/4}_1F^{1/4}_2\cdots D^{1/4}_2F^{1/4}_3\cdots D^{1/4}_3)^4=:W\tag 2.$$

An example of $$F^{1/4}_2$$ is illustrated below (I'm only showing $$8$$ cells for convenience).

Performing a Von Neumann measurement of a Hamiltonian $$\mathcal H_{\text{Rubik's}}$$ acting on $$\vert\psi\rangle$$ gives a natural probability distribution supported by the eigendecomposition of $$\vert\psi\rangle$$. Indeed, with a quantum phase estimation circuit as below, we can sample from such a distribution, with $$5$$ qubits of precision.

If we were able to execute and sample such a circuit acting on the state $$\vert\psi\rangle$$, could we learn anything about how difficult it is to walk from various states to each other?

For example, my intuition is that if $$\vert\psi\rangle$$ is in a superposition of bases that are "close" to each other under the word metric, then the eigenvalues sampled will be "close" to $$0$$, whereas the superposition of the solved state and the superflip state likely has a decomposition "far away" from $$0$$. Raising the sampled eigenvalues may give a count of (a difference in) the number of walks.

This is based on some ideas from Janzing and Wocjan (1, 2, 3) on some $$\mathrm {BQP}$$-complete problems with large matrices.