Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, Maryland 20742, USA.
Phys Rev Lett. 2019 Aug 2;123(5):050503. doi: 10.1103/PhysRevLett.123.050503.
We consider simulating an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t on a quantum computer. We show that this simulation has gate complexity (nt)^{1+o(1)} using product formulas, a straightforward approach that has been demonstrated by several experimental groups. While it is reasonable to expect this complexity-in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill-we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.
我们考虑在量子计算机上模拟具有最近邻相互作用的 n 量子位哈密顿量，其在时间 t 上的演化。我们使用乘积公式展示了这种模拟的门复杂度为(nt)^{1+o(1)}，这是一种已经被几个实验组证明的直接方法。虽然期望这种复杂度是合理的——特别是，这一点被 Jordan、Lee 和 Preskill 未经严格证明就声称过——但我们不知道一个直接的证明。我们的方法基于对乘积公式的局部误差结构的分析，这一方法由 Descombes 和 Thalhammer 引入，并在这里得到了显著简化。我们为典型的乘积公式证明了误差界，其中包括众所周知的构造，如 Lie-Trotter-Suzuki 公式。我们还为含时哈密顿量模拟开发了一种局部误差表示，并且讨论了其在周期性边界条件、定域相互作用和更高维度下的推广。结合之前的下界，我们的结果表明，乘积公式可以以几乎最优的门复杂度模拟晶格哈密顿量。
