I'm interested in, but confused about, local Hamiltonian simulation. I don't yet have enough intuition regarding even the approach set forth by Lloyd in 1997. I think Lloyd's recipe is to repeatedly run a "small" circuit of unitary gates to simulate a larger unitary, relying on the bounds of the Baker-Campbell-Hausdorff formula to deal with nonabelian properties of the Hamiltonian.

To motivate my question, consider initially the adjacency matrix of the Cayley graph of the subgroup of the Rubik's Cube group generated by the six half-turn twists $\langle F^2, B^2, L^2, R^2, U^2, D^2\rangle$.

The adjacency matrix of the Cayley graph can be seen to be a local Hermitian matrix:

$$H = \sum_{j \mathop =1}^6 H_j$$

where each $H_j$ is the permutation matrix for the respective face.

Half-Twist of Front Face

There are $48$ cells on the Rubik's cube (excluding the fixed center cells), and each cell can be in one of $6$ colors. Indeed, we can represent the cube with $48$ registers of $3$ qubits each; we might have a simple mapping such as $\vert 001\rangle\mapsto\text{RED},\vert 010\rangle\mapsto\text{BLUE},\ldots$.

Shown above is the front face before and after a half-twist $F^2$ - for simplicity I'm not showing the other cells adjacent to the corners/edges. Half-twists of each face appear to be a simple sequence of SWAP gates.

There are also "square-root of SWAP" gates, and even generalized "$n^{th}$ root of SWAP gates". Also shown above is an "$n^{th}$ root" of the $F^2$ operator, that I call $f^2$. Repeating such gates $n$ times may realize the full SWAP/the full $F^2$ operator.

With this setup, does it make sense to consider Hamiltonian simulation of the adjacency matrix of the Cayley graph of the group, with a repeated application of such "$n^{th}$-root-of-swap" gates, for each different face of the cube?

For example, letting lower-case $f^2$ be the $n^{th}$ root of $F^2$ (and $u^2$ be the $n^{th}$ root of $U^2$, etc.), for large enough $n$ can we simulate:

$$e^{-iHt}\approx (f^2b^2l^2r^2u^2d^2)^n?$$

Are such generalized SWAP gates/$n^{th}$ root of SWAP gates useful for Hamiltonian simulation?


The two-squares subgroup of the Rubik's cube group may be decomposed as a sum of 2-local Hamiltonians I think; the full Rubik's cube group is generated by the quarter-turn moves $\langle F,B,L,R,U,D,F',B',L’,R',U',D'\rangle$, which I think may be decomposed as a sum of 4-local Hamiltonians.

But is this the right recipe for certain local Hamiltonian simulation of permutation groups - for large enough $n$ do we take the $n^{th}$ root of general SWAP gates for each generator, and repeatedly apply such gates?

I'm starting to kind of envision local Hamiltonian simulation as a bit akin to "Lie-algebrafication" of a Lie group.


1 Answer 1


--Self-answer made CW--

The local circuit labelled $f^2$ above is likely incomplete and does not create the kind of entanglement I envisioned, as it suggests that $\vert\mathrm A\rangle$ can be swapped with $\vert\mathrm B\rangle$, independent of $\vert\mathrm C\rangle$ being swapped with $\vert\mathrm D\rangle$, etc. For example such a circuit corresponds to a Rubik's cube with a number of extra degrees of freedom.

Based on some comments from @Craig_Gidney , I believe a better circuit should use an ancilla to record the phase of the $\mathsf{SWAP}$ operation $F^2$.


For example, another circuit would be as above; the first half performs the quantum phase estimation to record the phase in the top ancilla, then we take the square root of that ancilla with the $\mathrm S$ gate, then we uncompute.

I think using a $\mathrm T$ gate instead of an $\mathrm S$ gate would calculate the $4^{th}$ root, instead of the square root. Further for the half-twist circuits $F^2,B^2,\ldots$ we need one ancilla as shown above, as the eigenvalues of the half-twists are $\{\pm 1\}$; however, for quarter-twist circuits $F, U,\ldots$ I think we would need two ancillae as $F^4=B^4=\cdots=\mathbb I$ and the eigenvalues are the fourth roots of unity, $\{\pm 1, \pm i\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.