How does Quantum Simulation actually solve the problem it poses?

Question

The problem of quantum simulation is below:

Given a Hermitian matrix, $H$, compute the unitary $e^{-iHt}$ for any $t > 0$. Using this computed unitary, calculate $e^{-iHt}\psi$ for any given $\psi$

My question is this: how do quantum algorithms actually solve this? To my knowledge, they don't compute the final state, but only produce a possible output of this state. They create a gate that represents $e^{-iHt}$, and send the qubits representing the initial state through this gate.

But after measuring this output, you don't get the computed superposition, but only are measuring what the quantum state outputs upon measurement.

So the problem you cannot actually solve for what the output state is--- you're only solving for a possible output.

Is this correct? If so, how is it useful?

Answer 1

TL/DR: Hamiltonian simulation (quantum simulation) is interesting in itself, as it is likely classically difficult to do, but it is also very interesting as a subroutine for other algorithms that rely on quantum phase estimation. Such algorithms include the quantum algorithm for systems of linear equations, commonly known as the HHL algorithm.

---

Your description of the Hamiltonian simulation problem is, in general, correct - given some hermitian matrix corresponding to a Hamiltonian $H$, the problem is to construct a sequence of unitary gates to simulate $U=e^{-iHt}$ up to some error $\varepsilon$. You can use this as-constructed unitary $U$ to act on some given wavefunction $|\psi\rangle$ to realize another wavefunction $U|\psi\rangle$. You are also correct that measuring this state $U|\psi\rangle$ in the computational basis will only provide a single output.

But even generating a number of outputs from $U|\psi\rangle$ may be interesting, insofar as it may likely be classically difficult to sample from such a wavefunction without a quantum computer. We say that Hamiltonian simulation is BQP-complete, as explained here. The state $U|\psi\rangle$ may still be an interesting state to have possession of, and being BQP-complete implies that there is not an efficient classical algorithm to sample therefrom.

Perhaps much more interestingly, we often want to do additional sophisticated things with our as-constructed unitary $U$. For example, if $|\psi\rangle$ happens to be an eigenstate of $H$ (and of $U$), then if we can construct controlled versions of $U$ we can use these controlled versions in the quantum phase estimation algorithm, to learn the energy of the provided eigenstate $|\psi\rangle$ relative to the Hamiltonian $H$.

Furthermore, we can do other, potentially even more interesting eigenvalue surgery by performing quantum phase estimation on the state $|\psi\rangle$ with respect to the Hamiltonian $H$ that we've simulated with our $U$. For example, if $|\psi\rangle$ is not necessarily an eigenstate of $H$ but is instead in a linear superposition thereof, then we can use Hamiltonian simulation to store the phases of the spectral decomposition of $|\psi\rangle$ in some ancilla registers and invert those phases in superposition. This is the basis of the HHL algorithm, which is also the basis of many algorithms used in quantum machine learning.