We present the problem of approximating the time-evolution operator
$e^{-i\hat{H}t}$ to error $\epsilon$, where the Hamiltonian $\hat{H}=(\langle
G|\otimes\hat{\mathcal{I}})\hat{U}(|G\rangle\otimes\hat{\mathcal{I}})$ is the
projection of a unitary oracle $\hat{U}$ onto the state $|G\ra
本文提出了用量子行走模拟黑箱哈密顿量的一般方法。这些技术具有两个主要应用：模拟稀疏哈密顿量和实现黑箱酉操作。我们给出了稀疏 Hamiltonians 常数精度下最好的已知模拟方法，复杂度线性地随着稀疏矩阵的最大非零元素数 D 和演化时间 t 增长，并且我们还研究了给定黑箱描述矩阵元素的任意酉操作实现的任务。
我们提出了一种高效的量子算法，用于模拟给定时间 t 内给定稀疏哈密顿量 H 的演化，特别地，当 H 作用于 n 个量子位，每行 / 列最多有恒定数量的非零元素，并且 | H | 受到限制时，我们可以选择任何正整数 k，使得模拟需要 O ((log*n) t^{1+1/2k}) 次访问 H 的矩阵元素。我们证明，除此之外，时间缩放不能显著提高，因为子线性时间缩放不可能。