Quantum State Tomography is the task of estimating a quantum state, given many measurements in different bases. We discuss a few variants of what exactly ``estimating a quantum state" means, including maximum likelihood estimation and computing a Bayesian average. We show that, when the measurements are fixed, this problem is NP-Hard to approximate within any constant factor. In the process, we find that it reduces to the problem of approximately computing the permanent of a Hermitian positive semidefinite (HPSD) matrix. This implies that HPSD permanents are also NP-Hard to approximate, resolving a standing question with applications in quantum information and BosonSampling.


翻译:量子州地形学是估算量子状态的任务,考虑到不同基础的许多测量结果。我们讨论“估计量子状态”的确切含义的几种变体,包括最大可能性估算和计算贝叶斯平均值。我们表明,当测量结果固定下来时,这个问题是NP-Hard, 接近于任何恒定系数。在这个过程中,我们发现它减少了大约计算Hermitian正阳性半无限期(HPSD)矩阵永久值的问题。这意味着HPSD永久值也是NP-Hard,可以估计,解决在量子信息和博森抽样应用方面的一个长期问题。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
专知会员服务
50+阅读 · 2020年12月14日
AI算法连载04:数学基础之蒙特卡洛方法与MCMC采样
算法与数学之美
7+阅读 · 2019年8月15日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
7+阅读 · 2019年3月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
深度学习线性代数简明教程
论智
11+阅读 · 2018年5月30日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年1月7日
Arxiv
0+阅读 · 2022年1月5日
VIP会员
相关资讯
AI算法连载04:数学基础之蒙特卡洛方法与MCMC采样
算法与数学之美
7+阅读 · 2019年8月15日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
7+阅读 · 2019年3月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
深度学习线性代数简明教程
论智
11+阅读 · 2018年5月30日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员