Classical simulation of lossy boson sampling using matrix product operators
Classical simulation of lossy boson sampling using matrix product operators
复制标题
DOI：
10.1103/physreva.104.022407
复制
发表时间：
2021-08-05
影响因子：
2.9
通讯作者：
Jiang, Liang
中科院分区：
文献类型：
--
作者：
Oh, Changhun;Noh, Kyungjoo;Jiang, Liang
从理论和实践的角度来描述噪声中尺度量子（NISQ）器件的计算优势是一个重要的任务。在这里，我们数值研究NISQ设备的计算能力，专注于玻色子采样，一个众所周知的有前途的问题，可以表现出量子霸权。我们使用矩阵乘积算子（MPO）模拟来研究有损玻色子采样的硬度，以解决光子损失对经典可模拟性的影响，使用MPO纠缠熵（EE），它表征MPO算法的运行时间。MPO模拟的一个优点是，它的模拟精度可以有效地控制通过增加一个MPO的键的尺寸比其他经典算法提出的日期。值得注意的是，我们通过使用MPO模拟有损玻色子采样，随着输入光子数的增长，其计算成本或MPO EE的行为不同，这取决于损失缩放，表现出与无损玻色子采样不同的功能。特别是当输出光子数比输入光子数的平方根更快时，我们的研究表明MPO模拟的时间复杂度呈指数缩放。相反，当输出光子数的缩放速度慢于输入光子数的平方根时，MPO EE可以减小，这指示指数时间复杂度可能不是必需的。
Characterizing the computational advantage from noisy intermediate-scale quantum (NISQ) devices is an important task from theoretical and practical perspectives. Here, we numerically investigate the computational power of NISQ devices focusing on boson sampling, one of the well-known promising problems which can exhibit quantum supremacy. We study hardness of lossy boson sampling using matrix product operator (MPO) simulation to address the effect of photon loss on classical simulability using MPO entanglement entropy (EE), which characterizes a running time of an MPO algorithm. An advantage of MPO simulation over other classical algorithms proposed to date is that its simulation accuracy can be efficiently controlled by increasing an MPO's bond dimension. Notably, we show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss scaling, exhibiting a different feature from that of lossless boson sampling. Especially when an output photon number scales faster than the square root of an input photon number, our study shows an exponential scaling of time complexity for MPO simulation. On the contrary, when an output photon number scales slower than the square root of an input photon number, MPO EE may decrease, indicating that an exponential time complexity might not be necessary.