Can I use the Lie product formula to simulate the Hamiltonian of an adjacency matrix by using the QPE to take Nth roots of permutation matrices?

Question

I have gotten some great help recently on Hamiltonian simulation, and am interested in using Hamiltonian simulation to explore (classical) random walks on large graphs, but I'm running up against limitations on my knowledge of linear algebra and matrix exponentials.

To get started suppose I have a large, undirected graph, whose adjacency matrix $W$ I can write as a sum of a number of permutation matrices of varying order, i.e.:

$$W=A+B+C+D,$$

where $W$ is a (Hermitian) symmetric $(0,1)$ matrix and each of $A,B,C,D$ are (unitary) permutation matrices. Incidentally in my particular example I have $AC=BD=\mathbb{I}$, but otherwise none of $A,B$ or $C,D$ commute with each other. Further I can express each of $A,B,C,D$ as a simple sequence of $\mathsf{SWAP}$ gates, each acting on a small number of (some overlapping set of) qubits.

I also have that, e.g., $A^3=C^3=B^4=D^4=\mathbb I;$ that is, I know the eigenvalues of each of $A,B,C,D$ are cube roots and 4th roots of unity. I think I can use my knowledge of the eigenvalues of $A,B,C,D$ in a quantum phase estimation algorithm to create circuits for the $N^{th}$ roots of each of $A,B,C,D$ for large enough $N$; e.g. I have gates for $A^{1/N},B^{1/N},$ etc.

But then can I use what I know to simulate $e^{W}$ as $$e^{W}=e^{A+B+C+D}= \lim_{N \rightarrow \infty} (e^{A/N}e^{B/N}e^{C/N}e^{D/N})^N\approx(A^{1/N}B^{1/N}C^{1/N}D^{1/N})^N?$$

Can I repeatedly use quantum phase estimation on the permutation matrices $A,B,C,D$ to loop through the $N^{th}$ roots of each of $A,B,C,D?$

Is $(A^{1/N}B^{1/N}C^{1/N}D^{1/N})^N$ the right approximation for $e^{A+B+C+D}?$

Answer 1

I don't think the last step holds. For example, choose $A$ to be the permutation matrix $$A=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},$$ which indeed satisfies $A^3=\mathbb{I}$. Mathematica can perform both of the following: $$A^{1/n}=\left( \begin{array}{ccc} \frac{1}{3} \left(2 \cos \left(\frac{2 \pi }{3 n}\right)+1\right) & \frac{1}{3} \left(-\cos \left(\frac{2 \pi }{3 n}\right)-\sqrt{3} \sin \left(\frac{2 \pi }{3 n}\right)+1\right) & \frac{1}{3} \left(-\cos \left(\frac{2 \pi }{3 n}\right)+\sin \left(\frac{2 \pi }{3 n}\right) \sqrt{3}+1\right) \\ \frac{1}{3} \left(1-2 \cos \left(\frac{(n+2) \pi }{3 n}\right)\right) & \frac{1}{3} \left(2 \cos \left(\frac{2 \pi }{3 n}\right)+1\right) & \frac{1}{3} \left(-\cos \left(\frac{2 \pi }{3 n}\right)-\sqrt{3} \sin \left(\frac{2 \pi }{3 n}\right)+1\right) \\ \frac{1}{3} \left(-\cos \left(\frac{2 \pi }{3 n}\right)-\sqrt{3} \sin \left(\frac{2 \pi }{3 n}\right)+1\right) & \frac{1}{3} \left(-\cos \left(\frac{2 \pi }{3 n}\right)+\sin \left(\frac{2 \pi }{3 n}\right) \sqrt{3}+1\right) & \frac{1}{3} \left(2 \cos \left(\frac{2 \pi }{3 n}\right)+1\right) \\ \end{array} \right)$$ and $$e^{A/n}=\left( \begin{array}{ccc} \frac{1}{3} \left(2 e^{-\frac{1}{2 n}} \cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{1/n}\right) & \frac{e^{1/n}}{3}-\frac{1}{3} e^{-\frac{1}{2 n}} \left(\cos \left(\frac{\sqrt{3}}{2 n}\right)+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) & \frac{1}{3} e^{-\frac{1}{2 n}} \left(-\cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{\frac{3}{2 n}}+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) \\ \frac{1}{3} e^{-\frac{1}{2 n}} \left(-\cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{\frac{3}{2 n}}+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) & \frac{1}{3} \left(2 e^{-\frac{1}{2 n}} \cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{1/n}\right) & \frac{e^{1/n}}{3}-\frac{1}{3} e^{-\frac{1}{2 n}} \left(\cos \left(\frac{\sqrt{3}}{2 n}\right)+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) \\ \frac{e^{1/n}}{3}-\frac{1}{3} e^{-\frac{1}{2 n}} \left(\cos \left(\frac{\sqrt{3}}{2 n}\right)+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) & \frac{1}{3} e^{-\frac{1}{2 n}} \left(-\cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{\frac{3}{2 n}}+\sin \left(\frac{\sqrt{3}}{2 n}\right) \sqrt{3}\right) & \frac{1}{3} \left(2 e^{-\frac{1}{2 n}} \cos \left(\frac{\sqrt{3}}{2 n}\right)+e^{1/n}\right) \\ \end{array} \right).$$ These expressions are completely different. For example, expanding up to $\mathcal{O}(1/n^2)$, $$A^{1/n}\approx \left( \begin{array}{ccc} 1-\frac{4 \pi ^2}{27 n^2} & \frac{2 \pi ^2}{27 n^2}-\frac{2 \pi }{3 \sqrt{3} n} & \frac{2 \pi ^2}{27 n^2}+\frac{2 \pi }{3 \sqrt{3} n} \\ \frac{2 \pi ^2}{27 n^2}+\frac{2 \pi }{3 \sqrt{3} n} & 1-\frac{4 \pi ^2}{27 n^2} & \frac{2 \pi ^2}{27 n^2}-\frac{2 \pi }{3 \sqrt{3} n} \\ \frac{2 \pi ^2}{27 n^2}-\frac{2 \pi }{3 \sqrt{3} n} & \frac{2 \pi ^2}{27 n^2}+\frac{2 \pi }{3 \sqrt{3} n} & 1-\frac{4 \pi ^2}{27 n^2} \\ \end{array} \right)$$ and $$e^{A/n}\approx \left( \begin{array}{ccc} 1 & \frac{1}{2 n^2} & \frac{1}{n} \\ \frac{1}{n} & 1 & \frac{1}{2 n^2} \\ \frac{1}{2 n^2} & \frac{1}{n} & 1 \\ \end{array} \right).$$ These don't even agree to order $\mathcal{O}(1/n)$ and only agree in the actual limit when $\lim_{n\to\infty}A^{1/n}=\lim_{n\to\infty}e^{A/n}=\mathbb{I}$, but that's no help.