Spin Hamiltonians are as hard as Boson Sampling
Borja Peropadre Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, United States Alán Aspuru-Guzik Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, United States Juan José García-Ripoll Instituto de Física Fundamental IFF-CSIC, Calle Serrano 113b, Madrid E-28006, Spain
Abstract
Aaronson and Arkhipov showed that predicting or reproducing the measurement statistics of a general linear optics circuit with a single Fock-state input is a classically hard problem. Here we show that this problem, known as boson sampling, is as hard as simulating the short time evolution of a large but simple spin model with long-range XY interactions. The conditions for this equivalence are the same for efficient boson sampling, namely having small number of photons (excitations) as compared to the number of modes (spins). This mapping allows efficient implementations of boson sampling in small quantum computers and simulators and sheds light on the complexity of time-evolution with critical spin models.
中文速览
玻色采样（Boson Sampling）是一个被证明经典计算机难以模拟的量子光学问题——给定随机线性光学网络和单光子输入，要预测输出光子的分布极其困难。这项工作证明，玻色采样在数学上等价于一个由长程XY相互作用驱动的自旋模型的极短时间演化：只需将输入和输出模式分别映射为两组自旋，让系统演化极短的时间（相当于一次跃迁事件），就能精确重现玻色采样的输出概率分布。这一等价成立的条件与玻色采样有效运行的条件完全相同，即光子数远小于模式数（稀疏极限），因此二者在计算复杂度上完全相同：若经典计算机能模拟这个自旋动力学，则意味着多项式层级的崩塌。这个映射的重要意义在于，它为用捕获离子、超导电路等现有量子模拟器或通用量子计算机来实现玻色采样开辟了新路径，而且自旋版本还可以引入量子纠错来克服线性光学方案固有的精度瓶颈，从而将可实验验证的问题规模推向更大范围。
原文 arXiv:1509.02703;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1509.02703v2