3
$\begingroup$

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}?$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! This is helpful. I think I've been confusing the adjacency matrix $A$ with the Laplacian matrix $L=D-A$, with $D$ the degree matrix (which is $\mathbb I$ for permutation matrices $A$). I think if $A^2=\mathbb I$ then $e^{L/n}=A^{1/n}$ but in general it is not the case, as you say, that $e^{A/n}\approx A^{1/n}$. If $A^3=\mathbb I$ as in my question/your example, there might be a similar relation. $\endgroup$
    – Mark S
    Sep 19 at 14:25
  • $\begingroup$ I see, that helps me understand your motivation a bit better $\endgroup$ Sep 19 at 14:51

Your Answer

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

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