标题： 哈密顿量模拟的最佳样本复杂度 显示英文标题

标题： Hamiltonian Simulation with Optimal Sample Complexity

摘要： 我们研究了哈密顿量仿真中的样本复杂度问题：需要多少份未知量子态的副本才能模拟由该态的密度矩阵编码的哈密顿量？ 我们证明了Lloyd、Mohseni和Rebentrost在[Nat. Phys., 10(9):631--633, 2014]中提出的程序对于此任务是最优的。 我们进一步将他们的方法扩展到多个输入态的情况，展示了如何模拟所提供的任意态的厄米多项式。 作为应用，我们得出了对易子仿真和正交性测试的最佳算法，并给出了一个当能够访问这些态的样本时创建纯态相干叠加态的协议。 我们还表明，这种基于样本的哈密顿量仿真可以作为量子计算的一种通用模型的基础，该模型只需要部分交换操作和简单的单量子比特态即可。 显示英文摘要

摘要： We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.