专栏首页arxiv.org翻译专栏光谱和的量子算法(CS AI)
原创

光谱和的量子算法(CS AI)

我们提出并分析了估计对称正定矩阵最常见谱和的新量子算法。对于函数f和矩阵A ∈ Rn×n,谱和定义为Sf(A) := Tr[f(A)] =P jf(λj),其中λjare为特征值。谱和的例子有冯诺依曼熵、逆迹、对数行列式和Schatten-p范数,后者不要求矩阵是SPD。最快的经典随机化算法估计这些量的运行时间至少线性依赖于矩阵非零分量的数量。假设量子访问矩阵,我们的算法在矩阵大小上是次线性的,并且最多二次依赖于其他量,如条件数和近似误差,因此可以与最近文献中提出的大多数随机和分布式经典算法竞争。这些算法可以用作解决许多实际问题的子程序,对于这些实际问题,谱和的估计通常是一个计算瓶颈。

原文题目:Quantum algorithms for spectral sums

原文:We propose and analyze new quantum algorithms for estimating the most common spectral sums of symmetric positive definite (SPD) matrices. For a function f and a matrix A ∈ R n×n , the spectral sum is defined as Sf (A) := Tr[f(A)] = P j f(λj ), where λj are the eigenvalues. Examples of spectral sums are the von Neumann entropy, the trace of inverse, the log-determinant, and the Schatten-p norm, where the latter does not require the matrix to be SPD. The fastest classical randomized algorithms estimate these quantities have a runtime that depends at least linearly on the number of nonzero components of the matrix. Assuming quantum access to the matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other quantities, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in recent literature. These algorithms can be used as subroutines for solving many practical problems, for which the estimation of a spectral sum often represents a computational bottleneck.

原文作者:Alessandro LuongoChangpeng Shao

原文地址:https://arxiv.org/abs/2011.06475

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 具有自修改能力的有界理性代理的性能(CS AI)

    嵌入在复杂环境中的代理的自我修改是难以避免的,无论是通过直接手段(例如,自己的代码修改)还是间接手段(例如,影响操作员、利用漏洞或环境)。虽然有人认为智能代理有...

    识檐
  • 学习丢弃:基于拓扑去噪的鲁棒图神经网络(CS AI)

    形神经网络已被证明是图形分析的强大工具。关键思想是沿着给定图的边递归地传播和聚集信息。尽管已经取得了成功,但是现有的神经网络通常对输入图的质量很敏感。真实世界的...

    识檐
  • 图的多智能体分散信念传播(CS AI)

    我们考虑交互式部分可观测马尔可夫决策过程问题,其中代理位于通信网络的节点。具体来说,我们假设所有消息都有特定的消息类型。此外,每个代理根据交互的信念状态、在本地...

    识檐
  • Linux 中 FQDN 查询及设置

    FQDN:(Fully Qualified Domain Name)全限定域名:同时带有主机名和域名的名称

    xuyaowen
  • CISSP考试指南笔记:4.5 无线网络

    Wireless communication involves transmitting information via radio waves that mo...

    血狼
  • What is Mahalanobis distance? 马氏距离

    https://blogs.sas.com/content/iml/2012/02/15/what-is-mahalanobis-distance.html

    用户1148525
  • python 卷积函数_用Python计算两个函数的卷积

    What is a convolution? OK, that’s not such a simple question. Instead, I am will...

    用户7886150
  • Codeforces Round #622 (Div. 2) 1313 C1

    C1. Skyscrapers (easy version) time limit per test1 second memory limit per te...

    风骨散人Chiam
  • 聊聊flink LocalEnvironment的execute方法

    flink-java-1.6.2-sources.jar!/org/apache/flink/api/java/DataSet.java

    codecraft
  • HDOJ 1194 Beat the Spread!(简单题)

    Problem Description Superbowl Sunday is nearly here. In order to pass the time...

    谙忆

扫码关注云+社区

领取腾讯云代金券