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.

Superposition With Superflip


$$\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).

Hamiltonian for Front Face

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.