5
$\begingroup$

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

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

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.

QPE

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.

$\endgroup$

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.