# Could the Hamiltonian of a 2x2 Rubik's Cube be simulated with a NISQ device?

Consider the four cells on each of the six faces of the 2x2x2 Rubik's cube (the pocket cube). We can construct and simulate a quarter-turn Hamiltonian as below. $$^*$$

Let $$\langle F_1,U_1,R_1\rangle$$ be the quarter-turn moves that rotate each of the front face, the upper face, and the right face in the clockwise direction. Similarly let $$\langle F_3,U_3,R_3\rangle$$ be the counter-clockwise generators; let the half-turns be $$\langle F_2,U_2,R_2\rangle.$$

If we hold the cube such that the face with cells $$\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$$ is in the front, we have the SWAP circuits for example as above. Each of $$F_1,F_2,F_3$$ act on twelve qudits, where each of $$\vert\mathrm{A}\rangle,\vert\mathrm{B}\rangle,\ldots,\vert\mathrm{V}\rangle$$ are registers that can be in a superposition of six different colors; thus the pocket cube has natural $$k=12$$-local, $$d=6$$-dimensional Hamiltonian $$\mathcal{H}$$. Both $$F_1$$ and $$F_3$$ use nine SWAPs, while $$F_2$$ only uses six.

We know that the order of each of the quarter-turn moves is four, and we can use this to construct circuits for the square-root of a quarter-turn move.

Indeed, following the recipe outlined in this question, we can prepare circuits for the roots of each generator; $$\sqrt{F_1}$$ is an example as above. This uses $$9+6+6+9=30$$ controlled-SWAP (CSWAP) gates with $$H$$ and $$S$$ gates for the quantum phase estimation. The two reusable ancillae store the phases of the eigenspace, while $$\vert\psi\rangle$$ is a register of $$24$$ six-dimensional qudits (or $$24\times 3=72$$ qubits).

From here, we can Trotterize to simulate the quarter-turn Hamiltonian of the 2x2 Rubik's cube, with two iterations of each of the roots:

$$e^{-i \mathcal{H}t}\approx\big (\sqrt{F_1}\sqrt{U_1}\sqrt{R_1}\sqrt{F_3}\sqrt{U_3}\sqrt{R_3}\big )^2=:W.$$

By squaring square roots, our Trotter factor is two; with six generators and thirty CSWAPs per generator, we can simulate the Hamiltonian with only $$2\times 6\times 30=360$$ six-dimensional CSWAP gates. $$^\dagger$$

With $$V$$ being a circuit to prepare the initial state $$\vert\psi\rangle$$ for example to the starting position of the cube, we can do a Hadamard test on $$W$$ as below.

Here, each Fredkin gate would be upgraded to a CCSWAP gate (as we'd need to control on both the measured, answer qubit as well as on the ancillae qubits for when we take the square roots).

But my specific question is: is it realistic to suppose that a circuit with a couple hundred CCSWAPs is small enough to fit into present or near-future NISQ-era devices?

I suspect that most of the loss in fidelity would come from these CCSWAP gates, and not from the $$H$$ or $$S$$ gates, or from the state-preparation circuit $$V$$. If the overhead to compile/transcribe such a controlled-$$W$$ circuit to the native gates and topology of a NISQ device is not too bad, the overall fidelity may still be appreciably greater than zero, and a post-classical signal may be observed.

With transmon processors approaching or exceeding three-nine's nowadays for the fidelity of two-qubit gates, an overall circuit fidelity of a circuit with a thousand(ish) two-qubit gates, acting on less than a hundred qubits, might be appreciably above zero, even accounting for all of the necessary SWAP gates due to specific connectivity of the transmon processors.

$$^*$$ Compared to the previous question, here we (1) reduce our Trotter factor to two instead of four, (2) iterate only over the roots of the quarter-turn generators instead of both the quarter-turn and half-turn generators, (3) prepare our initial state into a fixed basis state as opposed to a superposition of a difference of two states, and (4) ask only about a Hadamard test instead of the full quantum phase estimation. Perhaps these simplifications are enough to squeeze into a NISQ device while still offering some post-classical advantage.

$$^\dagger$$ Upon reconsideration, it appears to make much more sense to define the Hamiltonian simulation as $$\big (\sqrt{F_1}\sqrt{F_3}\sqrt{R_1}\sqrt{R_3}\sqrt{U_1}\sqrt{U_3}\big )^2$$, i.e. have the counterclockwise roots follow the respective clockwise roots, as there is much cancelation and this may reduce the depth significantly.