Hamiltonian Simulation by Uniform Spectral Amplification
Hamiltonian Simulation by Uniform Spectral Amplification
复制标题
DOI：
--
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
G. Low;I. Chuang
中科院分区：
文献类型：
--
作者：
G. Low;I. Chuang
量子计算机上的哈密顿模拟所承诺的指数级加速，关键取决于哈密顿模型$\hat{H}$和量子电路$\hat{U}$的结构，后者对哈密顿模型的描述进行编码。在探索更好地近似时间演化$e^{-i\hat{H}t}$与误差$\epsilon$的过程中，我们激发了一种系统的方法来理解和利用结构，在这种设置中，哈密顿量被编码为单位电路的测量算子$\hat{U}$用于广义测量。这允许我们在这个框架上定义一个\emph{均匀谱放大}问题，用于扩展具有指数小失真的编码哈密顿谱。我们提出了在层次结构中均匀光谱放大的一般解决方案，其中将$\hat{U}$分解为$n=1,2,3$统一预言机表示对编码的结构知识的增加。结合哈密顿量的结构知识，将这些结果特殊化，使我们能够使用$\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)$查询通过$d$ -稀疏哈密顿量模拟时间演化，其中$\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$。对于对数因子，这是对使用$\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/\epsilon)}}{\log\log{(1/\epsilon)}}\right)$或$\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/\epsilon)^{1/2})$查询的现有技术的多项式改进。在此过程中，我们还证明了$\Omega(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$查询的匹配下界，提出了一种无失真的谱隙放大推广方法，以及一种对未知状态振幅进行乘法运算的幅度放大算法。
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian $\hat{H}$, and the quantum circuit $\hat{U}$ that encodes its description. In the quest to better approximate time-evolution $e^{-i\hat{H}t}$ with error $\epsilon$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits $\hat{U}$ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring $\hat{U}$ into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by $d$-sparse Hamiltonians using $\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)$ queries, where $\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$. Up to logarithmic factors, this is a polynomial improvement upon prior art using $\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/\epsilon)}}{\log\log{(1/\epsilon)}}\right)$ or $\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/\epsilon)^{1/2})$ queries. In the process, we also prove a matching lower bound of $\Omega(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$ queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.