Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning-猫眼课题宝

DOI：

10.4230/lipics.icalp.2019.27

发表时间：

2017-10

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

F. Brandão;A. Kalev;Tongyang Li;Cedric Yen-Yu Lin;K. Svore;Xiaodi Wu

我们给出了求解半确定程序（sdp）的两种量子算法，提供了量子加速。我们考虑具有$m$约束矩阵的SDP实例，每个约束矩阵的维度为$n$，排名最多为$r$，稀疏度为$s$。第一个算法假设以单位代价访问一个oracle矩阵。我们显示它运行时$\tilde{O}(s^2(\sqrt{m}\epsilon^{-10}+\sqrt{n}\epsilon^{-12}))$，解决方案的误差$\epsilon$。这给出了一个最优的依赖$m, n$和二次改进比以前的量子算法当$m\approx n$。第二种算法假设一个全量子输入模型，其中矩阵以量子态给出。我们证明了它的运行时间为$\tilde{O}(\sqrt{m}+\text{poly}(r))\cdot\text{poly}(\log m,\log n,B,\epsilon^{-1})$，其中$B$是所有输入矩阵的跟踪范数的上界。特别是复杂度在$n$中是多对数的，在$r$中是多项式的。我们应用第二个SDP求解器来学习关于一组测量值的量子态的良好描述：给定$m$测量值和未知状态$\rho$的副本供应，其排名最多为$r$，我们表明我们可以及时找到$\sqrt{m}\cdot\text{poly}(\log m,\log n,r,\epsilon^{-1})$状态的描述，作为量子电路准备密度矩阵，该密度矩阵在$m$测量值上具有与$\rho$相同的期望值，直至误差$\epsilon$。得到的密度矩阵是最大熵态的近似值，与统计力学中杰恩斯原理所考虑的测量数据一致。与之前的工作一样，我们通过基于矩阵乘权法的经典SDP解算“量化”来获得我们的算法。我们的主要技术贡献之一是一个量子吉布斯态采样器，用于低阶哈密顿量，其维度依赖于多对数，这可能是独立的兴趣。

We give two quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with $m$ constraint matrices, each of dimension $n$, rank at most $r$, and sparsity $s$. The first algorithm assumes access to an oracle to the matrices at unit cost. We show that it has run time $\tilde{O}(s^2(\sqrt{m}\epsilon^{-10}+\sqrt{n}\epsilon^{-12}))$, with $\epsilon$ the error of the solution. This gives an optimal dependence in terms of $m, n$ and quadratic improvement over previous quantum algorithms when $m\approx n$. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is $\tilde{O}(\sqrt{m}+\text{poly}(r))\cdot\text{poly}(\log m,\log n,B,\epsilon^{-1})$, with $B$ an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in $n$ and polynomially in $r$. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given $m$ measurements and a supply of copies of an unknown state $\rho$ with rank at most $r$, we show we can find in time $\sqrt{m}\cdot\text{poly}(\log m,\log n,r,\epsilon^{-1})$ a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as $\rho$ on the $m$ measurements, up to error $\epsilon$. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest.

Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

文献摘要

相似文献