1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.)

$\endgroup$

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.