Duration: 36:15

2,908 views

38

"Efficient simulation of quantum systems motivates quantum computers and is a longstanding problem. We provide a simple quantum algorithm that simulates a general time-independent sparse Hamiltonian $\hat{H}$ on $n$ qubits specified to $m$ bits of precision. Remarkably, the query complexity $N$ of the algorithm is optimal for any combination and value of all input parameters: time $t$, error $\epsilon$, sparsity $d$, and norm $\|\hat{H}\|_{\text{max}}$.
In particular, $N=\Theta(\tau+\frac{\log{(1/\epsilon)}}{\log{\log{(1/\epsilon)}}})$ for $\tau=dt\|\hat{H}\|_{\text{max}} \lesssim \frac{\log{(1/\epsilon)}}{\log{\log{(1/\epsilon)}}}$, and $\Theta(\tau+\log{(\frac{1}{\epsilon})})$ for $\tau \gtrsim \log{(\frac{1}{\epsilon})}$, with an additional primitive gate complexity $\mathcal{O}((n+m\;\text{polylog}(m))N)$. This represents a square-root improvement over prior art where functions of $\tau$ and $\epsilon$ enter multiplicatively instead of additively. Our results are made possible by approaching the simulation problem differently, using a three-step ""quantum signal processing"" methodology, comprised of (1) transducing eigenvalues of $\hat{H}$ into a single ancilla qubit, (2) coherently transforming these eigenvalues in a highly nonlinear manner, and (3) projecting this ancilla with near unity success probability. This computes a large class of unitary functions of $\hat{H}$, of which Hamiltonian simulation is a special case."