论文标题
估计随机量子电路的平均值硬度，并在误差指数中进行线性缩放
Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent
论文作者
论文摘要
我们考虑计算随机量子电路输出概率的加法近似值的硬度。我们考虑三个随机电路系列，即HAAR随机，$ P = 1 $ QAOA和随机IQP电路。我们的结果如下。对于带有$ m $门的HAAR随机电路，我们通过显示$ \ MATHSF {COC_ = P} $平均案例添加剂近似值的硬度来改进先前的结果，以$ 2^{ - o（m）} $的不精确度。对此类问题的有效经典模拟将意味着多项式层次结构的崩溃。对于恒定的深度电路，即，当$ m = o（n）$时，指数中的线性缩放位置在显示样品硬度所需的缩放率的常数之内。在我们的工作之前，仅在Bouland等人（2021）中显示了这种结果。我们还使用多项式插值的最新结果来显示$ \ mathsf {coc_ = p} $硬度在$ \ mathsf {bpp} $还原下而不是$ \ mathsf {bpp {bpp}^{\ mathsf {\ mathsf {np}}} $ reductions $ reductions。这可以改善HAAR随机电路的先前工作结果，包括误差缩放和减少的功能。接下来，我们考虑随机$ P = 1 $ QAOA和IQP电路，并表明在平均值中，它是$ \ MATHSF {COC_ = P} $难以将输出概率近似于$ 2^{ - O（n）} $的添加误差。对于$ p = 1 $ QAOA电路，这项工作构成了近似于随机QAOA电路的输出概率的第一个平均值硬度，其中包括Sherrington-Kirkpatrick和Erdös-Renyi图。对于IQP电路，我们的结果的结果是，即使在平均案例中，也很难将具有假想耦合的Ising分区函数近似于$ 2^{ - o（n）} $的添加误差，这在平均案例中也很难，这在乘数近似值的最差近似硬度上扩展到了先前的工作，从而扩展了对ISING分区功能的最差近似硬度。
We consider the hardness of computing additive approximations to output probabilities of random quantum circuits. We consider three random circuit families, namely, Haar random, $p=1$ QAOA, and random IQP circuits. Our results are as follows. For Haar random circuits with $m$ gates, we improve on prior results by showing $\mathsf{coC_=P}$ hardness of average-case additive approximations to an imprecision of $2^{-O(m)}$. Efficient classical simulation of such problems would imply the collapse of the polynomial hierarchy. For constant depth circuits i.e., when $m=O(n)$, this linear scaling in the exponent is within a constant of the scaling required to show hardness of sampling. Prior to our work, such a result was shown only for Boson Sampling in Bouland et al (2021). We also use recent results in polynomial interpolation to show $\mathsf{coC_=P}$ hardness under $\mathsf{BPP}$ reductions rather than $\mathsf{BPP}^{\mathsf{NP}}$ reductions. This improves the results of prior work for Haar random circuits both in terms of the error scaling and the power of reductions. Next, we consider random $p=1$ QAOA and IQP circuits and show that in the average-case, it is $\mathsf{coC_=P}$ hard to approximate the output probability to within an additive error of $2^{-O(n)}$. For $p=1$ QAOA circuits, this work constitutes the first average-case hardness result for the problem of approximating output probabilities for random QAOA circuits, which include Sherrington-Kirkpatrick and Erdös-Renyi graphs. For IQP circuits, a consequence of our results is that approximating the Ising partition function with imaginary couplings to an additive error of $2^{-O(n)}$ is hard even in the average-case, which extends prior work on worst-case hardness of multiplicative approximation to Ising partition functions.
