Background and history

The mid-90's to early 2000's work on Hamiltonian simulation saw some pretty rapid advances. Within two years of Shor's algorithm, Lloyd outlined how Trotterization can lead to efficient local Hamiltonian simulation such as of:


Furthermore the 2000 publication of the first edition of Mike and Ike synthesized much of the resulting studies up to that point and sketched how more involved Hamiltonian simulation can occur when eigenvalues of individual matrices in the Hamiltonian are known.

Childs et al. then cleverly leveraged Mike and Ike's circuit to solve a "welded trees" problem, by viewing the welded tree graph as an adjacency matrix that they partition or edge-color into a sum of nine different, simpler Hamiltonians; they then Trotterize these nine graphs to simulate a quantum walk of a particle tunneling from one end of the welded tree to the other, by SWAP'ping the particle's position from node to node over the tree.

Aharanov and Ta-Shma's contribution

Not much later, Aharanov and Ta-Shma were motivated to explore adiabatic computation, and relied on the prior literature in Childs, et al., Mike and Ike, and Lloyd to fully reduce the problem of any sparse Hamiltonian simulation (where we have oracle access to the entries of the Hermitian matrices) to local Hamiltonian simulation (as Lloyd had done above).

While Childs et al. partition their parent matrix into nine different, simpler matrices (so, $m=9$ in the above equation), Aharanov and Ta-Shma use a more sophisticated partitioning based on their oracles, into a polynomial number of simpler matrices.

Do Aharanov and Ta-Shma think of a sparse Hamiltonian as a graph that they partition and subsequently Trotterize?

Nonetheless it's a truism in computer science that any graph can be thought of as an adjacency matrix, and interesting properties of the graph can be asked and answered by looking at the spectrum of the adjacency matrix; dually, any matrix can be thought of as a graph and the spectrum of the matrix has interesting implications for the graph. The entries in the matrix are the edge-weights of the graph - which, when unweighted as in Childs et al., are in $\{0,1\}$. But, in contrast to Childs et al. the entries in the Hermitian matrix of a typical sparse Hamiltonian are not​ in $\{0,1\}$ but are, in general, complex numbers in $\mathbb C$.

When the entries are $\{0,1\}$ as in Childs et al., then we know the eigenvalues of SWAP are $\pm 1$! And Trotterization can proceed with various powers of SWAP gates as @DaftWullie helpfully explained to me earlier. But, when the edges are arbitrary entries in $\mathbb C$ then it's not clear whether SWAP'ping is appropriate?

Thus to my question - after they've used the oracle to color and partition their Hermitian matrix, what are Aharanov and Ta-Shma doing to Trotterize the individual matrices?



Your Answer

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