Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
It is often asserted that Hamiltonian simulation (given some Hermitian matrix, $H$) is BQP-complete.
I don't see how the input to such an algorithm is done without the use of some block-encoding or something similar.
We could encode a Hermitian matrix as an adjacency matrix of an undirected graph, but the weights could only be real numbers. I think this idea was the inspiration for quantum walks.
But is this real-value only variant of hamiltonian simulation still BQP-complete?
I think so. In particular I think this follows from the work of Janzing and Wocjan on mixing times for classical random walks. I’ll link to their paper when I get access to a proper keyboard.
In more detail, they showed that it’s promise-BQP complete to estimate a difference in the number of $m$-length classical random walks for sufficiently nice large graphs, by doing a quantum phase estimation on the Hamiltonian simulation on the adjacency matrix (or Laplacian matrix), acting on a wavefunction $|\psi\rangle$ that corresponds to a difference in the nodes $i$ and $j$.
This difference can be exponentially small, but the adjacency matrix only has real entries (indeed, only 0-1 entries.)
