1

The wikipedia article for Hamiltonian simulation lists two complexities: gate and query complexity.

These two types of complexity refer to two different things; gate complexity is the asymptotic number of gates needed to run the program, whereas query complexity refers to the number of queries to an 'oracle' that provides input to the program.

The article mentions that gate complexity matters more if the Hamiltonian is given explicitly, but query complexity matters more if the Hamiltonian is given by an oracle. But this is a bit confusing to me.

In 'standard' (quantum) computing, the input to a circuit is given by some binary string, x, given as a statevector $| \psi \rangle$ in the computational basis. There would be no query complexity in this case, and this is what I'm assuming "explicit" representation refers to. So suppose we are given some circuit, $A$, along with two binary strings: $H$, $t$, $\frac{1}{\epsilon}$.

The circuit would look something like this:

enter image description here

Sorry for the crude handwriting.

But I don't think this is correct; this seems way too far off from the query access model. Can someone explain how this explicit representation works?

Andrew Baker
  • 279
  • 1
  • 8

1 Answers1

1

Your circuit appears a little confusing to me. The Hamiltonian $H$ is a hermitian matrix, and is not a ket (a vector) itself. The output of the evolution is not $|e^{-iHt}\pm\varepsilon\rangle$, but is rather $\approx e^{-Ht}|\psi\rangle$ for some (eigenstate) $|\psi\rangle$.

When simulating a Hamiltonian acting on such a state, e.g. $A|\psi\rangle=e^{-iHt}|\psi\rangle$, in both the standard model and the query model, generally the input state $|\psi\rangle$ is always assumed to be provided explicitly. The difference between the two models is how the entries of $H$ - e.g., the values of, say, $H_{ij}$ for the $i$th row and the $j$th column of the matrix, are provided.

The recent massive threads on Aaronson's blog about the difference between explicit gate counts and query counts, even for something as "simple" as Grover's algorithm, show that at least this distinction continues to be a source of controversy.

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
  • Thanks for your answer. Sorry for not being clear with my circuit diagram. I was trying to use $| H \rangle$ and $| e^{-iHt} \rangle$ as binary representations of the matrices (something that we could represent on a Turing machine). The oracle model cannot provide input to a Turing machine (unless we are "inputting" the oracle. This is why I used the ket vectors to represent the Hamiltonian and the evolution. Is this not what's used in the explicit model for Hamiltonian simulation? – Andrew Baker May 16 '23 at 23:46
  • Even in the circuit model we do concern ourselves with a Turing machine that's used to build the circuit for each input size $n$. As in your previous question, though, this Turing machine itself is best thought of as being external to any circuit. I find it awkward to consider $|H\rangle$ and $|t\rangle$ and $|\fac{1}{\varepsilon}\rangle$ as inputs to a quantum circuit - I think of them as classical programs. – Mark Spinelli May 17 '23 at 14:05